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算法

回答

相關問題