It is known, a computer can operate numbers with a limited number of bits. As a rule, we are accustomed to work with the 32-bit and 64-bit integers. On the .Net platform, the Int32 (int) and Int64 (long) types correspond to these integers.

But what to do if we need to represent, for instance, number *29! = 8841761993739701954543616000000?* Such number won’t fit both 32-bit and 64-bit data types. Long arithmetic is designed specifically for working with such big numbers.

In computing technology, long arithmetic implies operations (addition, multiplication, subtraction, division, raising to a power etc.) with numbers, the bitness of which exceeds the length word of the given computer. These operations are implemented not by hardware but by software with the help of basic hardware for working with small-order numbers.

Long arithmetic can be also considered as one of the divisions of competitive programming since the bitness of standard types is quite often insufficient for representation of eventual result during problem solving. When choosing a programming language for the purposes of competitive programming, a set of tools (predefined libraries, implemented classed) built into the language, plays a pretty important role. Many languages (Java, Ruby, Python) have in-built support for long arithmetic that can drastically minimize time spent on writing a program.

Up to version 4.0, the .Net platform did not have the in-built support for working with long numbers. The .Net 4.0 platform supports both long and complex numbers. This functionality is available through the * System.Numerics* assembly and the

*and*

**BigInteger***types defined in the namespace with the same name as the assembly.*

**Complex**The * BigInteger* structure was supposed to be included into .Net 3.5, but at that moment, it was not quite ready, and its implementation did not correspond to all the needs (performance problems were another factor). That’s why it was decided to postpone its release till .Net 4.0.

In this article, I would like to consider the details of the long arithmetic implementation from Microsoft.

### General terms

The concept of the long numbers representation in computer memory is pretty straightforward. Let’s consider number *123456789* in decimal arithmetic. Obviously, it can be represented in the following way:

123456789_{10} = 1*10^{8} + 2*10^{7} + 3*10^{6} + 4*10^{5} + 5*10^{4} + 6*10^{3} + 7*10^{2} + 8*10^{1} + 9*10^{0}

Generally, any number can be represented as:

**A = a**_{n-1}**β**^{n-1}** + a**_{n-2}**β**^{n-2}** +…+a**_{1}**β + a**_{0}

where *β* – a numeric base, in which we represent the number, and the *a*_{i} coefficients satisfy the two-sided inequality *0 ≤ a*_{i}* < β*.

The number representation resembles the polynomial representation, but instead of *x* raised to the corresponding power, we have the *β* base raised to the required power. As it is known, polynomial *a*_{0}* + a*_{1}*x + a*_{2}*x*^{2}* + … + a*_{n}*x*^{n} can be conveniently represented as an array, elements of which represent coefficients *a*_{i} and *а*, and index *i* defines the corresponding power of x. A long number is stored is the same way. The only thing left is to take a decision on the *β* base selection.

For instance, the same number 123456789 can be represented in decimal numeration *(β = 10*^{4}*)* system in the following way:

123456789_{10} = 1*(10^{4})^{2} + 2345*(10^{4})^{1} + 6789*(10^{4})^{0}

Representing number *123456789* in decimal numeration system gives us two benefits. First, we minimize the memory size consumed since instead of a 9-number array, it is enough to store a 3-number array (*1, 2345* and *6789*). Secondly, we considerably minimize the execution time for standard operations with long numbers, because 4-digit orders are processed simultaneously. In general, computer equally adds both one-figure numbers and 32-bit numbers, and therefore, it’s worth using it.

Usually, base *β *of a numeration system depends on a maximal size of base data type on a computer, and it is selected on the assumption of the following observations:

- Base must fit one of base data types;
- Base must be maximally large to decrease the size of a long number representation and increase the speed of operations with them, but at the same time small enough to ensure that all operations with coefficients use the base data type;
- For convenient output and debugging,
*β*can be selected as a power of 10,*β*as a power of 2 allows performing low-level high-speed operations.

It is also worth mentioning that the number sign is covered by a separate variable, i.e. array contains the long number module, and the number is stored backward. It is made primarily for convenience: there is no need in processing null/last element of the array, in which the number sign could be stored, as well as all operations are executed in the ‘from junior to senior bits’ order.

#### BigInteger from Microsoft

If we take a look at the * BigInteger* structure through the

*Reflector*or

*dotPeek*decompiler, we will notice the following fields:

1 2 3 4 5 6 7 8 9 10 11 12 |
private static readonly BigInteger s_bnMinInt = new BigInteger(-1, new uint[1]{ (uint) int.MinValue }); private static readonly BigInteger s_bnOneInt = new BigInteger(1); private static readonly BigInteger s_bnZeroInt = new BigInteger(0); private static readonly BigInteger s_bnMinusOneInt = new BigInteger(-1); internal int _sign; internal uint[] _bits; private const int knMaskHighBit = -2147483648; private const uint kuMaskHighBit = 2147483648U; private const int kcbitUint = 32; private const int kcbitUlong = 64; private const int DecimalScaleFactorMask = 16711680; private const int DecimalSignMask = -2147483648; |

