Do addition with numbers of arbitrary base

arithmetic

So I want to implement this BigInt algorithm but use arbitrary bases:

var c = { sign: 1, digits: [] }; // We'll store the result in c
var carry = 0;                   // Nothing to carry yet
for (var i = 0; i < a.digits.length; i++) {
    c.digits[i] = a.digits[i] + b.digits[i] + carry;
    if (c.digits[i] >= 10) { // Oops, too big.
        carry = 1;           // Set the carry to be added into the next digit
        c.digits[i] -= 10;   // Adjust to be one digit
    }
    else {
        carry = 0;           // It fit, so there's nothing to carry
    }
}
if (carry) { // Don't forget to add the final carry if it's needed
    c.digits[i] = carry;
}

Essentially this is doing what you do when you first learn addition in elementary school:

 314159
+  2718
-------
 316877

You stack them up with the ones place lined up. Then you go from right to left, adding each pair of digits. 8+9 = 17, 5+1 = 6, 1+7 = 8, and so on. But the 17 is a problem, because you can only put down one digit in each place, so you have to carry the 1 to the next place. So backing up, we have 9+8 = 17, so write down the 7 and carry the one, then 5+1+1 = 7. That's one digit so we don't have to carry anything, so we just have 1+7 = 8 and so on. Pretty simple right? It's exactly what you've been doing since first grade (or whenever).

My question is, can you do this with different based numbers? Like for instance, I want to use 7-bit numbers (128 base). Could I just line up 2 arrays of 7-bit numbers the same way, and add them, where the carry would be "too big" at 128, not 10, and go from there? How do I do it exactly, for arbitrary bases? What is the technique?

Best Answer

The simplest approach is just to represent each number as an array with one digit per entry. To add two numbers, you add them element by element, then handle carries. This works for all bases up to half the largest integer that fits into an array element. If you are using base $365$ you would just add the two numbers, then check the first element (which I assume is the ones place). If it exceeds $365$ you subtract $365$ and add one to the next element. Now look at the next place.

You could certainly store bases up to $127$ with one digit per byte. The algorithm for addition is more complicated because you have to find the carries in the middle of the number. Multiplication will be worse yet. The array approach above lends itself to multiplication as well. If the two numbers are $a[i]$ and $b[i]$ you multiply them into $c[i]$ as $c[k]=\sum_ia[i]b[k-i]$. Now your carries may be larger than $1$, so you would look at each $c[i]$ and integer divide it by the base to get the carry, then mod it by the base to get the remainder.

I believe Python has already implemented this in a package. I would guess c has as well.

Related Question