1

您好我正在尝试在 Javascript 中实现 karatsuba 算法。截至目前，该算法适用于某些情况，例如整数长度为 4 或 8 时。当整数长度为 6 时，它会打印出错误的结果

例如：3141*2718=>8537238（正确结果）

例如：314*271=>84981.37398106341（结果不正确）

Eg: 3141592653589793238462643383279502884197169399375105820974944592 * 2718281828459045235360287471352662497757247093699959574966967627 =>8.539734222673569e+126 (partially correct )

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))
}
4

1 回答 1

1

这可能不是您的结果不正确的唯一原因，但是在 javascript 中，所有数字都是定精度浮点数，并且对于大数字（超过 15 位），您将遇到精度不足，这将带来到不正确的结果。但这并不能解释为什么它对于相对较小的数字是不正确的（6 位整数可以完美地表示为浮点数和双精度数）

于 2020-05-03T12:37:02.320 回答