代码之家 › 专栏 › 技术社区 › Falieson

在javascript中,大量数字的karatusuba乘法失败

math algorithm javascript

Falieson · 技术社区 · 6 年前

我尝试过两种版本的Karatsuba乘法算法,当我用大的x和y值测试它们时,它们都失败了,结果不同。

我使用的参数

const x = 3141592653589793238462643383279502884197169399375105820974944592
const y = 2718281828459045235360287471352662497757247093699959574966967627
const solution = 8539734222673567065463550869546574495034888535765114961879601127067743044893204848617875072216249073013374895871952806582723184

我从本页得到的算法1: https://gist.github.com/haocong/c2d9b2169d28eb15a94d

Expected value to equal:
  8.539734222673567e+126
Received:
  7.292575034127423e+22

我从本页得到的算法2: https://stackoverflow.com/a/28376023/604950

Expected value to equal:
  8.539734222673567e+126
Received:
  6.0002556749374185e+22

要复制,您可以获取此公关: https://github.com/Falieson/Algorithms-Illuminated-Part1_TheBasics/pull/1

1 回复 | 直到 6 年前

Matus Dubrava 6 年前

这是因为您使用的数字太大,而javascript不知道如何处理它们。

这个 数字.issafeinteger()) 方法确定提供的值是否为安全整数。

2^53-1是一个安全整数:它可以精确表示,并且在任何IEEE-754舍入模式下都不会向它舍入其他整数。相反,2^53不是一个安全整数。

console.log(warn(math.pow(2,53)); //预期输出:“精度可能会丢失!”

多媒体数字网

例如,在第二个算法中

var res  =   (z2 *  Math.pow(10, 2 * m )  ) + ( (z1-z2-z0) * Math.pow(10,  m )) + z0;

在您的情况下,这不是一个安全的操作,JavaScript无法正确计算它,从而导致错误的结果。

如果您将此代码放在上面提到的行下面,您将看到这一点。

console.log(Number.isSafeInteger(10 ** (2 * m)));

这会导致错误。

推荐文章

SkyWalker · 在JavaScript中,合并日期-时间序列的有效算法是什么?

1 年前

root · 计数算法

1 年前

André Silveira · 使用循环将数组的每个槽递增1。数组的大小是传递给函数的参数

2 年前

danial · 如何在多个字符串的每个位置找到最频繁的字符

2 年前

Manny · 如何比较Perl中的字符串?

2 年前

Suhail Gupta · 在排序阵列中查找目标范围的时间复杂度-此解在最坏情况下是否为O(N)?

2 年前

Diret · 获取范围内每个数字的子倍数的算法

2 年前

Saif · 排序时python如何决定何时调用比较器?

2 年前

TryingToLearn · 我如何为通用遥控器构造一个类,该遥控器向连接到它的各种设备发送开/关命令?

2 年前

Sneha Sharma · 滑动窗口-在我的代码中找不到错误(非常基本的算法)

2 年前