JavaScript реализация алгоритма умножения Карацубы - PullRequest
Новая
       107

JavaScript реализация алгоритма умножения Карацубы

1 голос
/ 03 мая 2020

Привет, я пытаюсь реализовать алгоритм Карацубы в Javascript. На данный момент алгоритм работает нормально для определенных случаев, например, когда длина целого числа равна 4 или 8. Когда длина целого числа равна 6, он выводит неверный результат

Например: 3141 * 2718 => 8537238 (правильный результат )

* * 1004 Например: 314 * 271 => 84981,37398106341 (неверный результат) * * 1006 Например: 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))
}

1 Ответ

1 голос
/ 03 мая 2020

Это может быть не единственной причиной неверности ваших результатов, но в javascript все числа являются числами с плавающей запятой с фиксированной точностью, а с большими числами (более 15 цифр) вы встретите отсутствие точность, которая приведет к неверным результатам. Но это не объясняет, почему это неверно для относительно небольших чисел (целое число из 6 цифр может быть идеально представлено как с плавающей точкой, так и с двойной)

...