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?

CodePudding user response：

Assuming a, b >= 0, if you write a and b as radix 2²⁴ integers you have a = a₁⋅2²⁴ a₀ and b = b₁⋅2²⁴ b₀,
0 <= a₁, a₀, b₁, b₀ < 2²⁴.

In this form a⋅b = a₁⋅b₁⋅2⁴⁸ (a₁⋅b₀ a₀⋅b₁)⋅2²⁴ a₀⋅b₀. Now taking this mod 2⁴⁸ causes the first term to become 0. Products like a₁⋅b₀ 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 < 2⁵³ and thus exact. Since we're going to be multiplying by 2²⁴ 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 a₀⋅b₀, another 48-bit value. The result may exceed 2⁴⁸ and if it does then we'll just subtract 2⁴⁸.

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;
}

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.