title: Karatsuba Algorithm without BigInteger usage
body: <p>I have been trying to implement Karatsuba Algorithm in java without using BigInteger. My code is applicable only when both the integers are same &amp; have same number of digits. I do not get the correct answer however I get answer which is quite near to the right one. For instance I get 149 when 12*12. I can not figure out what is wrong with my code since I believe I have done everything right (by the book). Here's my code.</p>
  
  <pre><code>public static void main(String[] args) {
      long ans=karatsuba(12,12);
      System.out.println(ans);
  }
  
  private static long karatsuba(long i, long j) {
      if (i&lt;10 || j&lt;10){
          return i*j;
      }
      int n=getCount(i);
      long a=(long) (i/Math.pow(10, n/2));
      long b=(long) (i%Math.pow(10, n/2));
      long c=(long) (j/Math.pow(10, n/2));
      long d=(long) (j%Math.pow(10, n/2));
  
      long first=karatsuba(a,c);
      long second=karatsuba(b,d);
      long third=karatsuba(a+b,c+d);
  
      return ((long) ((first*Math.pow(10, n))+((third-first-second)*Math.pow(10,n/2))+third));
  }
  
  private static int getCount(long i) {
      String totalN=Long.toString(i);
      return totalN.length();
  }
  </code></pre>
  
  <p>EDIT:</p>
  
  <p>Thanks to Ziyao Wei, the problem was replacing "third" by "second". However I have another issue now which is:</p>
  
  <p>If karatsuba(1234,5678) is called I get the correct answer however when I call karatsuba(5678,1234) I do not get the right answer. Could anyone possibly know the reason for that? My updated code is:</p>
  
  <pre><code>public static void main(String[] args) {
      //wrong answer
      long ans=karatsuba(5678,1234);
      System.out.println(ans);
  
      //correct answer
      long ans1=karatsuba(1234,5678);
      System.out.println(ans1);
  }
  
  private static long karatsuba(long i, long j) {
      if (i&lt;10 || j&lt;10){
          return i*j;
      }
  
      int n=getCount(i);
  
      long a=(long) (i/Math.pow(10, n/2));
      long b=(long) (i%Math.pow(10, n/2));
      long c=(long) (j/Math.pow(10, n/2));
      long d=(long) (j%Math.pow(10, n/2));
  
      long first=karatsuba(a,c);
      long second=karatsuba(b,d);
      long third=karatsuba(a+b,c+d);
  
      return ((long) ((first*Math.pow(10, n))+((third-first-second)*Math.pow(10, n/2))+second));
  
  }
  </code></pre>
  
  <p>UPDATE:</p>
  
  <p><em>I have managed to round up value for "n/2" hence it solves the problem however if numbers more than four digits are used bugs occur. Here is my updated code:</em></p>
  
  <pre><code>public static void main(String[] args) {
      System.out.println(Math.round(5.00/2));
  
      //correct answer
      long ans=karatsuba(5678,1234);
      System.out.println(ans);
  
      //correct answer
      long ans1=karatsuba(1234,5678);
      System.out.println(ans1);
  
      //wrong answer
      long ans2=karatsuba(102456,102465);
      System.out.println(ans2);
  }
  
  
  private static long karatsuba(long i, long j) {
      if (i&lt;10 || j&lt;10){
          return i*j;
      }
  
      double n=Math.round(getCount(i));
  
      long a=(long) (i/Math.pow(10, Math.round(n/2)));
      long b=(long) (i%Math.pow(10, Math.round(n/2)));
      long c=(long) (j/Math.pow(10, Math.round(n/2)));
      long d=(long) (j%Math.pow(10, Math.round(n/2)));
  
      long first=karatsuba(a,c);
      long second=karatsuba(b,d);
  
      long third=karatsuba(a+b,c+d);
  
      return ((long) ((first*Math.pow(10, Math.round(n)))+((third-second-first)*Math.pow(10, Math.round(n/2)))+second));
  
  }
  
  private static double getCount(long i) {
      String totalN=Long.toString(i);
  
      return totalN.length();
  }
  </code></pre>
  
  <p>If somebody comes up with the solution for larger numbers (more than four digits) without using BigInteger then please do let me know. Thanks.</p>