使用BigInteger實現karatsuba算法錯誤

我正在嘗試使用Java來起訴BigInteger的karatsuba算法，我遵循了所有步驟，但是我沒有得到正確的結果，是什麼讓我發瘋。使用BigInteger實現karatsuba算法錯誤

這裏是我的代碼：

public BigInteger karatsuba(BigInteger a, BigInteger b, int base) { 
    if (a.compareTo(BigInteger.TEN) == -1 || b.compareTo(BigInteger.TEN) == -1) { 
     return a.multiply(b); 
    } 

    /* calculates the size of the numbers */ 
    int tam = a.toString().length(); 
    int mitad = tam/2; 


    BigInteger a1 = (a.divide(BigInteger.valueOf((long) Math.pow(base, mitad)))); 
    BigInteger a0 = (a.remainder(BigInteger.valueOf((long) Math.pow(base, mitad)))); 

    BigInteger b1 = (b.divide(BigInteger.valueOf((long) Math.pow(base, mitad)))); 
    BigInteger b0 = (b.remainder(BigInteger.valueOf((long) Math.pow(base, mitad)))); 

    /* 3 calls made to numbers approximately half the size */ 
    BigInteger t1 = karatsuba(a1, b1, base); 
    BigInteger t2 = karatsuba(a0, b0, base); 
    BigInteger t3 = karatsuba(a1.add(a0), b1.add(b0), base); 

    BigInteger aux1 = (t1.multiply(BigInteger.valueOf((long)Math.pow(base, tam)))); 
    BigInteger aux2 = t1.subtract(t2); 
    BigInteger aux4 = aux2.subtract(t3); 
    BigInteger aux3 = aux4.multiply(BigInteger.valueOf((long) Math.pow(base,mitad)).add(t2)); 

    return aux1.add(aux3); 

}

我測試的代碼如下條目：karatsuba(new BigInteger("1252",new BigInteger("532") , 10)而正確的結果是666064，我得到2212864 !!!並且我調試了，令人驚訝的是，當執行流程到達返回語句時，程序不會停止，但會進入BigInteger t2 = karatsuba(a0, b0, base);聲明。

所以我不知道我在做什麼錯。任何幫助將不勝感激。

來源

2017-02-04 shadow

不是JAVA編碼器，所以我可能是錯的，但：1. Math.pow（base，mitad）是可疑的，因爲結果是'float'，這很可能不適合結果。2. Karatsuba是遞歸所以所有的遞歸層必須在最終返回之前調用纔會真正返回...因爲我不使用大整數，所以我不確定'a.divide，a.remainder是否真的在做你想要的。如果它真的是分割和模數，那麼這是錯誤的，因爲你需要劃分bigint的內部表示而不是數字本身，否則你會使用bigint'/，％'作爲bigint'*'，這是瘋狂。 – Spektre

這可能不是你的問題（因爲1252和532完全在非Big整數範圍內），但'Math.pow'不太可能適用於實際的大整數。這也可能不是你的問題（因爲你正在測試'base'設置爲10），但是'a.toString（）.length（）'不可能計算出正確的大小，除非'base'是10. –

btw [快速bignum平方計算]（http://stackoverflow.com/q/18465326/2521214）你可以在最後找到我的arbnum Karatsuba在C++中的實現（arbnum是任意的mantissa float，所以你可以忽略bigint的指數） – Spektre

這裏是當然普林斯頓大學「使用Java程序設計入門」 Karatsuba algorithm implementation：

public static BigInteger karatsuba(BigInteger x, BigInteger y) { 

    // cutoff to brute force 
    int n = Math.max(x.bitLength(), y.bitLength()); 
    if (n <= 10) return x.multiply(y); 

    // number of bits divided by 2, rounded up 
    n = (n/2) + (n % 2); 

    final BigInteger b = x.shiftRight(n); 
    final BigInteger a = x.subtract(b.shiftLeft(n)); 
    final BigInteger d = y.shiftRight(n); 
    final BigInteger c = y.subtract(d.shiftLeft(n)); 

    // compute sub-expressions 
    final BigInteger ac = karatsuba(a, c); 
    final BigInteger bd = karatsuba(b, d); 
    final BigInteger abcd = karatsuba(a.add(b), c.add(d)); 

    return ac.add(abcd.subtract(ac).subtract(bd).shiftLeft(n)).add(bd.shiftLeft(2 * n)); 
    }

我認爲你可以大膽地使用它。

來源

2017-03-11 09:46:36 Nolequen

使用BigInteger實現karatsuba算法錯誤

回答

相關問題