In the last post, I gave an overview of how BigIntegers are stored and how addition and subtraction work. Now it’s time to move up the hyperoperation sequence and and discuss multiplication.
Simple Multiplication
Probably the simplest way to think about multiplication is repeated addition. In other words, 4*5 = 5+5+5+5. Using that definition, it would be trivial to write a multiplication function in terms of addition:
// Assume we've defined "ZERO" and "ONE" constants and a "notZero(n)" function, which are all trivial.
// notZero can be as simple as "return n.sign !== 0".
function multiply(a, b) {
var product = ZERO;
while (notZero(a)) {
product = add(product, b);
a = subtract(a, ONE);
}
return product;
}Something like the code above would work, but would be extremely slow. Imagine multiplying even relatively small numbers (for a big integer library) like 123,456,789 * 65,128,321. Even optimizing it by making sure a is smaller (remember, order doesn’t matter in multiplication) we would have to run the loop 65,128,321 times, with an addition and subtraction each time. Now imagine two 100 digit numbers! Obviously this won’t work.
Grade School Multiplication
The key thing to remember is that numbers are polynomials. So 123 * 456 is really (1 * 100 + 2 * 10 + 3) * (4 * 100 + 5 * 10 + 6). Simplifying a little more, we get (100 + 20 + 3) * (400 + 50 + 6). Lets leave the right side how it is and add up the terms on the left to get our original 123 back: 123 * (400 + 50 + 6). Now we can use the distributive property and get 123*400 + 123*50 + 123*6 = 49200 + 6150 + 738.
All that is a great flashback to your high school algebra class, but how does it help us? Remember that to multiply by a factor of 10, you just add zeros to the end of the number. If we factor out the power of 10 from each term, we just have to do a couple single-digit multiplications, append some zeros, and do a couple additions. Easy! In fact, this is how you’ve been doing multiplication since grade school.
123
x 456
-----
738
615
+492
=====
56088So let’s break down what we’re doing. Starting from the right, take each digit from the bottom number, multiply it by each digit of the top number (also from right to left) and write down the result. I’ve glossed over it so far, but remember if you end up with a two digit number, you have to carry the first digit and add it to the next result. Then you move to the next digit, remembering to “multiply by 10″ by shifting the numbers over to the left each time. Finally, add up all the “partial products” and you have the (hopefully correct) answer!
So, how do we do this in code? I’m glad you asked. Here’s a straightforward implementation (we’ll optimize it slightly by eliminating some of the intermediate steps later):
function multiply(a, b) {
// To keep track of all the partial products
var partialProducts = [];
// For each digit of b
for (var i = 0; i < b.digits.length; i++) {
var carry = 0;
var digit;
var partial = {sign: 1, digits: []}; // Initialize a new partial product
// For each digit of a
for (var 0; j < a.digits.length; j++) {
digit = (b.digits[i] * a.digits[j]) + carry; // Multiply the digits, adding in any carry
carry = Math.floor(digit / 10); // Integer divide by 10 to get the first digit
partial.digits[j] = digit % 10; // Mod 10 gets the second digit
}
// Don't forget the final carry (if necessary)!
if (carry > 0) {
partial.digits[j] = carry;
}
// Shift the digits to the left to multiply by the next power of 10
for (var shift = 0; shift < i; shift++) {
// Unfortunately, JS's naming is backwards from ours.
// "array.unshift(0)" pushes a zero into the front of the array, which is what we want
partial.digits.unshift(0);
}
// Append this partial product to the list
partialProducts.push(partial);
}
// Now add up all the partial products
var product = ZERO;
for (var i = 0; i < partialProducts.length; i++) {
product = add(product, partialProducts[i]);
}
return product;
}Whew! That’s pretty long, but fairly simple. For each digit of b, loop through each digit of a, multiplying the digits and storing them in the partial product, then add up the partial products at the end.
It’s also still inefficient for several reasons. It’s much better than the simple “loop and add” function at the beginning but we can do better, and actually shorten the code at the same time.
The Real Algorithm
The problem is all those partial products. Instead of building up a list (taking up a potentially large amount of memory) then adding them up at the end, we can just add in each product as we go. We can also avoid pushing all the zeros in by adjusting how we index into the arrays.
function multiply(a, b) {
var partial = { sign: a.sign * b.sign, digits: [] }; // digits should be filled with zeros
// For each digit of b
for (var i = 0; i < b.digits.length; i++) {
var carry = 0;
var digit;
// For each digit of a
for (var j = i; j < a.digits.length + i; j++) {
// Multiply the digits, and add them to the current partial product, along with any carry
digit = partial.digits[j] + (b.digits[i] * a.digits[j - i]) + carry;
carry = Math.floor(digit / 10); // New carry
partial.digits[j] = digit % 10; // Put the result back into the partial product
}
// Don't forget the final carry (if necessary)!
if (carry) {
digit = partial.digits[j] + carry;
carry = Math.floor(digit / 10);
partial.digits[j] = digit % 10;
}
}
// That's it!
return partial;
}I didn’t mention it before, but the nice thing about multiplication is that the sign is easy to get right. Because our sign property is a 1 (or zero) with the same sign as the number itself, the resulting sign is just a.sign * b.sign.
Further Optimizations
The last function above, is basically how the BigInteger library does multiplication (except in base 10000000 and, as usual, I’ve skipped over some minor details for clarity). But there are actually more sophisticated algorithms to make multiplying huge numbers faster.
They are mostly based on Karatsuba multiplication, which is a recursive “divide and conquer” algorithm. The added complexity and overhead of recursive function calls makes it slower for “reasonably sized” numbers, so it’s best to use simple long multiplication until you get to some threshold then switch to Karatsuba multiplication. I experimented with supporting it early on and the cutoff was somewhere in the several-thousand-digit range.
