CODEWITHSUNDEEP
algorithmkaratsuba
colymore
colymore

Reputation: 12316

Karatsuba algorithm error

i'm doing a karatsuba implementation but i have this error:

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)

This is my method:

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);
    }

I think it's because i'm using different length parameteres for example 123 and 456789. Any idea?

Upvotes: 0

Views: 125

Answers (1)

Lidae
Lidae

Reputation: 318

The NumberFormatException is thrown by new BigInteger(""), which happens for example when left = 10 and right = 100, since then you get something like this:

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

This is easy enough to correct by checking if the Strings are empty, and if so, set the number to zero, for example like this

    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);
    }

I tried to run the algorithm and although it runs, there is still a problem with the (implementation of the) algorithm itself. For example, 100*100 is reported as 1000000. I think this is related to how the splitting occurs, but I wasn't able to completely fix it. Here are some reflections:

If you're splitting ab=12345 at m=3, the way it happens in the code you get a=123 and b=45. But if you're reading off of the wikipedia article (which I did), you need that 

ab = a*10^m+b

whereas you have ab = a*10^(ab.length-m)+b

The former can be accomplished easily enough by changing the code like this:

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));

Now 100*100 = 10000, but there are still problems when the number of digits are different. I couldn't find what's wrong though, probably would have to really go through every step of the algorithm (rather than just copying the wikipedia pseudocode) to find the error. Hopefully this is still of some help though!

As an aside, I think the algorithm will probably work better with base 2, because then you can do bitshifts for the multiplications. Probably the splitting is easier (and faster) like that as well. Also, the recursion should probably be stopped much sooner since the algorithm is only effective for really large numbers. Those are of course optimizations, but I figured they were worth mentioning.

Upvotes: 0

Related Questions