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