Eyeofpie Eyeofpie - 4 months ago 43
Java Question

Recursive Karatsuba multiplication not working?

I'm trying to implement Karatsuba multiplication through recursive calls. The code below should work, but I keep getting the wrong answer. Any thoughts?

public static long karatsuba(long x, long y){
//base case:
if (x < 10 || y < 10) return x * y;

//length of digits:
int xSize = String.valueOf(x).length();
int ySize = String.valueOf(y).length();
int N = Math.max(xSize, ySize);

//split each number in half (by length of digits):
long numX_hi = Long.valueOf((String.valueOf(x).substring(0, N/2)));
long numX_lo = Long.valueOf((String.valueOf(x).substring(N/2, xSize)));
long numY_hi = Long.valueOf((String.valueOf(y).substring(0, N/2)));
long numY_lo = Long.valueOf((String.valueOf(y).substring(N/2, ySize)));

//solve multiplications recursively:
long z0 = karatsuba(numX_lo,numY_lo);
long z1 = karatsuba((numX_hi+numX_lo),(numY_hi+numY_lo));
long z2 = karatsuba(numX_hi,numY_hi);

//answer:
return (long)(z2 * Math.pow(10,N)) + (long)((z1-z2-z0) * Math.pow(10,(N/2))) + (z0);
}


Here are a few test cases:

1) karatsuba(1234,5678) >>> 6952652

*should be 7006652

2) karatsuba(4589, 7831) >>> 34649459

*should be 35936459

3) karatsuba(911, 482) >>> 44722

*should be 472842

Answer

There are two distinct problems with your method.

Firstly, you should split starting from the last (least significant) digit, not the first. So if you've got these two numbers:

1234
567890

You currently split them like this:

123   4 (123*1000+4)
567 890 (567*1000+890)

This gets you the wrong result because 1234 != 123*1000+4

You should instead split them like this:

  1 234  (1*1000+234)
567 890  (567*1000+890)

The second error I discovered happens when you add things back together.

return  (long)(z2 * Math.pow(10,N))  +  (long)((z1-z2-z0) * Math.pow(10,(N/2)))  +  (z0);

Will return an incorrect result for odd Ns, as N/2 will be rounded up down and therefore N != ((N/2)*2)

I've combined the two fixes and now I get the correct results:

public static long karatsuba(long x, long y){
    //base case:
    if (x < 10 || y < 10) return x * y;

    //length of digits:
    int xSize = String.valueOf(x).length();
    int ySize = String.valueOf(y).length();
    int halfN     = Math.max(xSize, ySize) / 2; // store N/2 instead of N
    int splitX = xSize - halfN;  // count the split point from xSize down
    int splitY = ySize - halfN;  // count the split point from ySize down

    //split each number in half (by length of digits):
    long numX_hi = Long.valueOf((String.valueOf(x).substring(0, splitX)));
    long numX_lo = Long.valueOf((String.valueOf(x).substring(splitX)));
    long numY_hi = Long.valueOf((String.valueOf(y).substring(0, splitY)));
    long numY_lo = Long.valueOf((String.valueOf(y).substring(splitY)));

    //solve multiplications recursively:
    long z0 = karatsuba(numX_lo,numY_lo);
    long z1 = karatsuba((numX_hi+numX_lo),(numY_hi+numY_lo));
    long z2 = karatsuba(numX_hi,numY_hi);

    //answer:
    return  (long)(z2 * Math.pow(10,halfN*2))  +  (long)((z1-z2-z0) * Math.pow(10,halfN))  +  (z0);
}
Comments