javascript - 是否可以在没有 bignums 的情况下在 JavaScript 中执行快速 48 位无符号乘法？

Question

在 JavaScript 中，我们可以执行 48 位加法、减法、除法和取模:

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

所有这些操作都有效，因为中间值不能传递 Number.MAX_SAFE_INTEGER。但是，对于乘法，他们可以:

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

所以 u48_mul 可能返回不正确的结果。一种解决方案是使用 BigInt:

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

但是，在大多数浏览器中，它的速度要慢得多。有没有什么巧妙的技巧可以让我们在 JavaScript 中更快地执行 48 位无符号乘法？

Answer 1

假设 a, b >= 0，如果你将 a 和 b 写成基数为 2²⁴ 的整数，你有a = a₁⋅2²⁴ + a₀ 和 b = b₁⋅2²⁴ + b₀,
0 <= a₁, a₀, b₁, b₀ < 2^{24 .}

以这种形式 a⋅b = a₁⋅b₁⋅2⁴⁸ + (a₁ ⋅b₀ + a₀⋅b₁)⋅2²⁴ + a₀>⋅b₀。现在取模 2⁴⁸ 导致第一项变为 0。像 a₁⋅b₀ 这样的乘积是两个 24 位的乘积整数，因此与 JS 数字相乘会产生精确的 48 位结果。将两个这样的值加在一起可能会产生一个 49 位的值，但它仍然是 < 2⁵³，因此是准确的。因为我们要乘以 2²⁴，所以我们只需要保留这个和的低 24 位。这很好，因为当我们使用 24 位掩码对它进行 AND (&) 时，JS 将只保留低位 32 位。最后我们将结果添加到另一个 48 位值 a₀⋅b₀。结果可能会超过 2⁴⁸，如果超过，我们将减去 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;
}

由于@Mark Dickinson 的观察，可以通过消除其中一个被 2²⁴ 的除法来改进这一点。尽管 IEEE 754 binary64 float 可以精确表示 -2⁵³ 和 2⁵³ 之间的所有整数，但这些并不是唯一可以精确表示的整数。特别是在指定的 IEEE 754 指数范围内乘以 2 的幂的 48 或 49 位整数也可以精确表示。因此我们可以替换这五行

    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 a0 = a & mask24;
    let b0 = b & mask24;
    let t1 = ((((a - a0) * b0 + a0 * (b - b0)) / two_to_the_24th) & mask24) * two_to_the_24th;

因为 (a - a0) 和 (b - b0) 都是 2²⁴ 的倍数，所以它们的乘积必须是 b0 和 a0 因此必须是这些乘积的总和。换句话说，(a - a0) 和 (b - b0) 都只有 24 个 significant 位，所以乘积只有 48 个有效位位，它们的总和只有 49 个有效位。

现在，这比使用 Bigint 更快吗？在 Chrome 96.0.4664.55(官方构建)(x86_64) 上的实验中，它比您的 u48_mul 的 BigInt 版本快将近 6 倍。