title: Recursive Karatsuba multiplication not working?
body: <p>I'm trying to implement <a href="https://en.wikipedia.org/wiki/Karatsuba_algorithm" rel="nofollow">Karatsuba multiplication</a> through recursive calls. The code below should work, but I keep getting the wrong answer. Any thoughts? </p>
  
  <pre><code>    public static long karatsuba(long x, long y){
          //base case:
          if (x &lt; 10 || y &lt; 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);
      }
  </code></pre>
  
  <p>Here are a few test cases:</p>
  
  <p>1) karatsuba(1234,5678)  >>>  <em>6952652</em></p>
  
  <p>*should be  <em>7006652</em></p>
  
  <p>2) karatsuba(4589, 7831)  >>>  <em>34649459</em></p>
  
  <p>*should be  <em>35936459</em></p>
  
  <p>3) karatsuba(911, 482)  >>>  <em>44722</em></p>
  
  <p>*should be  <em>472842</em></p>