在JavaScript中實現Karatsuba乘法？

我試圖實現karatsuba algorithm使用下面code.The問題開始時的在x和y位（參數）失配爲recursive call數與以下邏輯那種情況下不工作。到目前爲止，當x和y中的位數相同時，我會得到正確的輸出。在JavaScript中實現Karatsuba乘法？

更準確地說，我認爲問題從z1和z3的計算開始，因爲這是x和y數字頻繁失配的地方。

另外我有點混淆導出如何定義m這是在這裏的基地的力量的邏輯。我相信我的問題清楚了嗎？（任何有關更多優化的建議都會更有幫助，因爲我剛剛開始了我的java腳本之旅）。

function karatSuba(x,y) 
{ 
    var x1,x0,y1,y0,base,m; 
    var dummy_x = x.toString(); 
    var dummy_y = y.toString(); 
    var n = (dummy_x.length>dummy_y.length) ? dummy_y.length : dummy_x.length; 
    m = Math.round(n/2); 
    base = 10; 

    //base case 
    if((x<base)||(y<base)) 
    return x * y; 
    //base case 

    var bm = Math.pow(base ,m); 

    var dummy_x1 = dummy_x.substring(0,n/2); 
    var x1 = parseInt(dummy_x1); 
    dummy_x1 = null; 

    var dummy_x1 = dummy_x.substring(n/2,n); 
    var x0 = parseInt(dummy_x1); 
    dummy_x1 = null; 

    var dummy_y1 = dummy_y.substring(0,n/2); 
    var y1 = parseInt(dummy_y1); 
    dummy_y1 = null; 

    var dummy_y0 = dummy_y.substring(n/2,n); 
    var y0 = parseInt(dummy_y0); 
    dummy_y = null; 

    var p = x1 + x0; 
    var q = y1 + y0; 

    var a = karatSuba(x1,y1); 
    var b = karatSuba(x0,y0); 
    var z1 = karatSuba(a,Math.pow(bm,2)); 
    var z2 = b; 
    //var z3 = karatSmul(bm ,((karatSmul(p,q) - a - b))); 
    var z3 = bm * ((p*q) - (a) - (b)); 
    var z = z1 + z2 + z3; 
    return z; 

} 

console.log(karatSuba(344,100));

來源

2015-02-06 ShankarGuru

你有沒有試過簡單地填充前導零的短字符串？我沒有仔細檢查過所有的代碼，但是我懷疑當短字符串的長度小於n/2時會遇到問題。 – Katie 2015-02-06 18:45:48

我嘗試過，但輸出似乎是一個莫名其妙的。例如，在我計算z1的地方，如果它的東西像karatsuba（35,100）...我將z1變成了350而不是3500.我相信那是造成問題的原因。 – ShankarGuru 2015-02-06 19:27:37

@Katie請問您可以澄清更多關於用零填充較短的字符串。像karatsuba（35,121）案件將流出邏輯然後.. – ShankarGuru 2015-02-06 20:59:43

您編寫算法的方式有幾個錯誤。下面的代碼應該工作。

function karatSuba(x,y) 
{ 

    var x1,x0,y1,y0,base,m; 
    base = 10; 


    if((x<base)||(y<base)){ 
    console.log(" X - y = " , x,y, x*y) 
    return x * y; 
    } 

    var dummy_x = x.toString(); 
    var dummy_y = y.toString(); 

    var n = (dummy_x.length > dummy_y.length) ? dummy_y.length : dummy_x.length; 
    m = Math.round(n/2); 



    var high1 = parseInt(dummy_x.substring(0,dummy_x.length-m)); 
    var low1 = parseInt(dummy_x.substring(dummy_x.length-m,dummy_x.length )) ; 

    var high2 = parseInt(dummy_y.substring(0,dummy_y.length-m)); 
    var low2 = parseInt(dummy_y.substring(dummy_y.length-m,dummy_y.length)); 


    var z0 = karatSuba(low1, low2); 
    var z1 = karatSuba(low1+high1, low2+high2); 
    var z2 = karatSuba(high1,high2); 

    var res = (z2 * Math.pow(10, 2 * m) ) + ((z1-z2-z0) * Math.pow(10, m)) + z0; 

    return res; 

} 

var a = 12345; 
var b = 6789; 
console.log(karatSuba(a,b)); 
console.log(a * b);

來源

2015-02-06 22:36:44

非常感謝。現在它工作正常。 – ShankarGuru 2015-02-09 09:23:01

在JavaScript中實現Karatsuba乘法？

回答

相關問題