Ошибка алгоритма Карацубы

Question

Я делаю реализацию 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. Есть идеи?

Answer 1

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. Я думаю, что это связано с тем, как происходит разделение, но я не смог полностью это исправить. Вот некоторые размышления:

Если вы делите ab=12345 при m=3, то, как это происходит в коде, вы получаете 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, потому что тогда вы можете делать битовые сдвиги для умножений. Вероятно, раскол проще и быстрее. Кроме того, рекурсия, вероятно, должна быть остановлена ​​намного раньше, поскольку алгоритм эффективен только для действительно больших чисел. Это, конечно, оптимизация, но я решил, что стоит упомянуть.