嗨,我正在尝试用 Javascript 实现 karatsuba 算法。到目前为止,该算法在某些情况下工作正常,例如当整数的长度为 4 或 8 时。当整数的长度为 6 时,它会打印出错误的结果
例如:3141*2718=>8537238(正确结果)
例如:314*271=>84981.37398106341(错误结果)
例如:3141592653589793238462643383279502884197169399375105820974944592 * 2718281828459045235360287471352662497757247093699959574966967627 =>8.539734222673569e+126(部分正确)
var firstnumber= 3141592653589793238462643383279502884197169399375105820974944592
var secondNumber=2718281828459045235360287471352662497757247093699959574966967627
Karatsuba(firstnumber,secondNumber)
function Karatsuba(x,y)
{
if(x<10 || y<10)
{
return x*y
}
var first=Math.ceil(Math.log(x + 1) / Math.LN10)
var second=Math.ceil(Math.log(x + 1) / Math.LN10)
var min=Math.min(first,second);
var a=Math.floor(x/Math.pow(10,min/2))
var b=Math.floor(x%Math.pow(10,min/2))
var c=Math.floor(y/Math.pow(10,min/2))
var d=Math.floor(y%Math.pow(10,min/2))
var s=Math.pow(10,min/2)
return ((Math.pow(10,min))*Karatsuba(a,c)+ s*(Karatsuba(a,d) +Karatsuba(b,c)) + Karatsuba(b,d))
}
最佳答案
这可能不是结果不正确的唯一原因,但在 javascript 中,所有数字都是固定精度 float ,对于大数字(超过 15 位),您将遇到精度不足的问题,这会带来不正确的结果。但这并不能解释为什么它对于相对较小的数字是不正确的(6位整数可以完美地表示为 float 和 double )
关于Karatsuba 乘法算法的 JavaScript 实现,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/61574291/