Does Karatsuba's recursive multiplication not work?

Question

I am 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 some 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 1

There are two different problems with your method.

First, you should split up, starting with the last (least significant) digit, not the first. So, if you have these two numbers:

 1234 567890 

You currently separate them as follows:

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

This will lead to an incorrect result, because 1234 != 123*1000+4

Instead, you should break them down as follows:

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

---

The second error I discovered occurs when you add things 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 N s, since N/2 will be rounded up down and, therefore, N != ((N/2)*2)

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