0

我正在做一个 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);
    }

我认为这是因为我使用了不同的长度参数，例如 123 和 456789。知道吗？

4

1 回答 1

0

由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-13T00:06:03.520 回答