Arbitrary Precision Integers
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. Extreme Numerics.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.
BigInteger a = new BigInteger(12345);
BigInteger b = new BigInteger(9876543210L);
BigInteger c = new BigInteger(9876543210123456789m);
BigInteger d = 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.
byte[] bytes = { 0x01, 0x03, 0xdd, 0xcf, 0xe6, 0x82, 0xc3, 0x20, 0x0d, 0x75, 0x06, 0x12 };
BigInteger e = new BigInteger(+1, bytes);Big integers can also be created from a text string, using the Parse or TryParse 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:
Field | Description |
|---|---|
The number zero. | |
The number one. | |
The number minus one. | |
The smallest possible BigInteger value, equal to -268719476704. | |
The largest possible BigInteger value, equal to 268719476704. |
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
Extreme Numerics.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:
BigInteger f = BigInteger.Parse("650984076498398479473");
BigInteger g = BigInteger.Parse("49739876698723097627652");
BigInteger h = 2 - 3 * (f + g);The table below lists the operators and there equivalents.
Operator | Static method equivalent | Description |
|---|---|---|
+n | (no equivalent) | Returns the big integer n. |
-n | 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 or CompareTo 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 method performs the calculation. It takes two arguments. 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 exception is thrown if this occurs.
Exponentiation is hopelessly inefficient using the simple method. The ModularPow method uses a more efficient algorithm to perform this calculation. It takes three arguments. 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.
BigInteger M17 = BigInteger.Pow(2, 2281) - 1;
BigInteger result = 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:
Property | Description |
|---|---|
Tests whether the number is zero. | |
Tests whether the number is equal to 1. | |
Tests whether the number is even. | |
Tests whether the number is odd. | |
Tests whether the number is an exact power of two. |
The Abs method returns the absolute value of a big integer. The Max and Min methods return the larger and smaller of two big integers, respectively. The GreatestCommonDivisor method returns the greatest common divisor of two big integers, while the LeastCommonMultiple returns the smallest number that is divided by two big integers. The Sqrt method returns the integer part of the square root of a number. The Pow method raises a number to a power, which can be a 32 bit integer or a big integer. The Factorial 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:
BigInteger GDP = BigInteger.Parse("14300000000000");
BigInteger GDP5000 = GDP * BigInteger.Pow(103, 2992) / BigInteger.Pow(100, 2992);
Console.WriteLine("Expected GDP in AD 5000: {0:C}", GDP5000);This prints out (in en-us culture):
Expected GDP in AD 5000: $3,667,012,204,198,739,456,889,107,416,336,411,935,057,640,625,467,885Casts 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.