Multiple Precision in JavaScript: Fast Division IV

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(n2), 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 a \ge b\epsilon with \epsilon > 1 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 \epsilon but your mileage may vary as always.

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

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s