是否可以在没有 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 可能 return 不正确的结果。一种解决方案是使用 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²⁴.

这种形式 a⋅b = a₁⋅b₁⋅2⁴⁸ + (a₁⋅b₀ + a₀⋅b₁)⋅2²⁴ + a₀⋅b₀。现在取 mod 2⁴⁸ 导致第一项变为 0。产品如 a₁⋅b₀ 是两个 24 位整数的乘积，因此与 JS 数字相乘会产生精确的 48 位结果。将两个这样的值加在一起可能会产生一个 49 位的值，但它仍然小于 2⁵³，因此是准确的。因为我们要乘以 2²⁴，所以我们只需要保留这个和的低 24 位。这很好，因为当我们使用 24 位掩码对它进行 AND (&) 时，JS 将只保留低位 32 位。最后我们将结果添加到 a₀⋅b₀，另一个 48 位值。结果可能会超过 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 浮点数可以精确表示 -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 和 [=16= 的乘积一定是] 因此这些产品的总和也必须如此。换句话说，(a - a0) 和 (b - b0) 都只有 24 significant bits，所以乘积只有 48 significant bits 而它们的总和只有 49 significant bits .

现在，这比使用 Bigint 更快吗？在 Chrome 96.0.4664.55 (Official Build) (x86_64) 的实验中，它比 u48_mul.

的 BigInt 版本快将近 6 倍

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

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

javascript

math

floating-point

bit-manipulation