Let's code a Big Integer (part I)

Introduction

I like to solve programming contest problems once in a while, and sometimes, while working on it, I've been forced to switch from C++ to either Java or Python (and more recently to Haskell) to use the multi-precision integer support of those languages, a.k.a BigNums or BigIntegers. Both Python and Haskell have this feature in the very core of the language, meanwhile in Java you have to create an instance of the BigInteger class an invoke its operation methods in chain, thus creating some verbose expressions:

I've been always intrigued by how BigInt works; this gives me a excuse to delve around this topic, so I decided to craft my own C++ BigInt class to deal with this issue just for fun.

Approaches

As far as I've found, there are two approaches to implement BigInteger's (you may find out later that they are basically the same approach using different data types), the first approach uses an array of chars where each char represents a digit of the big number, for example, 30! = 265252859812191058636308480000000 would be represented as:

This approach is easy to understand/implement and is fine for time tightened competitions with loose memory constraints, but for a more general solution, is a waste of memory.

Consider that each char can represent up to 256 different values (if and only if sizeof char is 1) and this approach represents only one digit per char. There are a few tricks to make better use memory, like storing two digits per char instead of one and so on. Either way, this representation will waste memory, especially with longer streaks of digits, and efficiency in operations will be compromised because the bigger the memory we use, the longer the algorithms take to iterate over the data (duh!).

The second approach, more memory efficient, is the one used in the BigInteger Java class. It stores the bits that compose the number across an array of several ints, for example, the binary representation of 30! is:

30! = 110100010011111101100011011100001111100101101000011001011101111101011101110101010100000000000000000000000000

Those are 108 bits, every java integer occupies 32 bits, so the number can be split over 4 int values:

30! = [110100010011, 11110110001101110000111110010110, 10000110010111011111010111011101, 01010100000000000000000000000000]
= [3347, -164163690, -2040662563, 1409286144]

Or, if you chose to use unsigned integers as words instead:

= [3347, 4130803606, 2254304733, 1409286144]

As you can see, 30! can be held in an array of 4 32-bit int's (16 bytes) where the first element (element at 0) contains the most significant bits and the last element (element at size - 1) contains the least significant bits. On the other hand, the previous approach needed 33 bytes to store the number, a difference of 17 bytes. You can see in the following graph the difference in bytes of both techniques as the number grows in digits.

As you can see in the chart, calculating the factorial of something like 140000 (140000! has 659660 digits) requires around 70000 bytes for the first approach and 25000 for the second.

(The more clever of you will notice that both approaches are the same, both represent the number as a polynomial and the variable is char for the first and int for the second).

Construction

Constructing a BigInt from a String

Dissecting the algorithm that constructs a BigInt from a string that resides in one of the class constructors, we have the following steps, for base 10 numbers, the constructor basically operates as follows:

1. Check the sign character and skip the leading 0's from the number string.

2. Estimate a possible number of bits for the big number, this value is greater or equal than the real number of bits the number has, p.e., 30! has 108 bits, this step in the Java's BigInteger algorithm's will estimate 110 (110 >= 108).

   Why an approximated number of bits, why no calculate the exact number of bits? (See more...)

   Calculating the total bits of a base 10 integer requires doing the conversion of the whole number to binary, so this trick saves a lot of time as the exact number of bits is not needed beforehand.

   How can we do this? (See more...)

   The number of bits a 10 base digit number requires is:

   \[ log_{2}10 \times num digits = 3.32192809488736234789 \times num digits \]

   So the following code will do the calculation rounding up the resulting product.

   Wait! This operation can be done with integer arithmetic only, using some fixed point math tricks, multiplying 3.32192809488736234789 by a scale like 1024 you get 3401.65436916465904423936, rounding up to avoid underallocation you get 3402, then you take the product of a scaled number and a non scaled number and divide them by 1024 yielding the approximated value of 110.

3. Given the estimate number of bits, the next step calculates the number of required words needed to store the big number, p.e., To store 110 bits, 4 words are required. A very simple algorithm to do this calculation is:

   Just for fun, if you want to get rid of the conditional part you can also do:

   (See the explanation...)

   Two's complement does the trick in that last part ((~(remainingWords | -remainingWords)) & 1); as two's complement does not allow a double representation of zero (that is, there is only ONE zero in binary form, other binary signed number representations allow a double representation of ZERO, like one's complement that allows both +0 and -0), so the operation x | -x will be zero if and only if x = 0, the rest of the numbers will generate -1 (all bits on). The other binary operations ( ~(stuff) & 1 ) will take care of checking that if the value returned by x | x is 0 then the resulting value is 1.

4. Following step consist of splitting the number string in groups of N digits, where N is the number of base 10 digits that are guaranteed to fit into a 32-bit int, for base 10 this is N = 9. Why 9? Because the maximum decimal number with 9 digits is 999999999 has 30 bits and the maximum decimal number with 10 digits is 9999999999 and has 36 bits, the last one overflows.

   For our 30! example, this step returns 4.

5. For this step is important to remember that the first element (element at 0) in the array contains the most significant bits and the last element (element at size - 1) contains the least significant bits. Then, starting from the smaller group, convert the 9 digit string to an int, then multiply all the elements of the array by 10⁹ (starting from the last element) and carry the bits that overflow the result to the next array element (current index - 1).

   This can be visualized better with an example, remember that 30! was split in 4 strings: "265252", "859812191", "058636308" and "480000000", we start the process with the more significant digits, for this case "265252" is took as the starting group, it is multiplied by 10⁹ to open up space to add the following group of digits:

   265252 ✕ 109 = 265252000000000

   Now we add the following group of digits and repeat by scaling the result again with 10⁹

   265252000000000 + 859812191 = 265252859812191

   265252859812191 ✕ 109 = 265252859812191000000000 ...

   The following table resumes the four iteration loop that deals with all the groups:

   Current Bignum value	Bignum value after scaling by 109	Group to process	New Bignum value	Array value
   0	0	265252	265252	[0, 0, 0, 265252]
   265252	265252000000000	859812191	265252859812191	[0, 0, 61758, -25421473]
   265252859812191	265252859812191000000000	058636308	265252859812191058636308	[0, 14379, 1659331918, 396996116]
   265252859812191058636308	265252859812191058636308000000000	480000000	265252859812191058636308480000000	[3347, -164163690, -2040662563, 1409286144]

   Multiplying by 10⁹ opens up space (adds nine 0s) so we can add the new group to the current number using a simple add arithmetic. The array values can look odd because we are dealing with a huge decimal number split across several int's. The operation that multiplies all the array elements by 10⁹ takes care of the carry and then sums the new group element. This last operation is implemented in method destructiveMulAdd inside the java's BigInteger class.

   At array level, you can view the number as a polynomial where every array entry is a coefficient, then this operations works as follows:

   \[ a\left[0\right] + a\left[1\right].x + a\left[2\right].x^2 + ... + a\left[n-1\right].x^{n-1} \]

   Where x = 109. Scaling the number is a matter of multiplying the polynomial by 109:

   \[ \left(a\left[0\right] + a\left[1\right].x + a\left[2\right].x^2 + ... + a\left[n-1\right].x^{n-1}\right).10^9 \]

   With x = 109, there is a chance that the value of the coefficient overflows after scaling, so we have to use a temporal variable to carry the overflow of every local multiplication from the $kth$ element to the $kth + 1$.

What next?

In the next article, we will be dealing with the implementation of the basic arithmetic operations