javascript 32位整数乘法模拟

Question

我只想将 int 与 32 位整数相乘并溢出。

一些按位运算容易让人喜欢的文章

function add32bit( a, b )
{
    return (a+b)|0;
}

就这样。

function mul32bit( a, b )
{
    return (a*b)|0;
}

但这行不通。

在允许整数溢出的32位整数系统中。

计算

12312311 * 1231231211 = -236858179

但是使用 javascript

(12312311 * 1231231211)|0 = -236858180

有办法精确计算。

Answer 1

解决方案(？)

根据 Richie Frame 的提示，我尝试使用 Karatsuba algorithm 编写一个函数，将两个整数相乘并将结果作为带符号的 32 位整数返回。

// base algorithm from: https://en.wikipedia.org/wiki/Karatsuba_algorithm
// modified to discard values unneccessary for 32-Bit-operations

function int32_mul(x, y)
{
    // We use B = 2 and m = 16, because it will make sure that we only do multiplications with
    // 16 Bit per factor so that the result must have less than 32 Bit in total (which fits well
    // into a double).
    var bm = 1 << 16;

    x0 = x % bm;
    x1 = (x - x0) / bm;

    y0 = y % bm;
    y1 = (y - y0) / bm;

    // z1 + z0. We can discard z2 completely as it only contains a value out of our relevant bounds.
    // Both z1 and z0 are 32 Bit, but we shift out the top 16 Bit of z1.
    return (((x1 * y0 + x0 * y1) << 16) + (x0 * y0)) | 0;
}

我也进行了一些测试以确保它有效，但我不是该领域的专家，因此我不能保证它适用于所有组合。老实说，我的大脑对这个问题有点糊涂。

var tests = [
    [ 0, 0, 0 ],
    [ 0, 1, 0 ],
    [ 1, 1 << 8, 256 ],
    [ 1, 1 << 16, 65536 ],
    [ 1, 1 << 24, 16777216 ],
    [ 1, 0x7fffffff, 2147483647 ],
    [ 1, 0x80000000, -2147483648 ],
    [ 1, 0xffffffff, -1 ],
    [ 2, 1 << 8, 512 ],
    [ 2, 1 << 16, 131072 ],
    [ 2, 1 << 24, 33554432 ],
    [ 2, 0x80000000, 0 ],
    [ 2, 0x7fffffff, -2 ],
    [ 2, 0xffffffff, -2 ],
    [ 256, 256, 65536 ],
    [ 65536, 65536, 0 ],
    [ -2, 2, -4 ],
    [ -65536, 65536, 0 ],
    [ -2, -2, 4 ],
    [ -2147483648, 1, -2147483648 ],
    [ -2147483649, 1, 2147483647 ],
    [ 12312311, 1231231211, -236858179 ],
];

for (var i = 0; i < tests.length; ++i)
{
    var test = tests[i];
    if (int32_mul(test[0], test[1]) !== test[2])
    { console.log(test[0], '*', test[1], '!==', test[2]); }
}

如果更专业的人发现了这一点，请发表评论和/或启发我们进一步的测试用例。

我也不能完全说出这个函数接受什么样的值。我很确定它能很好地处理所有有符号的 32 位整数，但它也可以处理无符号的 32 位整数，或者甚至任何不超过 68 位的整数组合(我们拆分的 16 位 + 52 Bits ) 总计(负数和正数，因为符号在 double 中有一个自己的位)。

问题说明

请解释为什么 JavaScript 会为我们提供错误的结果。我使用 C 运行了一些简单的测试(在 http://ideone.com/ELSgD0 上摆弄它):

#include <stdio.h>
#include <stdint.h>

int main(void) {
    printf("%d\n", (int32_t)(12312311L * 1231231211L));
    printf("%llu\n", (uint64_t)12312311L * 1231231211L);
    printf("%.32f\n", 12312311. * 1231231211.);
    printf("%.8f\n", 15159301582738621.);
    return 0;
}

输出:

-236858179
15159301582738621
15159301582738620.00000000000000000000000000000000
15159301582738620.00000000

Javascript 在所有计算中都使用 double (甚至是整数)。从上面的测试我得出结论，double 不能有值 15159301582738621。

这是因为 float(32 位)、double(64 位)和 quad(128 位)等 float 据类型的工作方式。基本上它们不存储精确值，而是存储 x * 2^y 形式的值的 x 和 y 值，这使得它们存储非常大的值和非常小的值。我们(人类)过去常常对非常大和非常小的数字使用类似的语法，例如1e9 代表十亿或 1e-5 代表 0.00001，而 e 是 * 的快捷方式10^。

现在假设您计算 10001 * 10001，这显然是 100020001，但假设您只能存储 5 位数字和一个指数。要存储结果，您必须对其进行近似并使用例如1.0002e8 或 10002e4。如您所见，您必须忘记末尾的 1 。实际上，你的例子中 double 的问题非常相似，只是规模更大，基数为 2 而不是 10。

最后两个 printf 语句证明 double 不能保存值 15159301582738621，这正是您的示例计算的结果。如果您尝试使用 12312311 * 1231231212(第二个数字末尾为 2 而不是 1)，您会发现并非此范围内的所有数字都不能存储为 double，因为该计算工作正常与你的功能。