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:
-
Check the sign character and skip the leading
0's from the number string. -
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...)
-
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:
-
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.
-
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 digitstringto anint, then multiply all the elements of the array by 109 (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 109 to open up space to add the following group of digits:265252 ✕ 109 = 265252000000000Now we add the following group of digits and repeat by scaling the result again with 109
265252000000000 + 859812191 = 265252859812191265252859812191 ✕ 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 109 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 109 takes care of the carry and then sums the new group element. This last operation is implemented in methoddestructiveMulAddinside 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
\[ \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 \]x = 109. Scaling the number is a matter of multiplying the polynomial by109: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
