INTERFACE MPZ; (* This is an intermediate interface to establish the association between the module "MPInt" (the implementation in Modula-3 of the Multiple Precision Integer package) with the routines defined by GNU Multiple Precision package (GMP) which is implemented in "C". In fact, the interface "MPNat" defines the signatures of the external procedures implemented by GMP for unsigned integers (module "mpn"). And the module "MPInt" take cares of memory allocation and all routines not involving "MPNat". Here, we only take care of routines that make use of routines defined in "MPNat" (indeed, the routines of "mpn"). This module never allocates space for new numbers; all routines always write the result in some area passed by the caller; so, the routines defined in "MPInt" that call the routines defined here have to create sufficient space required by the "mpn" routines. Created on Jun 05, 1997 by Marcus Vinicius A. Andrade Rewritten on Dec 10 1997 by Marcus Vinicius A. Andrade (******** representation of a (big) integer ******) <--------------------------- nl ----------------------------> |Number Sign| Least | | | Most | |-1 => Neg. |Significant| | |Significant| | 0 => Zero | Limb | | | Limb | |+1 => Pos. | | | | | |___________|___________|___________|___________|___________| ^ ^ ^ | | | 0 nn is zero iff z=0 *) IMPORT MPNat, Ctypes, Word; CONST MP_NEG = -1; MP_ZERO= 0; MP_POS = 1; Dgt_Size = MPNat.DIGIT_SIZE; TYPE SizeT = MPNat.mp_sizeT; Sign = [-1..+1]; BaseT = [2..16]; NumDgt = Ctypes.unsigned_long_int; DigitT = Word.T; (* each "limb" in the representation above *) T = ARRAY OF DigitT; (* the vector where the number is stored; the FIRST position in this array is used to define the signal of the number, that is: z[0]=MP_ZERO=> Number is zero z[0]=MP_NEG => Number is negative z[0]=MP_POS => Number is positive *) (* -------------------------------------------------------- *) (* Some general routines to manipulate big INTEGER *) (* -------------------------------------------------------- *) PROCEDURE FirstPosition(READONLY x : T) : CARDINAL; (* Retuns the first position where the number start excluding the signal position *) PROCEDURE GetSize(READONLY x : T) : CARDINAL; (* Returns the number of limbs allocated to "x" *) PROCEDURE NumDigits(READONLY x : T) : SizeT; (* Returns the number of limbs used by "x", it does not consider leading zeros. If "x=0" then returns 0. *) PROCEDURE GetDigit(READONLY x : T; i: CARDINAL) : DigitT; (* Returns the value stored in the limb "x[fp+i-1]" where "fp=FirstPosition(x)" *) PROCEDURE SetDigit(VAR x : T; i: CARDINAL; v: DigitT); (* Sets to "v" the value of the limb "x[fp+i-1]" where "fp=FirstPosition(x)" *) PROCEDURE SetSign(VAR x : T; s: Sign); (* Sets to "s" the sign of "z" *) PROCEDURE GetSign(READONLY x : T) : Sign; (* Returns the sign of "z", that is, -1 if z < 0; 0 if z = 0; +1 if z > 0. *) PROCEDURE IsZero(READONLY x : T) : BOOLEAN; (* Returns TRUE iff x=0, that is, if the signal of "x" is MP_ZERO *) PROCEDURE Num_IsZero(READONLY x: T): BOOLEAN; (* Returns TRUE iff all limbs in "x" are zero *) PROCEDURE FillWithZero(VAR x: T; p,s: CARDINAL); (* Sets to zero "x[fp+p+1]" to "x[fp+p+s]" where "fp=FirstPosition(x)" *) PROCEDURE CountLeadingZerosInDigit(d : DigitT) : NumDgt; (* Counts the number of zero-bits from the most significant bit (msb) to the first non-zero bit in (limb) "d". This is the number of steps "d" needs to be shifted left to set the msb *) PROCEDURE CountTrailingZerosInDigit(d: DigitT) : NumDgt; (* Counts the number of zero-bits from the least significant bit (lsb) to the the first non-zero bit in (limb) "d". This is the number of steps "d" needs to be shifted right to set the lsb *) PROCEDURE CountLeastSignificantLimbZero(READONLY x: T) : NumDgt; (* Counts the number of the least significant limb of "x" that are zero *) PROCEDURE ShiftDigit(d: DigitT; s: NumDgt) : DigitT; (* Shifts the digit "d", "s" positions to right if "s > 0" and to left if "s < 0" *) (* -------------------------------------------------------- *) (* Arithmetic operators, I/O routines, etc *) (* -------------------------------------------------------- *) PROCEDURE Add(VAR z: T; READONLY x,y : T; xl,yl: SizeT); (* Computes "z=x + y"; Requires |x| >= |y| *) PROCEDURE Sub(VAR z: T; READONLY x,y : T; xl,yl: SizeT); (* Computes "z=x - y"; Requires |x| >= |y| *) PROCEDURE Mult(VAR z: T; READONLY x,y : T; xl,yl: SizeT); (* Computes "z=x * y"; Requires |x| >= |y| *) PROCEDURE DivRem(VAR z,r : T; READONLY x,y : T; xl,yl: SizeT) : DigitT; (* Computes z = x DIV y and r = x MOD y. Returns the most significant limb of the quocient. It must be included at quocient. The values of q and r are such that x=yq + r and 0 <= r < |z|. If y=0 then termines abnormally. If y>0 then returns FLOOR(x/y) If y<0 then returns CEIL(x/y), where / is the real numbers division. *) PROCEDURE LShift(VAR z: T; READONLY x: T; xl: SizeT; d: CARDINAL) : SizeT; (* Shifts "x", "d" bits to left and writes the "xl" least significants limbs of the result to "z" and returns the bits shifted out to the left. *) PROCEDURE RShift(VAR z: T; READONLY x: T; xl: SizeT; d: CARDINAL) : SizeT; (* Shifts "x", "d" bits to right and writes the "xl" most significants limbs of the result to "z" and returns the bits shifted out to the right. *) PROCEDURE Comp(READONLY x,y : T; s: SizeT) : Sign; (* Returns the value of (x-y)/|x-y|, that is, -1 if x < y, 0 if x = y, +1 otherwise. *) PROCEDURE GCD(VAR z : T; READONLY x,y : T; xl,yl: SizeT) : SizeT; (* Computes "z = gcd(x,y)" and returns the size in limbs of "gcd(x,y)" *) PROCEDURE Sqrt(VAR z,r : T; READONLY x: T; xl: SizeT) : SizeT; (* Computes "z" equal to the (floor of) square root of "x", writes the remainder at "r" and returns the size in limbs of "z". *) PROCEDURE IsPerfectSquare(READONLY x: T) : BOOLEAN; (* Returns true if there exists an integer "z" such that "x=z^2" *) PROCEDURE ToString(READONLY x : T; base : BaseT:=10) : TEXT; (* Returns the string representing the number "x" in the specified base. Assumes that 2 <= base <= 16. *) PROCEDURE FromString(VAR z: T; str : TEXT; strlen : CARDINAL; base : BaseT:=10); (* Writes on "z" the number whose value is given by the string "str" in the specified base. The string may contain leading spaces (that will be ignored), followed by an optional sign, followed by a series of digits. Assumes that 2 <= base <= 16. *) PROCEDURE Random(VAR z: T; zl : SizeT; s: Sign); (* Writes on "z" a random number with "zl" digits whose signal is "s" *) END MPZ.