我尝试了两个版本的 karatsuba 乘法算法,当我用较大的 X 和 Y 值测试它们时,它们都失败了,结果不同。
我正在使用的参数
const x = 3141592653589793238462643383279502884197169399375105820974944592
const y = 2718281828459045235360287471352662497757247093699959574966967627
const solution = 8539734222673567065463550869546574495034888535765114961879601127067743044893204848617875072216249073013374895871952806582723184
Algorithm1 我从这个页面得到:https://gist.github.com/haocong/c2d9b2169d28eb15a94d
Expected value to equal:
8.539734222673567e+126
Received:
7.292575034127423e+22
Algorithm2 我从这个页面得到:https://stackoverflow.com/a/28376023/604950
Expected value to equal:
8.539734222673567e+126
Received:
6.0002556749374185e+22
要重现你可以获取这个 PR: https://github.com/Falieson/Algorithms-Illuminated-Part1_TheBasics/pull/1
最佳答案
那是因为您使用的数字太大,而 JavaScript 不知道如何处理它们。
The Number.isSafeInteger() method determines whether the provided value is a number that is a safe integer.
2^53 - 1 is a safe integer: it can be exactly represented, and no other integer rounds to it under any IEEE-754 rounding mode. In contrast, 2^53 is not a safe integer.
console.log(warn(Math.pow(2, 53))); // expected output: "Precision may be lost!"
MDN
例如在你正在做的第二个算法中
var res = (z2 * Math.pow(10, 2 * m ) ) + ( (z1-z2-z0) * Math.pow(10, m )) + z0;
在你的情况下这不是一个安全的操作,JavaScript 无法正确计算它,给你一个错误的结果。
如果将此代码放在上面提到的行下,您将看到它。
console.log(Number.isSafeInteger(10 ** (2 * m)));
这评估为 false。
关于javascript - 大数的 karatsuba 乘法在 javascript 中失败,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/50556069/