## Balanced Multiplication

What has multiplication to do with division? With division alone? Nothing at all. With *fast* division? Everything. All fast division algorithms depend more or less on fast multiplication to reach their goal of being asymptotically faster than schoolbook division at least.

These fast multiplication algorithms depend on multiplicands of roughly the same size[1]. You can do some tricks to come near to this ideal and one of the simplest ones is this one:

The computational complexity of multiplication is O(n^{2}), that means, that you have to touch every digit of the participants: with 123*456 you get the following single multiplications: 1*4,1*5,1*6,2*4,2*5,2*6,3*4,3*5,3*6.

But computational complexity with the O-notation is a general value, it decreases to O(n) if one of the participants has only a single digit. And that is also general which means that it does not matter how big these digits are.

We can make use of this fact to balance multiplication if the multiplicands meet the conditions with and the smaller multiplicand must be larger than or equal to the karatsuba-cutoff point.

// Assumes smaller multiplicand is in variable y function mulBalanced(x, y) { var tmp, ret; var xlen, ylen, nblocks; xlen = x.used; ylen = y.used; // make big-digits and work with them like normal // sized digits with y representing a single digit. nblocks = Math.floor(xlen / ylen); ret = new Bigint(0); for (var i = 0; i < nblocks; i++) { tmp = x.slice(ylen * i, ylen * (i + 1)).mul(y); tmp.dlShiftInplace(ylen * i); ret = ret.add(tmp); } // the last digit MSB side is <= the smaller multiplicant tmp = x.slice(ylen * i, x.used).mul(y, true); tmp.dlShiftInplace(ylen * i); ret = ret.add(tmp); return ret; }

We cut the numbers limb-wise, so functions like `slice(start,end)`

do exactly that.

I have chosen half of the value of the karatsuba-cutoff as my but your mileage may vary as always.

[1] with the exception of truncated FFT multiplication which will be treated in a later post.