Javascript中的Karatsuba算法

我在Javascript中实现了Karatsuba算法。Javascript中的Karatsuba算法

const multiply = (a, b) => { 
    let sizeA = numOfDigits(a); 
    let sizeB = numOfDigits(b); 
    if(sizeA < sizeB) { 
     a = '0'.repeat(sizeB-sizeA).concat(a); 
    } 
    else if(sizeB < sizeA) { 
     b = '0'.repeat(sizeA - sizeB).concat(b); 
    } 
    if (numOfDigits(a) === 1 && numOfDigits(b) === 1) { 
     return a * b; 
    } else { 
     let n = numOfDigits(a); 
     n = (n % 2 === 0) ? n : n + 1; 
     let n_2 = parseInt(Math.ceil(n /2)); 
     let splitA = reduceInHalf(a); 
     let splitB = reduceInHalf(b); 
     let p = splitA[0]; 
     let q = splitA[1]; 
     let r = splitB[0]; 
     let s = splitB[1]; 
     let u = multiply(p, r); 
     let v = multiply((q - p).toString(), (s - r).toString()); 
     let w = multiply(q, s); 
     let product = u * Math.pow(10,n) + (u + w - v) * Math.pow(10, n_2) + w; 
     return product; 
    } 
}

当我通过非常大的数字，比如说2个64位数字时，它会失败。我陷入了最大的调用堆栈问题。我还遇到了另一个实现返回了错误的结果。

事情工作正常，每个也有32位数字。只要输入2 64位数字，它就会进入非终止递归。这可以工作吗？

来源

2016-11-12 Mayur Arora

看起来你依赖于各种部分的JavaScript数字功能（例如q - p，以及所有u * Math.pow(10,n) + (u + w - v) * Math.pow(10, n_2) + w）;但JavaScript数字是双精度浮点值。它们不能完全代表超过16位数字的整数。（请参阅"biggest integer that can be stored in a double"。）

如果要使用非常大的整数进行数学计算，则需要找到一个大整数库，或者自己管理它（使用字符串或数组或任何其他）。

来源

2016-11-12 19:20:01 ruakh

Javascript中的Karatsuba算法

回答

相关问题