## ComputerArithmetic Module

This file implements functions for radix integer arithmetic

### Types

 Type Description SchoenhageStrassen works on the ring ZF[2^{2^n}+1] having elements 0,...,2^{2^n}. We represent its elements as records with a number num and the information about the ring they belong to (the algorithm makes recursive calls to smaller rings ZF[2^{2^k}+1] so to avoid confusion about the rings we are currently working with, the numbers carry the information about the ring they belong to.

### Functions and values

 Function or value Description  ChangeBaseOfComplementNumber x oldB newB  Full Usage: ChangeBaseOfComplementNumber x oldB newB Parameters: x : int[] oldB : int newB : int Returns: BigInteger * int[] Converting the base of a given B-complement number: Given the digits x of a B-complemnt number to base oldB, the function computes (dVal,y) where dVal is a BigInteger that denotes the value of the given number in decimal and y are the digits of the B-complement representation of that number to the new radix newB. x : int[] oldB : int newB : int Returns: BigInteger * int[]  ChangeBaseOfRadixNumber x oldB newB  Full Usage: ChangeBaseOfRadixNumber x oldB newB Parameters: x : int[] oldB : int newB : int Returns: BigInteger * int[] Converting the base of a given radix-B number: Given the digits x of a radix-B number to base oldB, the function computes (dVal,y) where dVal is a BigInteger that denotes the value of the radix-B number in decimal and y are the digits of that number to the new radix newB. x : int[] oldB : int newB : int Returns: BigInteger * int[]  ComplementNumber2Int x radixBase  Full Usage: ComplementNumber2Int x radixBase Parameters: x : int[] radixBase : int Returns: int convert a complement number to an integer (if possible) x : int[] radixBase : int Returns: int  Convolution x y  Full Usage: Convolution x y Parameters: x : ZFnum[] y : ZFnum[] Returns: ZFnum[] convolution of two vectors x and y (which is the result of the Fourier transform of x and y if these are doubled in size by padding zeros to the higher indices) x : ZFnum[] y : ZFnum[] Returns: ZFnum[]  DecodeRNS quiet primes rnsNums  Full Usage: DecodeRNS quiet primes rnsNums Parameters: quiet : bool primes : BigInteger[] rnsNums : BigInteger[][] Returns: BigInteger[] Decode an array of given RNS numbers rnsNums for the RNS base primes, i.e., primes are the relatively prime numbers that form the RNS base, and the function computes for every rnsNums[j] a value X[j] such that rnsNums[j][i] = X[j] mod prime[i] for all i. quiet : bool primes : BigInteger[] rnsNums : BigInteger[][] Returns: BigInteger[]  ExtEuclid a b  Full Usage: ExtEuclid a b Parameters: a : BigInteger b : BigInteger Returns: BigInteger * BigInteger * BigInteger ExtEuclid implements the extended Euclidean algorithm (see also Lemma of Bézout): For given integers a and b, it computes numbers u,v,g such that u*a + v*b = g = gcd(a,b). a : BigInteger b : BigInteger Returns: BigInteger * BigInteger * BigInteger  FloatingPointTool qscoll  Full Usage: FloatingPointTool qscoll Parameters: qscoll : NameValueCollection to be called from the web page as the online teaching tool qscoll : NameValueCollection  FourierMatrix mkInv n p  Full Usage: FourierMatrix mkInv n p Parameters: mkInv : bool n : int p : int Returns: ZFnum[][] Generate the (inverse) 2^p x 2^p Fourier matrix in the ring ZF[2^{2^n}+1]. Note that w = 2^{2^{n+1-p}} is a principal (2^p)-th root of unity and that w^{-1} = 2^{2^{n+1}-2^{n+1-p}} is its multiplicative inverse (for w=2, we would use p=n+1). mkInv : bool n : int p : int Returns: ZFnum[][]  FromFloatingPoint (s, e, m) B  Full Usage: FromFloatingPoint (s, e, m) B Parameters: s : bool e : int[] m : int[] B : int Returns: float Convert a given floating point representation (without hidden bits) given as triple (s,e,m) where s is the sign, e the exponent and m the mantissa (exponent and mantissa were given as radix-B numbers). The result is the corresponding floating point number. s : bool e : int[] m : int[] B : int Returns: float  Int2ComplementNumber x radixBase  Full Usage: Int2ComplementNumber x radixBase Parameters: x : int radixBase : int Returns: int[] convert an integer to a radix number of given base x : int radixBase : int Returns: int[]  Int2RadixNumber x radixBase  Full Usage: Int2RadixNumber x radixBase Parameters: x : int radixBase : int Returns: int[] convert an integer to a radix number of given base x : int radixBase : int Returns: int[]  IntDivRestore ostr doPrint B x y  Full Usage: IntDivRestore ostr doPrint B x y Parameters: ostr : TextWriter doPrint : bool B : int x : int[] y : int[] Returns: int[] * int[] This function implements a restoring division for B-complement numbers. In case argument doPrint is true, it will print the calculation to stream ostr, otherwise, it just returns the quotient q and remainder r as (q,r). ostr : TextWriter doPrint : bool B : int x : int[] y : int[] Returns: int[] * int[]  IntNatAddCRA isBC B x y  Full Usage: IntNatAddCRA isBC B x y Parameters: isBC : bool B : int x : int[] y : int[] Returns: int[] * int[] This function implements a carry-ripple adder that can be configured via input isBC to work with B-complement or radix-B numbers in that it applies functions alpha/beta to the most significant digits or not. It is required that the operands have the same number of digits (you may use functions ZeroEqualize and SignEqualize to achieve this). The output is a pair of B-complement or radix-B numbers (c,s) where c and s holds the carry and sum digits, respectively. isBC : bool B : int x : int[] y : int[] Returns: int[] * int[]  IntNatMultCRA isBC B x y  Full Usage: IntNatMultCRA isBC B x y Parameters: isBC : bool B : int x : int[] y : int[] Returns: int[,] * int[,] * int[] This function implements a multiplier array that can be configured via input isBC to work with B-complement or radix-B numbers in that may apply functions alpha/beta to the most significant digits. The output is a pair of B-complement or radix-B numbers (pp,cp,p) where pp holds the partial products, cp are the carry digits for computing rowise additions, and p is the final product, respectively. isBC : bool B : int x : int[] y : int[] Returns: int[,] * int[,] * int[]  IntNatMultCSA isBC B x y  Full Usage: IntNatMultCSA isBC B x y Parameters: isBC : bool B : int x : int[] y : int[] Returns: int[,] * int[,] * int[] * int[] This function implements a multiplier array using carry-save addition that can be configured via input isBC to work with B-complement or radix-B numbers in that may apply functions alpha/beta to the most significant digits. The output is a pair of B-complement or radix-B numbers (pp,cp,cr,p) where pp holds the partial products, cp are the carry digits for computing rowise additions, cr are the carry bits for the final additiona, and p is the final product, respectively. isBC : bool B : int x : int[] y : int[] Returns: int[,] * int[,] * int[] * int[]  IntNatSubCRA isBC B x y  Full Usage: IntNatSubCRA isBC B x y Parameters: isBC : bool B : int x : int[] y : int[] Returns: int[] * int[] This function is a carry-ripple subtraction that can be configured via input isBC to work with B-complement or radix-B numbers in that it applies functions alpha/beta to the most significant digits or not. It is required that the operands have the same number of digits (you may use functions ZeroEqualize and SignEqualize to achieve this). The output is a pair of B-complement or radix-B numbers (c,s) where c and s holds the carry and sum digits, respectively. isBC : bool B : int x : int[] y : int[] Returns: int[] * int[]  MultInverse a p  Full Usage: MultInverse a p Parameters: a : BigInteger p : BigInteger Returns: BigInteger Compute multiplicative inverse b which satisfies (a*b) mod p = 1 for a given number a and a number p such that gcd(a,p) = 1. This is done by (ExtEuclid a p) which yields numbers (x,y,g) such that a*x+p*y = gcd(a,p) = 1 holds, thus a*x mod p = 1 a : BigInteger p : BigInteger Returns: BigInteger  NatDivRestore ostr doPrint B x y  Full Usage: NatDivRestore ostr doPrint B x y Parameters: ostr : TextWriter doPrint : bool B : int x : int[] y : int[] Returns: int[] * int[] This function implements a restoring division for radix-B numbers. In case argument doPrint is true, it will print the calculation to stream ostr, otherwise, it just returns the quotient q and remainder r as (q,r). ostr : TextWriter doPrint : bool B : int x : int[] y : int[] Returns: int[] * int[]  NegativeWrappedConvolution x y  Full Usage: NegativeWrappedConvolution x y Parameters: x : ZFnum[] y : ZFnum[] Returns: ZFnum[] negative wrapped convolution of two vectors x and y x : ZFnum[] y : ZFnum[] Returns: ZFnum[]  ParseNumber s  Full Usage: ParseNumber s Parameters: s : string Returns: int[] * int parsing numbers: a number is expected as "<[C;F;3;2]>16" where instead semicola also comma are allowed, and in case of a base less than 35, the digits 0..9 A..Z may be directly concatenated. One may even use "<...>" and "[...]" instead of "<[...]>" for the digit list. s : string Returns: int[] * int  PositiveWrappedConvolution x y  Full Usage: PositiveWrappedConvolution x y Parameters: x : ZFnum[] y : ZFnum[] Returns: ZFnum[] positive wrapped convolution of two vectors x and y (which is the result of the Fourier transform of x and y) x : ZFnum[] y : ZFnum[] Returns: ZFnum[]  PrintMatrix m  Full Usage: PrintMatrix m Parameters: m : ZFnum[][] print a matrix over numbers ZF[2^{2^n}+1] (like the Fourier matrix) m : ZFnum[][]  RadixArithmeticTool qscoll  Full Usage: RadixArithmeticTool qscoll Parameters: qscoll : NameValueCollection main function to be called by the radix-B and B-complement number tool qscoll : NameValueCollection  RadixBaseConverterTool qscoll  Full Usage: RadixBaseConverterTool qscoll Parameters: qscoll : NameValueCollection main function to be called by the RadixBaseConverterTool qscoll : NameValueCollection  RadixNumber2Int x radixBase  Full Usage: RadixNumber2Int x radixBase Parameters: x : int[] radixBase : int Returns: int convert a radix number to an integer (if possible) x : int[] radixBase : int Returns: int  ResidueArithmeticTool qscoll  Full Usage: ResidueArithmeticTool qscoll Parameters: qscoll : NameValueCollection main function to be called by the residue number tool qscoll : NameValueCollection  SchoenhageStrassenRadixB xI yI  Full Usage: SchoenhageStrassenRadixB xI yI Parameters: xI : BigInteger yI : BigInteger reduction of radix-B multiplication to a multiplication in ZF[2^{2*l}+1] xI : BigInteger yI : BigInteger  SchoenhageStrassenTool qscoll  Full Usage: SchoenhageStrassenTool qscoll Parameters: qscoll : NameValueCollection main function to be called by the SchoenhageStrassen tool qscoll : NameValueCollection  SchoenhageStrassenZFnum x y  Full Usage: SchoenhageStrassenZFnum x y Parameters: x : ZFnum y : ZFnum Returns: ZFnum[] * BigInteger demonstration of SchoenhageStrassen multiplication in ZF[2^{2*l}+1] x : ZFnum y : ZFnum Returns: ZFnum[] * BigInteger  SignEqualize B x y  Full Usage: SignEqualize B x y Parameters: B : int x : int[] y : int[] Returns: int[] * int[] given numbers x and y, extend the shorter one by B-1 to give them the same length B : int x : int[] y : int[] Returns: int[] * int[]  SignExtend B n x  Full Usage: SignExtend B n x Parameters: B : int n : int x : int[] Returns: int[] extend B-complement number x by n digits B : int n : int x : int[] Returns: int[]  SignReduce B x  Full Usage: SignReduce B x Parameters: B : int x : int[] Returns: int[] remove redundant digits from a B-complement number B : int x : int[] Returns: int[]  SlowFourierTransform m x  Full Usage: SlowFourierTransform m x Parameters: m : ZFnum[][] x : ZFnum[] Returns: ZFnum[] compute a slow Fourier transform (just a matrix multiplication) m : ZFnum[][] x : ZFnum[] Returns: ZFnum[]  ToFloatingPoint noPrint isNegative x y B mDigits eDigits  Full Usage: ToFloatingPoint noPrint isNegative x y B mDigits eDigits Parameters: noPrint : bool isNegative : bool x : int[] y : int[] B : int mDigits : int eDigits : int Returns: (string * (bool * int[] * int[]) option) list Given radix-B numbers x and y, this function computes several floating point representations of number x/y where additionally the sign is determined by input isNegative. The floating point numbers will all have mDigits digits for the mantissa and eDigits digits for the exponent, and both are given in base B also. The result is a list of pairs of the form (mode,f) where f is an optional triple (sign,mantissa,exponent) where mode is one of the following rounding modes: roundToZero roundToMinusInfty roundToPlusInfty roundToNearestZero roundToNearestMinusInfty roundToNearestPlusInfty roundToNearestEven Clearly, the triple (sign,mantissa,exponent) denotes the representation of the floating point number in radix B with mDigits for the mantissa, and eDigits for the exponent (with bias). noPrint : bool isNegative : bool x : int[] y : int[] B : int mDigits : int eDigits : int Returns: (string * (bool * int[] * int[]) option) list  ZeroEqualize x y  Full Usage: ZeroEqualize x y Parameters: x : int[] y : int[] Returns: int[] * int[] given numbers x and y, extend the shorter one by zeros to give them the same length x : int[] y : int[] Returns: int[] * int[]  ZeroExtend n x  Full Usage: ZeroExtend n x Parameters: n : int x : int[] Returns: int[] extend radix-B number x by n digits n : int x : int[] Returns: int[]  ZeroReduce x  Full Usage: ZeroReduce x Parameters: x : int[] Returns: int[] remove redundant digits from a radix-B number x : int[] Returns: int[]  num2Str x B  Full Usage: num2Str x B Parameters: x : int[] B : int Returns: string converting number x given to base B to a string; for bases less than 36, notation without semicola and commata is preferred for the digit list x : int[] B : int Returns: string  printAddCRA ostr printVars isBC B x y  Full Usage: printAddCRA ostr printVars isBC B x y Parameters: ostr : TextWriter printVars : bool isBC : bool B : int x : int[] y : int[] This function prints a carry-ripple adder as a SVG graphics. Input printVars is used to control whether variables like "x[2]" are printed or whether their values are printed in the svg graphics. ostr : TextWriter printVars : bool isBC : bool B : int x : int[] y : int[]  printMultCRA ostr printVars isBC B x y  Full Usage: printMultCRA ostr printVars isBC B x y Parameters: ostr : TextWriter printVars : bool isBC : bool B : int x : int[] y : int[] This function prints a carry-ripple multiplier array as a SVG figure. Input printVars is used to control whether variables like "x[2]" are printed or whether their values are printed in the svg graphics. ostr : TextWriter printVars : bool isBC : bool B : int x : int[] y : int[]  printMultCSA ostr printVars isBC B x y  Full Usage: printMultCSA ostr printVars isBC B x y Parameters: ostr : TextWriter printVars : bool isBC : bool B : int x : int[] y : int[] This function prints a carry-save multiplier array as a SVG figure. Input printVars is used to control whether variables like "x[2]" are printed or whether their values are printed in the svg graphics. ostr : TextWriter printVars : bool isBC : bool B : int x : int[] y : int[]  printSubCRA ostr printVars isBC B x y  Full Usage: printSubCRA ostr printVars isBC B x y Parameters: ostr : TextWriter printVars : bool isBC : bool B : int x : int[] y : int[] This function prints a carry-ripple adder as a SVG figure. Input printVars is used to control whether variables like "x[2]" are printed or whether their values are printed in the svg graphics. ostr : TextWriter printVars : bool isBC : bool B : int x : int[] y : int[]