Most of computer applications operates on small integers which can be represented by 32 bit integers. However, there are times we’ll need to deal with extremely big integers which can only be represented by hundreds of bits. One of such application is cryptography.
This post gives two simple implementations of the big integer arithmetic. Both implementations use char array to store the big integers. The first one stores the digits of the integer as char, and the second one stores the digits as single digit integer values.
We define a big integer as the structure below,
For example, given two input integers “111222333444555” and “12345”, we can store them into two BNs a and b, with a.length = 15, a.dg = ‘1’, a.dg=’1’ …, a.dg=’5’, a.sign = 1; b.length=5, b.dg=’1’, b.dg=’2’…a.dg=’5’, b.sign=1.
Addition: We add the two integers digit by digit from right to left. If the sum of the two digits is bigger than ‘9’. Then a carry of 1 is produced for the next position. And the carry is added to the sum of the digits at the next position. We store the digits of the result from left to right and then reverse it after it’s done.
Subtraction: Subtraction is similar to addition. We minus the digits from the two integers from right to left. If the resulted digit is less than 0, we borrow 1 from the next position.
Multiplication: A naive approach is to use addition to handle multiplication. But if both inputs are big, then the algorithm is very slow.
A better approach is to handle a single digit multiplication using addition, then shift the multiplicand by 1 (which is equivalent to x10) and handle the next digit multiplication.
For example, if the two inputs are 12345 and 57, we treat the multiplication as 12345 x 7 + 123450 x 5, then each of the two multiplications can be handled using additions. In this way, the number of additions needed are reduced to the sum of all digits of the multiplier.
Division: Again the naive approach is to use subtraction. A better alternative is trying to subtract the divisor from part of the dividend from right to left. For example, to compute 234 / 11, we start by computing 23 / 11 using subtraction. The quotient is 2 and the remainder is 1. We then compute (1*10 + 4) / 11 using subtraction, the quotient will be 1. So the result is 21.
Below is a C implementation of the algorithms described above,
Save the code to bignumarray.c, and compile the code using the command below,
gcc -o bignumarray bignumarray.c
And here are some simple tests,
Digit Array Representation
The big integer is still defined as below,
But now the dg holds the values for each digit. For example, given two inputs 12345 and 678, then the two big integers are a, b, with a.length = 5, a.sign = 1, and a.dg=5, a.dg=4, a.dg=3, a.dg=2, a.dg=1; b.length=3, b.sign = 1, and b.dg=8, b.dg=7, b.dg=6. Note that the digits are stored in a reverse manner because it is more convenient to manipulate the end of an array than the start of an array (e.g. truncate the array by 1).
The arithmetic operations are similar to the previous implementation. Below is the sample C code.
Save the code to bignumarray2.c, and compile the code using the command below,
gcc -o bignumarray2 bignumarray2.c
And here are some simple tests,
1. Dynamic array is necessary in order to support arbitrary length of big integers.
2. Using a single byte to represent a single digit is a huge waste. There’re better representations.
1. Programming Challenges