Averest


ComputerArithmetic Module

This file implements functions for radix integer arithmetic

Types

Type Description

ZFnum

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.

ZFnumFailure

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:
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:
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:
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:

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:
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:
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:
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:

print a matrix over numbers ZF[2^{2^n}+1] (like the Fourier matrix)

m : ZFnum[][]

RadixArithmeticTool qscoll

Full Usage: RadixArithmeticTool qscoll

Parameters:

main function to be called by the radix-B and B-complement number tool

qscoll : NameValueCollection

RadixBaseConverterTool qscoll

Full Usage: RadixBaseConverterTool qscoll

Parameters:

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:

main function to be called by the residue number tool

qscoll : NameValueCollection

SchoenhageStrassenRadixB xI yI

Full Usage: SchoenhageStrassenRadixB xI yI

Parameters:

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:

main function to be called by the SchoenhageStrassen tool

qscoll : NameValueCollection

SchoenhageStrassenZFnum x y

Full Usage: SchoenhageStrassenZFnum x y

Parameters:
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:
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[]