カラツバ法エラー

Question

私はカラツバ実装をやっているが、私はこのエラーを持っている：

java.lang.NumberFormatException: Zero length BigInteger 

    at java.math.BigInteger.<init>(BigInteger.java:296) 
    at java.math.BigInteger.<init>(BigInteger.java:476) 
    at com.Karatsuba.resolve(Karatsuba.java:20) 
    at com.Karatsuba.resolve(Karatsuba.java:26) 
    at com.KaratsubaTest.karatsubaShouldMultiply(KaratsubaTest.java:22) 

は、これが私の方法である：

BigInteger resolve(BigInteger left, BigInteger right) { 

     String leftS = left.toString(); 
     String rightS = right.toString(); 

     int digits = Math.max(leftS.length(), rightS.length()); 
     digits = (digits/2) + (digits % 2); 

     if (left.compareTo(new BigInteger("10", 10)) == -1 || right.compareTo(new BigInteger("10", 10)) == -1) { 
      return left.multiply(right); 
     } 

     BigInteger firstLeft = new BigInteger(leftS.substring(0, digits)); 
     BigInteger secondLeft = new BigInteger(leftS.substring(firstLeft.toString().length(), leftS.length())); 
     BigInteger firstRight = new BigInteger(rightS.substring(0, digits)); 
     BigInteger secondRight = new BigInteger(rightS.substring(firstRight.toString().length(), rightS.length())); 

     BigInteger z2 = resolve(firstLeft, firstRight); 
     BigInteger z0 = resolve(secondLeft, secondRight); 
     BigInteger z1 = resolve(firstLeft.add(secondLeft), firstRight.add(secondRight)).subtract(z2).subtract(z0); 

     return z2.multiply(BigInteger.valueOf((long) Math.pow(10, 2 * digits))) 
       .add(z1.multiply(BigInteger.valueOf((long) Math.pow(10, digits)))) 
       .add(z0); 
    } 

私は私がのために異なる長さのparameteresを使用していますので、それはだと思います例123と456789を参照してください。

Answer 1

NumberFormatExceptionはleft = 10とright = 100が、それ以来、あなたはこのような何かを得るとき、たとえばたまたま、new BigInteger("")によってスローされます。これは、文字列が空であるかどうかをチェックすることで修正するのは簡単です

digits = 2 
firstLeft = new BigInteger("10".substring(0,2)) = new BigInteger("10") 
secondLeft = new BigInteger("10".substring(2,2)) = new BigInteger("") 

をし、もしそうなら、私はアルゴリズムを実行しようとし、それを実行するが、A（実装）に問題が依然として存在するこの

BigInteger a = fromString(leftS.substring(0, digits)); 
    BigInteger b = fromString(leftS.substring(a.toString().length(),digits)); 
    BigInteger c = fromString(rightS.substring(0, digits)); 
    BigInteger d = fromString(rightS.substring(c.toString().length(), rightS.length())); 

... 

    private BigInteger fromString(String str) { 
     if (str.length() == 0) 
      return BigInteger.ZERO; 
     else 
      return new BigInteger(str); 
    } 

様例えば、ゼロに番号を設定しますアルゴリズムそのもの。たとえば、100 * 100が1000000と報告されています。これは分割がどのように行われるかに関係していると思いますが、完全に修正することはできませんでした。

m = 3でab = 12345を分割している場合、a = 123とb = 45になるコードで発生する方法です。

：あなたは（私は）Wikipediaの記事のオフに読んでいるなら、あなたは ab = a*10^(ab.length-m)+b

を持っているのに対し、

ab = a*10^m+b 

が、前者は、このようなコードを変更することにより、簡単に十分に達成することができることを必要とします

int l = leftS.length(); 
int r = rightS.length(); 
int m0 = Math.max(l, r); 
int r0 = m0%2; 
int m = (m0/2) + r0; 

... 

BigInteger a = fromString(leftS.substring(0, m-r0)); 
BigInteger b = fromString(leftS.substring(a.toString().length(),l)); 
BigInteger c = fromString(rightS.substring(0, m-r0)); 
BigInteger d = fromString(rightS.substring(c.toString().length(), r)); 

100 * 100 = 10000ですが、数字の桁数が異なる場合でも問題は残ります。私は間違ったものは見つけられませんでした。おそらく、エラーを見つけるためにアルゴリズムのすべてのステップを（ウィキペディアの疑似コードをコピーするのではなく）本当に行わなければならないでしょう。うまくいけば、これはまだいくつかの助けです！

さて、私はアルゴリズムがおそらく基底2でうまくいくと思います。なぜなら乗算のビットシフトを行うことができるからです。おそらく分裂は同様に同様に（そして速く）容易です。また、アルゴリズムは本当に大きな数にのみ有効なので、再帰はおそらくずっと早く停止する必要があります。それらはもちろん最適化ですが、私は彼らが言及する価値があると考えました。