Last update June 5, 2004

etc.bigint

There are times when you need more precision in an integer than an int, or even a long can provide. That's what this module is for. At its heart is a class, Int, which strives to be exactly what you'd expect of an unlimited precision integer.

The module etc.bigint provides a three-layered heirarchy of functionality. At the middle level is the Int class itself. In addition to the implementation of the Int class itself, this layer also provides a number of supporting functions. Below that, there are lower-level functions upon which the Int class relies, and which you can also call directly. These are based, not on Ints, but on arrays of uints. The low-level functions take pointers and lengths as their arguments, and so should be used with caution. In addition, the low level functions all operate on unsigned integers, whereas the Int class is signed. Finally, at the highest level, there are many math functions which are implemented in terms of Ints. These provide high level math functions such as square roots, primality testing and so forth.

We begin with a description of the Int class. First, please note that Int is a class, not a primitive object, so you cannot have statements such as the following:

Example
	
	Int n = 42;             // Not allowed
	
	

Instead, you have to do this:

Example
	
	Int n = new Int(42);    // Correct
	
	

But of course, big integers, by their very nature, will sometimes be too big to fit in an int, and so Int provides a contructor which takes a string, allowing you to do things like:

Example
	
	Int n = new Int("1759603394719674893113249834366313119002385700012");
	
	

Int also has a toString property, so you can print the value of an Int like this:

Example
	
	printf("n = %.*s\n", n.toString);
	
	

All of the operator overloads are implemented as you would expect, except that the assigning operator overloads are purposefully not implemented, and should never be. This is because, if you do a = b; followed by ++b;, you would not expect the value of a to change. Since class objects are passed by reference, this is exactly what we have avoided. This means that only non-assigning operators may be used.

Example
	
	a += b;         // This won't compile -- assigning operators are not permitted
	
	a = a + b;      // This is the correct way to do it.
	
	
	

Well, that's enough of an introduction. Let's get to the specifics.

Installation

The Int class

Supporting functions

High level functions

Low level functions

Versions

To do (future work)


Installation

Copy the ".d" source files onto your computer, retaining the directory structure. You can either copy them into your existing import search path, or put them somewhere else and then add that somewhere else to your import seach path. Now you can either compile the files (all of them), making sure you give the compiler your import search path - in which case you will be linking against the actual object files you create; or you can simply link your application against the appropriate version of libdeimos.lib, which is included in the download. (Unfortunately only prebuilt Win32 libraries are included)

In your own code, you can now get big integer functionality by including the following line:

	
	import etc.bigint;
	

The Int class

These are the member functions and variables of the class Int
class Int
static Int ZERO
static Int ONE
static Int TWO
static Int MINUS_ONE
Preconstructed Ints

enum SignMode { NORMAL, MINUS_SPACE, MINUS_SPACE_PLUS }
Used by the format(...) function
enum Round { TOWARD_ZERO, TOWARD_INFINITY, TOWARD_MINUS_INFINITY }
Used by the divMod(...) function

