karatsuba算法错误

我做了karatsuba实现，但我有此错误：karatsuba算法错误

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.任何想法？

来源

2016-11-12 colymore

的NumberFormatException由new BigInteger("")抛出，当left = 10和right = 100，从那以后你得到这样的事情碰巧例如：

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

这是很容易通过，如果该字符串是空的检查改正，如果是这样，将数值设为零，例如像这样

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。但是，如果你阅读过维基百科文章的（我做了），你需要

ab = a*10^m+b

，而你有ab = a*10^(ab.length-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下可能会更好，因为那样你就可以为乘法做位移。可能分裂更容易（也更快），就像那样。此外，递归可能应该很快停止，因为该算法仅对真正大数量有效。这些当然是优化，但我认为他们值得一提。

来源

2016-11-13 00:06:03 Lidae

karatsuba算法错误

回答

相关问题