The structure contains only two instance fields (*_sign* and *_bits*). The rest of fields are constants and static fields for reading that provide structure values for numbers *-1*, *0* and *1*.

We can assume that the *_sign* variable stores number sign, and the* **_bits* array contains the *a*_{i} coefficients. Taking into account that the* **_bits* array is of the *uint[]* type, we can suggest that the power of two 2^{32} is taken as a *β *base (since *uint* is a 32-bit unsigned number).

So, let’s try to prove or disprove our suggestions.

A constructor taking *int* as an argument looks in the following way:

1 2 3 4 5 6 7 8 9 10 11 12 |
public BigInteger(int value) { if (value == int.MinValue) { this = BigInteger.s_bnMinInt; } else { this._sign = value; this._bits = (uint[]) null; } } |

Its implementation can tell a bit more about the role of the *_sign* variable. As we can see, if a long number fits the int range (from *-2*^{3}^{1} to *2*^{31}*-1*), it is stored in the *_sign *variable. And the *_bits* array is not used at all and is equal to null. This optimization should speed up the work of the * BigInteger* type as well as decrease the size of consumed memory when the number, in fact, is not large.

A constructor taking *unit* as an argument looks in the following way:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
public BigInteger(uint value) { if (value <= (uint) int.MaxValue) { this._sign = (int) value; this._bits = (uint[]) null; } else { this._sign = 1; this._bits = new uint[1]; this._bits[0] = value; } } |

Depending on whether the number fits the range or it does not, it is written into either the* _sign* variable, or into the *_bits* array.

The next constructor taking the 64-bit number with a sign (long) helps to answer the question on the choice of numeric base:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 |
public BigInteger(long value) { if ((long) int.MinValue <= value && value <= (long) int.MaxValue) { if (value == (long) int.MinValue) { this = BigInteger.s_bnMinInt; } else { this._sign = (int) value; this._bits = (uint[]) null; } } else { ulong num; if (value < 0L) { num = (ulong) -value; this._sign = -1; } else { num = (ulong) value; this._sign = 1; } this._bits = new uint[2]; this._bits[0] = (uint) num; this._bits[1] = (uint) (num >> 32); } } |

If a number does not fit the *int* range, the *_sign* variable, as we see, contains the number sign (*-1* – for negative, and *1* – for positive), and the *_bits* array contains the same *a*_{i} coefficients* *and is filled in the following way:

1 2 3 |
this._bits = new uint[2]; this._bits[0] = (uint) num; this._bits[1] = (uint) (num >> 32); |

In this case, the 64-bit *num* number is divided into two 32-bit numbers (*uint)num и (uint)(num >> 32*). The first number is the last 32 bits of the *num* number, whereas the second number represents the first 32 bits (right shift at** ***n* bits matches the integer division by *2*^{n}).

Let’s define how the *long.MaxValue = 2*^{63}*-1 = 9223372036854775807* number will be stored in the * BigInteger* structure. For this, let’s divide it by 2

^{32}:

In fact, *(uint)long.MaxValue = 4294967295, (uint)(long.MaxValue >> 32) = 2147483647*.

Therefore, *9223372036854775807 = 2147483647*(2*^{32}*)*^{1}* + 4294967295*(2*^{32}*)*^{0}, and * BigInteger *will be represented by a pair:

**_sign = 1
_bits = {4294967295, 2147483647} // keep in mind that the number is stored backwards**

For the long number *-1234567891011121314151617181920*, we have:

That is, the number is expanded in powers of 2^{32} in the following way:

*1234567891011121314151617181920 = 15*(2 ^{32})^{3} + 2501550035*(2^{32})^{2} + 3243814879*(2^{32})^{1} + 4035623136*(2^{32})^{0} *

Therefore, * BigInteger* will be represented by a pair:

**_sign = -1 // number sign**

** _bits = {4035623136, 3243814879, 2501550035, 15}**

The number that fits the *int* range, let’s say 17, will be stored in the following way:

**_sign = 17
_bits = null**

Having studied the * BigInteger* constructors and structures, we can conclude the following:

- If a number fits the
*int*range, it is stored in the*_sign*variable; - If a number does not fit the int range, its sign is stored in the
*_sign*variable (*-1*for a negative number, and*1*for a positive number), and the*_bits*array stores the*a*_{i}coefficients of the long number expansion with base*2*^{3}^{2}.

The *β = 2*^{32 }base is a good choice since it is easier to work with the power of two on the low level (multiplication and division by the power of two correspond to the bit left and right shifts), as well as allows to quickly perform operations with them.

In general, the * BigInteger* structure is a full-featured implementation of the long arithmetic on the .Net platform. In addition, Microsoft tried to bring it maximally closer to primitive numeric types: a

