The largest integer that can be represented using the built-in .NET types
is 296-1, using the Decimal type.
Many applications, like cryptography, require much larger numbers.
The Extreme Optimization Mathematics Library for .NET provides
a type that can represent integers with over 20 billion decimal digits.
In practice, the size of numbers is limited by available memory.
Constructing big integers
The BigInteger
structure has seven constructors. Six of these construct a big integer from a built-in type.
The one parameter can be a signed or unsigned 32 or 64 bit integer, a
Decimal, or a
Double.
| C# |  Copy |
|---|
BigInteger a = new BigInteger(12345);
BigInteger b = new BigInteger(9876543210L);
BigInteger c = new BigInteger(9876543210123456789m);
BigInteger d = new BigInteger(1e+100);
|
| Visual Basic | Copy |
|---|
Dim a As New BigInteger(12345);
Dim b As New BigInteger(9876543210L);
Dim c As New BigInteger(9876543210123456789m);
Dim d As New BigInteger(1e+100);
|
The final constructor takes two arguments. The first is an integer that specifies the sign.
The sign of this number is copied to the new value. A value of zero results in zero.
The second argument is a
Byte
array that contains the bits of the number. The value at index zero is the least significant
byte.
| C# | Copy |
|---|
byte[] bytes = { 0x01, 0x03, 0xdd, 0xcf, 0xe6, 0x82, 0xc3, 0x20, 0x0d, 0x75, 0x06, 0x12 };
BigInteger e = new BigInteger(+1, bytes);
|
| Visual Basic | Copy |
|---|
Dim bytes As Byte() = { 0x01, 0x03, 0xdd, 0xcf, 0xe6, 0x82, 0xc3, 0x20, 0x0d, 0x75, 0x06, 0x12 }
Dim e As new BigInteger(+1, bytes)
|
Big integers can also be created from a text string, using the
Parse(String)
or TryParse(String, BigInteger%)
method, by casting from one of the built-in numerical types, or by
calling one of the static functions. All these options are further discussed below.
Constants
The BigInteger structure
provides several constants for commonly used and special big integers. These are listed
in the following table:
Working with big integers
You can work with big integers like you would any built-in integer type.
Like strings, big integers are immutable.
Arithmetic operations
The Extreme Optimization Mathematics Library for .NET provides methods for all basic arithmetic operators
on big integers. Many have special versions for cases where one of the operands is a built-in integer type. Overloaded versions of
the arithmetic operators are provided for languages that support them. For languages that don't support operator
overloading, equivalent static (Shared in Visual Basic) methods are supplied.
For example:
| C# | Copy |
|---|
BigInteger a = BigInteger.Parse("650984076498398479473");
BigInteger b = BigInteger.Parse("49739876698723097627652");
BigInteger c = 2 - 3 * (a + b);
|
| Visual Basic | Copy |
|---|
Dim a As BigInteger = BigInteger.Parse("650984076498398479473")
Dim b As BigInteger = BigInteger.Parse("49739876698723097627652")
Dim c As BigInteger = 2 - 3 * (a + b)
|
The table below lists the operators and there equivalents.
Big integer operators and their static (Shared) method equivalents
| Operator |
Static method equivalent |
Description |
|
+n
|
(no equivalent) |
Returns the big integer n. |
|
-n
|
Negate(BigInteger)
|
Returns the negation of the big integer n. |
|
n1 + n2
|
BigInteger.Add(n1, n2)
|
Adds the big integers n1 and n2. |
|
n1 - n2
|
BigInteger.Subtract(n1, n2)
|
Subtracts the big integers n1 and n2. |
|
n1 * n2
|
BigInteger.Multiply(n1, n2)
|
Multiplies the big integers n1 and n2. |
|
n * i
|
BigInteger.Multiply(i, a)
|
Multiplies the big integer n and the 32 bit integer i. |
|
i * n
|
BigInteger.Multiply(i, n)
|
Multiplies the 32 bit integer i and the big integer n. |
|
n1 / n2
|
BigInteger.Divide(n1, n2)
|
Divides the big integer n1 by n2. |
|
n1 % n2
|
BigInteger.Modulus(n1, n2)
|
Returns the remainder after dividing the big integer n1
by n2. |
| (no equivalent) |
BigInteger.DivRem(n1, n2, out r)
|
Divides the big integer n1 by n2
returning the remainder in r. |
|
n / i
|
BigInteger.Divide(n, i)
|
Divides the big integer n by the 32 bit integer i. |
|
n << i
|
BigInteger.LeftShift(n, i)
|
Shifts the big integer n to the left by
i bits. |
|
n >> i
|
BigInteger.RightShift(n, i)
|
Shifts the big integer n to the right by
i bits. |
In addition, the relational operators are also available. In a language
that does not support custom operators, the
Equals(BigInteger)
or CompareTo(BigInteger)
method can be used.
Modular arithmetic
In addition to the common arithmetic operations, the
BigInteger type supports
modular operations. Expressed mathematically, one can say that the result of a modular
operation is the remainder of the result of the original operation after division by
another integer, the modulus.
Most modular operations can be easily and efficiently expressed using this method.
Two operations require special attention. The modular inverse of a number is the unique
number that, when multiplied by the original modulo the same modulus, results in 1.
The ModularInverse(BigInteger, BigInteger)
method performs the calculation. It takes two parameters. The first is the number
to invert. The second is the modulus.
The modular inverse does not exist if the modulus is zero, or if the value
and the modulus have a common factor greater than one. An exceptiom is thrown
if this occurs.
Exponentiation is hopelessly inefficient using the simple method. The
ModularPow(BigInteger, BigInteger, BigInteger)
method uses a more efficient algorithm to perform this calculation.
It takes three parameters. The first is the base. The second is the exponent,
which can be a 32 bit integer or a large integer. The last parameter is the modulus.
The exponent can be negative. In this case, the modular inverse is raised
to the absolute value of the exponent. If the modular inverse does not exist,
an exception is thrown.
The example below computes 16 to the power M17-1 modulo M17, where M17 is the
17th Mersenne prime number (22281-1).
The result is equal to 1. It is impossible to compute this result using the naive
method.
| C# | Copy |
|---|
BigInteger M17 = BigInteger.Pow(2, 2281) - 1;
BigInteger result = BigInteger.ModularPow(17, M17 - 1, M17);
|
| Visual Basic | Copy |
|---|
Dim M17 As BigInteger = BigInteger.Pow(2, 2281) - 1
Dim result As BigInteger = BigInteger.ModularPow(17, M17 - 1, M17)
|
Other mathematical functions
To get an idea of the size of a big integer, use the
BitCount
property, which returns the total number of bits in a big integer. Alternatively, the
DecimalDigitCount
property returns an approximation of the number of decimal digits. It may be off by 1
for numbers that are close to a power of 10. Other numerical properties are listed in
the table below:
Numerical properties of big integers
| Property |
Description |
|
IsZero
|
Tests whether the number is zero. |
|
IsOne
|
Tests whether the number is equal to 1. |
|
IsEven
|
Tests whether the number is even. |
|
IsOdd
|
Tests whether the number is odd. |
|
IsPowerOfTwo
|
Tests whether the number is an exact power of two. |
The Abs(BigInteger)
method returns the absolute value of a big integer. The
Max(BigInteger, BigInteger) and
Min(BigInteger, BigInteger) methods
return the larger and smaller of two big integers, respectively. The
GreatestCommonDivisor(BigInteger, BigInteger)
method returns the greatest common divisor of two big integers, while the
LeastCommonMultiple(BigInteger, BigInteger)
returns the smallest number that is divided by two big integers.
The Sqrt(BigInteger)
method returns the integer part of the square root of a number. The
Pow(BigInteger, Int32)
method raises a number to a power, which can be a 32 bit integer or a big integer.
The Factorial(Int32)
method returns the factorial of an integer. All these methods are static
(Shared in Visual Basic).
Parsing and printing
BigInteger supports
the use of standard numeric format strings. Custom formats are not supported.
The following example reads in the estimated U.S. Gross Domestic Product (GDP)for
2008 and extrapolates the expected GDP for the year 5000 AD, assuming a
3 percent annual growth rate:
| C# | Copy |
|---|
BigInteger M17 = BigInteger.Pow(2, 2281) - 1;
BigInteger result = BigInteger.ModularPow(17, M17 - 1, M17);
|
| Visual Basic | Copy |
|---|
Dim M17 As BigInteger = BigInteger.Pow(2, 2281) - 1
Dim result As BigInteger = BigInteger.ModularPow(17, M17 - 1, M17)
|
This prints out:
Expected GDP in AD 5000: $3,667,012,204,198,739,456,889,107,416,336,411,935,057,640,625,467,885
Casts and conversions
Converting to big integers
The BigInteger type
supports implicit conversions from all integer types, both signed
and unsigned, including BigInteger.
Explicit conversions (casts) are available from all other numerical types.
When converting real or rational numbers, the result is rounded towards zero
by simply dropping the fractional part. Explicit conversions never throw an exception.
Converting from big integers
There are no implicit conversions from
BigInteger
to any of the built-in numerical types. For integral types, the explicit conversions return the
least significant bits that fit in the type. For example, the conversion to
a 32 bit unsigned integer contains the 32 least significant
bits of the original.
For the built-in floating-point types, Single
and Double, the converted value is
accurate to the first 24 or 64 bits, respectively.
If the number is too large to be represented in the floating-point type, then either
positive or negative infinity is returned.
Explicit conversions never throw an exception.
The big integer type also implements the
IConvertible interface.
The implementation is explicit. In order to call any of the conversion functions,
you first need to cast the original to the IConvertible
interface type.
Unlike type casts, calls to these conversion types do throw an
OverflowException
when the value is too large to fit in an integral type or
Decimal.