this(int value)
Construct an Int having the value value
this(uint value)
Construct an Int having the value value
this(long value)
Construct an Int having the value value
this(ulong value)
Construct an Int having the value value
this(float value)
Construct an Int having the value value
this(double value)
Construct an Int having the value value
this(real value)
Construct an Int having the value value
this(char[] value)
Parse the string value and construct an Int having the parsed value. The syntax of the string must be as follows:
Optionally a sign character, + or -
Optionally a radix specifier (see below)
Digits in the correct radix, and the underscore ('_') character
The radix spedifier must be one of:
0x or 0X
Indicates that the number is presented in hexadecimal
0d or 0D
Indicates that the number is presented in decimal
0o or 0O
Indicates that the number is presented in octal
0b or 0B
Indicates that the number is presented in binary
If the radix specifier is omitted, the number is assumed to be decimal. Note that, if the radix specifier is omitted, the number is not permitted to begin with a leading zero. This is in order to avoid confusion with those standards in which a leading zero implies octal. Digits may be in upper or lower case. For convenience, the underscore character is allowed (and ignored), so that you can group digits into convenient groups. Throws an IntException  if an invalid digit is encountered.
this(char[] value, uint radix)
Parse the string value and construct an Int having the parsed value. The syntax of the string is the same as for the previous constructor except that the radix specifier must be omitted (as it is explicitly stated in the second parameter). Note that only radices betweeen 2 and 16 inclusive are permitted. Throws an IntException if an invalid digit is encountered.
this(uint[] value, bool isNegative)
Construct an Int from a low level array of uints. The array must consist of zero or more uints, each of which represents a successive radix 232 digit, with element zero being the least significant such digit. If isNegative is true, then the array is interpretted as being in two's complement notation (effectively having an infinite number of leading 1 bits).
~this()
In a version(Secure build only, the destructor wipes the memory which was used to store this Int's value. This is because big integers are often used for cryptographic purposes for which it would be unwise to leave values hanging around in memory. In non-Secure versions, this class has no destructor.
char[] toString()
Returns a string containing this Int's value in decimal
char[] toHexString()
Returns a string containing this Int's value in hexadecimal, with an underscore character separating each group of eight digits.
int toInt()
Returns the value of this Int cast as an int. If the value is too wide to be stored in an int then one of the values int.max or int.min will be returned, according to whether the number is positive or negative.
uint toUint()
Returns the value of this Int cast as an uint. If the value is too wide to be stored in an uint, or is negative, then the value uint.max will be returned.
long toLong()
Returns the value of this Int cast as a long. If the value is too wide to be stored in a long then one of the values long.max or long.min will be returned, according to whether the number is positive or negative.
ulong toUlong()
Returns the value of this Int cast as a ulong. If the value is too wide to be stored in a ulong, or is negative, then the value ulong.max will be returned.
ulong toFloat()
Returns the value of this Int cast as a float.
ulong toDouble()
Returns the value of this Int cast as a double.
ulong toReal()
Returns the value of this Int cast as a real.
bool isInt()
Returns true if the value of this Int can be stored in an int without truncation, false otherwise.
bool isUint()
Returns true if the value of this Int can be stored in a uint without truncation, false otherwise.
bool isLong()
Returns true if the value of this Int can be stored in a long without truncation, false otherwise.
bool isUlong()
Returns true if the value of this Int can be stored in a ulong without truncation, false otherwise.
int opEquals(Object n)
int opEquals(int n)
int opEquals(uint n)
The == operator
int opCmp(Object n)
int opCmp(int n)
int opCmp(uint n)
The remaining comparison operators
Int opAdd(Int n)
Int opAdd(int n)
Int opAdd(uint n)
The + operator
Int opSub(Int n)
Int opSub(int n)
Int opSub(uint n)
Int opSub_r(int n)
Int opSub_r(uint n)
The binary - operator
Int opNeg()
The unary - operator
Int opMul(Int n)
Int opMul(int n)
Int opMul(uint n)
The binary * operator
Int opDiv(Int n)
Int opDiv(int n)
Int opDiv(uint n)
Int opDiv_r(int n)
Int opDiv_r(uint n)
The / operator. Throws an IntException if this is zero.
Int opMod(Int n)
Int opMod(int n)
Int opMod(uint n)
Int opMod_r(int n)
Int opMod_r(uint n)
The % operator. Throws an IntException if this is zero.
Int opAnd(Int n)
Int opAnd(int n)
uint opAnd(uint n)
The binary & operator. Note that and-ing with a uint will in fact return a uint. This means that it is more efficient to write, for example (x & 1u), where x is an Int, than it is to write (x & 1).
Int opOr(Int n)
Int opOr(int n)
Int opOr(uint n)
The | operator
Int opXor(Int n)
Int opXor(int n)
Int opXor(uint n)
The ^ operator
Int opCom()
The unary ~ operator
Int opShl(Int n)
Int opShl(int n)
Int opShl(uint n)
Int opShl_r(int n)
Int opShl_r(uint n)
The << operator. Throws an IntException if the result is too big to fit in an Int(!) That is, if such an Int would have been way too big to actually fit on your computer.
Int opShr(Int n)
Int opShr(int n)
Int opShr(uint n)
Int opShr_r(int n)
Int opShr_r(uint n)
The >> operator
Int opUShr(Int n)
Int opUShr(int n)
Int opUShr(uint n)
Int opUShr_r(int n)
Int opUShr_r(uint n)
The >>> operator. Throws an IntException if this is negative and n is positive.
uint end()
The number of uints required to store this value internally (excluding the sign). See also opIndex and opSlice
uint opIndex(int index)
The read version of the [] operator. Note that the write version is purposefully not overloaded, and should never be, for the same reason that the assignment operators are not overloaded. See also opSlice
uint[] opSlice(int i, int j)
The [..] operator. Conceptually, a big integer can be thought of an infinitely large array of uints, with each uint representing a radix 232 digit of the big integer's representation. Index zero is the least significant digit. These functions allow you to read (but not write) that conceptual array. Note that for every index greater than or equal to end, the value of the corresponding conceptual element will always be zero (for positive numbers) or 0xFFFFFFFF (for negative numbers). Note that a big integer has no length property, since the conceptual array is infinitely large.
char[] format(uint radix, uint minWidth, uint groupWidth, bool leadingZeroes, SignMode signMode)
A more fully-featured alternative to toString()
bool equalsZero()
Fast test for zero. Returns true if the value of this Int equals zero, false otherwise
bool positive()
Fast test for positives. Returns true if the value of this Int is greater than zero, false otherwise
bool negative()
Fast test for negatives. Returns true if the value of this Int is less than zero, false otherwise
int sign()
Another fast test for negatives! Gets the sign of the number. Returns -1 if the value of this Int is less than zero, 0 otherwise
Int changeSign()
This is not the same thing as negate! Returns an Int having the same radix 232 digits as this, but whose interpretation is that of the complementary sign. In effect, you are returning an Int in which you leave digits [0..end] unchanged, but complement digits [end..∞].

Supporting functions

Int abs(Int x)
Returns the absolute magnitude of x
int sgn(Int x)
Returns -1 if x is negative, 0 if x is zero, or 1 if x is positive,
bit bitTest(Int x, uint n)
Returns 1 if bit n of x is set, 0 otherwise.
Int bitSet(Int x, uint n)
Returns an Int whose value is (x | (1<<n)). This does not modify in place, since Ints are immutable.
Int bitClear(Int x, uint n)
Returns an Int whose value is (x & ~(1<<n)). This does not modify in place, since Ints are immutable.
uint ge2(Int x)
uint ge2(int x)
uint ge2(uint x)
Returns the greatest exponent of 2 by which x may be divided before it becomes odd. Equivalently, returns the number of trailing zero bits in the binary representation of x. Throws an IntException if x is zero.
uint log2(Int x)
uint log2(int x)
uint log2(uint x)
Returns the integer base 2 logarithm of x. Equivalently, returns the number of significant bits in the binary representation of x. Throws an IntException if x is zero or negative.
Int pow2(int x)
Returns 1 << x (or, equivalently, 2x). Throws an IntException if x is negative.
bool isPow2(Int x)
bool isPow2(int x)
bool isPow2(uint x)
Returns true if x is an exact power of two, false otherwise.
uint countOnes(Int x)
uint countOnes(int x)
uint countOnes(uint x)
Returns the total number of 1 bits in the binary representation of x. Throws an IntException if x is negative.
Int shlWhole(Int x, uint y)
Int shlWhole(int x, uint y)
Returns x shifted left by y whole uints. That is, returns (x << (32*y)), or, equivalently, (232)yx
Int shrWhole(Int x, uint y)
Returns x shifted right by y whole uints. That is, returns (x >> (32*y)), or, equivalently, (2-32)yx
Int lowWhole(Int x, uint y)
Returns the y low order uints of x. That is, returns (x & ((1 << (32*y))-1)), or, equivalently, x mod (232)y
Int divMod(Int x, Int y, out Int r)
Int divMod(Int x, Int y, out Int r, Int.Round mode)
Returns x/y and x%y both at the same time. Throws an IntException if x is zero.

High level functions

Int sqrt(Int x)
Int sqrt(Int x, out Int r)
Returns the integer square root of x. The second version also returns the remainder. Throws an IntException if x is negative.
bool isSquare(Int x)
Returns true if x is a perfect square, false otherwise.
Int pow(Int x, Int y)
Returns xy
Int modMul(Int x, Int y, Int m)
Returns xy mod m
Int modPow(Int x, Int y, Int m)
Returns xy mod m
Int modInv(Int x, Int m)
Returns x-1 mod m. Throws an IntException if x and y are not coprime (that is, if gcd(x, y) is not equal to one).
Int modInvPrime(Int x, Int p)
Returns x-1 mod p. This is a faster version of modInv, but it only works if the modulus is prime. This function will exhibit undefined behavior if p is not prime.
Int lcm(Int a, Int b)
Returns the lowest common multiple (aka lowest common denominator) of a and b
Int gcd(Int a, Int b)
Int gcd(Int a, Int b, out Int x, out Int y)
Returns the greatest common divisor of a and b. The second version also returns x and y such that a*x + b*y == gcd(a,b)
Int factorial(Int n)
Int factorial(int n)
Returns the product of all integers in the range 1..n. Throws an IntException if x is negative or if the result is too big to fit in an Int(!) That is, if such an Int would have been way too big to actually fit on your computer.
int isProbablyPrime(Int p)
int isProbablyPrime(Int p, uint attempts)
Returns 0 if p is definitely composite; 2 if p is definitely prime, or 1 if p is very probably prime. The second parameter represents a required confidence level: the higher the number, the more confident you can be that the number is prime, It is the number of attempts which the algorithm will make to determine primality. If attempts is omitted, it defaults to ten. Note that an exact test for primality will be made if p is small enough to fit into a uint
Int getProbablePrimeLess(Int n)
Int getProbablePrimeLess(Int n, uint attempts)
Returns the greatest probable prime which is less than n. An IntException will be thrown if n is zero, one or two.
Int getProbablePrimeLessEqual(Int n)
Int getProbablePrimeLessEqual(Int n, uint attempts)
Returns the greatest probable prime which is less than or equal to n. An IntException will be thrown if n is zero or one.
Int getProbablePrimeGreater(Int n)
Int getProbablePrimeGreater(Int n, uint attempts)
Returns the smallest probable prime which is greater than n.
Int getProbablePrimeGreaterEqual(Int n)
Int getProbablePrimeGreaterEqual(Int n, uint attempts)
Returns the smallest probable prime which is greater than or equal to n.
int jacobi(Int a, Int n)
Returns the value of the Jacobi symbol (a / b).

Low level functions

These functions neither operate on, nor return, Ints. Instead, they operate on arrays of uints representing unsigned big integers, least significant digit first, and are capable of performing operations in-place. These functions are called using pointers, and it is the caller's responsibility to ensure that sufficient space is reserved for the output. These functions are written partly in assembler, for speed.

int log2Exact(uint x)
Returns log2(x) if x is an exact power of two, -1 otherwise
char[] bigintToString(uint[] x, uint radix, uint groupWidth)
dchar[] bigintToString(uint[] x, uint radix, dchar[] digits, uint groupWidth, dchar groupChar)
Construct a string containing a string representation of x. digits is a string containing the characters which represent digits (from zero upward). groupChar is the character which will be used to separate groups of digits.
uint[] bigintFromString(char[] s, uint radix)
uint[] bigintFromString(dchar[] s, uint radix, dchar[] digits, dchar groupChar)
Create a big integer array from a string. digits is a string containing the characters which represent digits (from zero upward). It is assumed that the character groupChar is used to separate groups of digits, and conseqently this character will be ignored.
uint[] bigintToRadix(uint[] x, uint radix)
Convert a big integer array to an arbitrary radix. The output array will be least-significant-digit first, and will contain numeric values (0, 1, ...), not characters ('0', '1', ...). This allows you to use radices well above sixteen.
uint[] bigintFromRadix(uint[] x, uint radix)
Create a big integer array from an arbitrary radix. The input array must be least-significant-digit first, and must contain numeric values (0, 1, ...), not characters ('0', '1', ...). This allows you to use radices well above sixteen.
uint bigintLLAdd(uint* d, uint* x, uint* y, uint len)
uint bigintLLAdd(uint* d, uint* x, uint xLen, uint* y, uint yLen)
d = x + y. You are required to reserve len uints (first version), or max(xLen, yLen) uints (second version) for the output. d. The return value is the propogated carry.
void bigintLLAnd(uint* d, uint* x, uint* y, uint len)
d = x & y. You are required to reserve len uints for the output d.
void bigintLLAssign(uint* d, uint* x, uint len)
d = x. You are required to reserve len uints for the output d.
int bigintLLCmp(uint* x, uint* y, uint len)
int bigintLLCmp(uint* x, uint xLen, uint* y, uint yLen)
Compare x with y. Returns -1 if x < y, 0 if x == y or 1 if x > y
int bigintLLCmpAll(uint x, uint* y, uint len)
int bigintLLCmpAll(uint* x, uint y, uint yLen)
Compare all uints of x with the single value y (or vice versa). Returns -1 if x < y, 0 if x == y or 1 if x > y. The constant value must be 0 (all 0 bits) or 0xFFFFFFFF (all 1 bits).
void bigintLLCom(uint* d, uint* x, uint len)
d = ~x. You are required to reserve len uints for the output d.
uint bigintLLDec(uint* d, uint* x, uint carry, uint len)
uint bigintLLDecV(uint* d, uint* x, uint y, uint carry, uint len)
d = x - carry. The second version also subtracts y from every uint of x (y must be 0 or 0xFFFFFFFF). You are required to reserve len uints for the output d. The return value is the propogated carry.
uint bigintLLDiv(uint* d, uint* x, uint k, uint len)
d = x / k (scalar division). You are required to reserve len uints for the output d. The return value is the propogated carry (which in fact equals the remainder).
bool bigintLLEquals(uint* x, uint* y, uint len)
Returns true if x == y, false otherwise.
bool bigintLLEqualsZero(uint* x, uint len)
Returns true if x == 0, false otherwise.
uint bigintLLCountOnes(uint* x, uint len)
Returns the number of 1 bits in x.
uint bigintLLInc(uint* d, uint* x, uint carry, uint len)
uint bigintLLIncV(uint* d, uint* x, uint y, uint carry, uint len)
d = x + carry. The second version also adds y to every uint of x (y must be 0 or 0xFFFFFFFF). You are required to reserve len uints for the output d. The return value is the propogated carry.
uint bigintLLMinimize(uint* x, uint len)
Returns the length of x ignoring leading zeroes
uint bigintLLMinimizeV(uint* x, uint y, uint len)
Returns the length of x ignoring leading uints equal to y (y must be 0 or 0xFFFFFFFF)
uint bigintLLMul(uint* d, uint* x, uint k, uint len)
d = x * k (scalar multiplication). You are required to reserve len uints for the output d. The return value is the propogated carry.
uint bigintLLNeg(uint* d, uint* x, uint len)
d = -x You are required to reserve len uints for the output.d. The return value is the propogated carry (which will always be 1 unless x was zero)
void bigintLLOr(uint* d, uint* x, uint* y, uint len)
d = x | y. You are required to reserve len uints for the output d.
uint bigintLLShl(uint* d, uint* x, uint* y, uint len)
d = x << y. You are required to reserve len uints for the output d. The return value is the propogated carry.
uint bigintLLShr(uint* d, uint* x, uint* y, uint len)
d = x >> y. You are required to reserve len uints for the output d. The return value is the propogated carry (in the high order bits).
uint bigintLLSub(uint* d, uint* x, uint* y, uint len)
uint bigintLLSub(uint* d, uint* x, uint xLen, uint* y, uint yLen)
d = x - y. You are required to reserve len uints (first version), or max(xLen, yLen) uints (second version) for the output. d. The return value is the propogated carry.
void bigintLLXor(uint* d, uint* x, uint* y, uint len)
d = x ^ y. You are required to reserve len uints for the output d.
void bigintLLZero(uint* d, uint len)
d = 0. You are required to reserve len uints for the output d.
void bigintDivMod(uint* q, uint qLen, uint* r, uint rLen, uint* x, uint xLen, uint* y, uint yLen)
q = x / y; r = x % y. You are required to reserve qLen >= (xLen - yLen + 1) uints for the output q, and rLen >= yLen uints for the output r.
void bigintMul(uint* d, uint dLen, uint* x, uint xLen, uint* y, uint yLen)
d = x * y. You are required to reserve dLen >= (xLen + yLen) uints for the output d.
void bigintSquare(uint* d, uint dLen, uint* x, uint xLen)
d = x * x. You are required to reserve dLen >= (2 * xLen) uints for the output d.

Versions

Since the etc.bigint package is supplied in source code form, it is possible to build different versions of it. In addition to simple debug and release builds, defining the following versions will create different builds, as follows:

Secure
Useful for cryptographic purposes. In a Secure build, all temporary results are overwritten with zero before being freed. This includes the destructor of the Int class itself (which will run when the garbage collector decides is appropriate).
Paranoid
Enables some extremely over-the-top tests for robustness, but likely to slow things down considerably.
DisableMontgomery
Montgomery reduction is an algorithm which speeds up modPow. It is used by default whenever the exponent is odd. Defining DisableMontgomery prevents this algorithm from being used (in fact, it won't even get compiled in). May be useful for testing.
DisableBarratt
Barrett reduction is another algorithm which speeds up modPow. It is almost as fast as Montgomery (but not quite). It is used by default whenever Montgomery can't be used (for example when the exponent is even). Defining DisableBarrett prevents this algorithm from being used (in fact, it won't even get compiled in). May be useful for testing.
DisableKaratsuba
The Karatsuba-Offman method is an algorithm which speeds up multiplication - but only for very large numbers. Defining DisableBarrett prevents this algorithm from being used (in fact, it won't even get compiled in). May be useful for testing.
DisableSquare
By default, an optimized algorithm is used for squaring. Defining DisableSquare prevents this algorithm from being used (in fact, it won't even get compiled in). May be useful for testing.

To do (future work)

Future work on etc.bigint

  • More parts of the lowlevel routines could be recoded in assembler to speed things up further.
  • The constructors which take float, double and real should really be taking advantage of knowledge of IEEE float formats. (version(X86) only?)
  • We could do with nth-root and is-perfect-power algorithms.
  • Primality test could use Rabin-Miller algorithm instead of / as well as the current (Legendre) algorithm.

Arcane Jill


Copyright (c) 2004 by Arcane Jill. All Rights Reserved