Is it possible to perform fast 48-bit unsigned multiplication in JavaScript without bignums?

user_1031791 0
Viewed 114

In JavaScript, we can perform 48-bit addition, subtraction, division and modulus:

In JavaScript, we can perform 48-bit addition, subtraction, division and modulus, using the native Number type:

function u48_add(a, b) {
  return (a + b) % Math.pow(2, 48);
}

function u48_sub(a, b) {
  return (a - b + Math.pow(2,48)) % Math.pow(2, 48);
}

function u48_div(a, b) {
  return Math.floor(a / b);
}

function u48_mod(a, b) {
  return a % b;
}

All these operations work, because the intermediate values can't pass Number.MAX_SAFE_INTEGER. For multiplication, though, they could:

function u48_mul(a, b) {
  return (a * b) % Math.pow(2, 48);
}

So u48_mul could return incorrect results. A solution would be to use BigInt:

function u48_mul(a, b) {
  return Number((BigInt(a) * BigInt(b)) % (2n ** 48n));
}

But, in most browsers, it is drastically slower. Is there any clever trick that allows us to perform 48-bit unsigned multiplication in JavaScript faster?

bit-manipulation floating-point math javascript
1 Answers

Assuming a, b >= 0, if you write a and b as radix 224 integers you have a = a1⋅224 + a0 and b = b1⋅224 + b0,
0 <= a1, a0, b1, b0 < 224.

In this form a⋅b = a1⋅b1⋅248 + (a1⋅b0 + a0⋅b1)⋅224 + a0⋅b0. Now taking this mod 248 causes the first term to become 0. Products like a1⋅b0 are the multiplication of two 24-bit integers, so multiplied as JS numbers produces the exact 48-bit result. Adding two such values together may produce a 49-bit value, but that is still < 253 and thus exact. Since we're going to be multiplying by 224 we need only retain the low-order 24 bits of this sum. That's good because when we AND (&) it with a 24-bit mask JS will keep only the low order 32-bits. Finally we add the result to a0⋅b0, another 48-bit value. The result may exceed 248 and if it does then we'll just subtract 248.

function mulmod48(a, b) {
    const two_to_the_24th = 16777216;
    const two_to_the_48th = two_to_the_24th * two_to_the_24th;
    const mask24 = two_to_the_24th - 1;

    let a0 = a & mask24;
    let a1 = (a - a0) / two_to_the_24th;
    let b0 = b & mask24;
    let b1 = (b - b0) / two_to_the_24th;
    let t1 = ((a1 * b0 + a0 * b1) & mask24) * two_to_the_24th;
    let result = t1 + a0 * b0;
    if (result >= two_to_the_48th) {
        result -= two_to_the_48th;
    }
    return result;
}

This can be improved by eliminating one of the divisions by 224, thanks to an observation by @Mark Dickinson. Although IEEE 754 binary64 floats can represent exactly all integers between -253 and 253, those are not the only integers that can be represented exactly. In particular a 48 or 49 bit integer multiplied by a power of 2 within the specified IEEE 754 exponent range can also be represented exactly. Thus we can replace these five lines

    let a0 = a & mask24;
    let a1 = (a - a0) / two_to_the_24th;
    let b0 = b & mask24;
    let b1 = (b - b0) / two_to_the_24th;
    let t1 = ((a1 * b0 + a0 * b1) & mask24) * two_to_the_24th;

with these three

    let a0 = a & mask24;
    let b0 = b & mask24;
    let t1 = ((((a - a0) * b0 + a0 * (b - b0)) / two_to_the_24th) & mask24) * two_to_the_24th;

since both (a - a0) and (b - b0) are multiples of 224 so must the products of these with b0 and a0 and therefore so must the sum of these products. In other words, both (a - a0) and (b - b0) have only 24 significant bits, so the products have only 48 significants bits and the sum of those has only 49 significant bits.

Now, is this any faster than using Bigints? In an experiment on Chrome 96.0.4664.55 (Official Build) (x86_64) it was almost 6x faster than your BigInt version of u48_mul.

user_2387040
Related