*instance can be used in the same way as any other integer type.*

**BigInteger***reloads standard numeric operations for execution of basic mathematical operations, such as addition, subtraction, division, multiplication, subtractions, negation, and unary negation. We can also use standard numeric operators for comparing two*

**BigInteger**

**BigInteger***values with each other. Similarly to other integer types,*

*supports bit operators:*

**BigInteger***And*,

*Or*,

*XOR*,

*left shift*,

*right shift*.

For languages that do not support the user-defined operators, the * BigInteger* structure also provides equivalent methods for execution of mathematical operations. It refers to methods

*dd, Divide, Multiply, Negate, Subtract*, and some other methods. Microsoft treated the implementation of the

*structure in the same way.*

**Decimal**Many members of the * BigInteger* structure directly correspond to members of other integer types. Besides,

*adds such elements as:*

**BigInteger**- IsEven – defines whether a number is even;
- IsPowerOfTwo — defines whether a number is a power of two;
- Sign — returns a value that specifies the BigInteger sign number;
- Abs — returns the absolute value of the BigIneger number;
- DivRem — returns quotient and remainder after division operation;
- GreatestCommonDivisor — returns the largest common divisor for two numbers;
- Log — returns logarithm of the specified number in a numeration system with specified base;
- Max/Min — returns the largest/smallest of two numbers;
- ModPow — executes modular division of a number that is raised to power of another number;
- Pow — raises the BigInteger value to the specified power.

### Few words on BigInteger in Mono and Java

It is notable that Mono also supports long arithmetic. Implementation of the * BigInteger* structure in Mono is practically the same as in Microsoft, except for the absence of optimization of numbers represented by the

*int*type.

That is, number *17* in Mono will by represented by the following pair:

**_sign = 1 // ****number sign**

_bits = {17}

* BigInteger* is implemented in Java in the similar way:

1 2 3 4 5 6 7 8 9 10 11 |
public class BigInteger extends Number implements Comparable<BigInteger> { int signum; int[] mag; private int bitCount = -1; private int bitLength = -1; private int lowestSetBit = -2; private int firstNonzeroByteNum = -2; private int firstNonzeroIntNum = -2; private final static long LONG_MASK = 0xffffffffL; } |

Since there are no unsigned types in Java, the *ma**g* array is of the *int[]* type. Therefore, representation of a long number in Java and .Net differ. In .Net, the representation will be more effective, since the unit type covers bigger range:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
private BigInteger(long val) { if (val < 0) { signum = -1; val = -val; } else { signum = 1; } int highWord = (int)(val >>> 32); if (highWord == 0) { mag = new int[1]; mag[0] = (int)val; } else { mag = new int[2]; mag[0] = highWord; mag[1] = (int)val; } } |

Java as well as Mono does not have optimization for numbers represented by the *int* type.

### BigInteger Productivity

When you work with the * BigInteger* long numbers, you should bear in mind possible productivity-related problems. For example, a seemingly harmless

*++*operator may considerably affect productivity:

1 2 3 4 5 6 7 8 |
int length = 1000000; BigInteger num = BigInteger.Parse("12345678910111213141516171819"); for (int i = 2; i < length; i++) { if (IsPrime(i)) num++; } Console.WriteLine(num); |

Though it seems that the value change takes place in the given example, it is not the case. The * BigInteger* objects are immutable, i.e. in fact, common language runtime internally creates a new

*object and assigns a value to it that is a unit bigger than the previous one.*

**BigInteger**In the given example, we can proceed in the following way: execute intermediate operations with the normal number types, and then use * BigInteger*:

1 2 3 4 5 6 7 8 9 10 |
int length = 1000000; BigInteger num = BigInteger.Parse("12345678910111213141516171819"); int temp = 0; for (int i = 2; i < length; i++) { if (IsPrime(i)) temp++; } num += temp; Console.WriteLine(num); |

Other .NET Framework number types are immutable as well. However, since the * BigInteger* types do not have upper or lower bounds, its values may increase to very large values and have a measurable impact on productivity.

### Instead of conclusion

As from version 4, .Net includes the full-featured implementation of integer-valued long arithmetic. The only thing it lacks is, probably, implementation of the * BigRational* structure that has been present in .

*Net BCL*in beta state for a long time.

The description of the * BigRational* structure: the

*structure is based on the BigInteger that was introduced in .Net Framework 4 and allows creating arbitrary-precision rational numbers. A rational number is a ratio between two integers, and in this implementation of the*

**BigRational***structure, the*

**BigRational***is used as the numerator and denominator.*

**BigInteger**### Timur Guev

#### Latest posts by Timur Guev (see all)

- Sorting in .NET - February 22, 2017
- Aspects of Strings in .NET - February 17, 2017
- StringBuilder: the Past and the Future - February 13, 2017