Imagine you need to implement (integer) mulitplication in code. Maybe you are on a system which doesn't have it or something. How to do this, and what is the minimal set of operators that are required?
The most obvious way to do multiplition is through repeated addition. To get the answer to 56 x 67 you add 56 to itself 67 times (or 67, 56 times - the order doesn't matter).
This is simple to implement if we assume for the moment that both a and b are positive (we will deal with negative integers later)
function mult_by_add(a, b) {
let result = 0;
for (let i = 0; i < b; i++) {
result += a;
}
return result;
}The order of the arguments is obviously going to make a big performance difference here - 3456 x 2 is going to involve one addition, whereas 2 x 3456 needs 3455. We always want the second operand to be the smaller one. This is easy to check for and fix with a small wrapper:
function mult(a, b) => {
if (b > a) {
return mult(b, a);
} else {
return mult_by_add(a, b);
}
}Even with the operand swapping trick, multiplying two five digit numbers will involve tens of thousands of operations, and worse, the growth is linear to the size of numbers - doubling the number doubles the number of operations needed (so it quickly becomes infeasible). Yet multiplication is not thousands of times slower than addition on any real machine. Can we find a better method?
It's a well known trick that multiplying by a power of two is fast, because it can be done through bit shifting. For example to calculate 3456 x 128 you don't need to do 128 additions, you shift-left by 7 bits. One operation vs 128. This is a nice shortcut if one of the numbers happen to be a power of two, but of course, most numbers aren't. What if the calculation is say, 3456 x 80, must we go back to repeated addition?
But notice that 3456 x 80 could also be written as 3456 x 64 + 3456 x 16. 64 and 16 are both powers of two (2^6 and 2^4 respectively), so we can use our power-of-two trick after all, and then add the results together. Three operations (two shifts and an addition) instead of 80.
In fact any multiplication can be written this way, as a series of adding powers of two. How do we know what powers of two to use? Conveniently this is the same as the binary representation of the number in question. eg. 80 in binary looks like this:
80 => 01010000
bit index => 76543210
The 1's at bit 6 and 4 mean that 80 can be expressed as 2^4 + 2^6. It's easy to derive the multiplcation formula above from this with some high school algebra 1.
So, to mulitply a x b using this method we go through the bits in b and if it is a one, shift a by the appropriate number of bits and add it to the result;
For example:
function bitwise_mult(a, b) {
let result = 0;
let mask = 1;
let bitIndex = 0;
// if the mask is bigger than the operand it means
// there are no more bits to process
while (mask <= b) {
if (b & mask) {
// a << bitIndex is the same as `a * 2^bitIndex`
result += a << bitIndex;
}
mask = mask << 1;
bitIndex += 1;
}
return result;
}We need only the bitwise and and addition to implement this (Left shift is convienient, but can be implemented via addition if needed)
I'm a sucker for a recusive algorithm, so I'll mention that we can rewrite this recursivly as a single statement in a quite elegant way (which in javascript is sadly about 25% slower than the original iterative version above):
const bitwise_mult = (a, b, result = 0) =>
b > 0 ? fmult(a << 1, b >> 1, b & 1 ? result + a : result) : result;This has O(N) performance 2, where N is the number of bits, compared to the orginal "repeated addition" algorithm which was O(2^N). When I actually benchmarked it it was on average 3 or 4 times slower than adding two numbers.
I've been assuming a and b are both positive, but of course we would like to use all integers, not just positive ones. This is easy to handle by normalizing the operands with our wrapper:
function mult(a, b) => {
if (a < 0) {
return -mult(-a, b);
} else if (b < 0) {
return -mult(a, -b);
} else if (b > a) {
return mult(b, a);
} else {
return bitwise_mult(a, b);
}
}There are more advanced algorithms, that scale better (eg. Karatsuba multiplication), but the added complexity only makes it worthwhile when the numbers are very long, bit-shifting is good enough for most purposes involving 32 or 64-bit numbers.