So I want to run Karatsuba Algorithm without using class BigInteger in Java, so upon following the pseudo-code and this question, I came with the following code

public static long recKaratsuba(long i1, long i2){ if(i1<10 || i2<10) { return i1*i2 ; } long len = Math.round(Long.toString(Math.max(i1,i2)).length()); long N = Math.round(len/2) ; long b = (long) (i1% Math.pow(10, N)) ; long a = (long) (i1/ Math.pow(10,N)); long d = (long) (i2% Math.pow(10,N)) ; long c = (long) (i2/ Math.pow(10,N)); //System.out.println("a,b,c,d :" + a + b + c + d); long ac = recKaratsuba(a, c) ; long bd = recKaratsuba(b, d) ; long pos = recKaratsuba(a+b,c+d) ; return ((long)(bd + ac*Math.pow(10,len) + (pos -ac -bd)*Math.pow(10,N) )) ; }

Now, the problem with this is that it’s producing the wrong answer, 1234*5678 is giving 11686652, which should’ve been 7006652. As a beginner to Java and algorithms, I am unable to pinpoint the exact bug in this code, also I do realize that this program is very inefficient and doesn’t work for more than 4 digits (according to the linked question ). But this is intuitively what I came up with originally after learning the pseudo-code.

So my question is, what is the problem in my code and how do I execute the following algorithm without using the BigInteger method?

There are a few things i notice:

- Instead of
*i1*and*i2*maybe use*x*and*y* - Variables
*len*and*N*are int, not long - No need to round the maximum of the lengths of the string-representations: Lengths are ints, ints are whole numbers and cant be rounded
- No need to round the division by 2: Dividing a whole number will always result in a whole number (integer division is done)
- The error is in the return-statement:
`Math.pow(10, len)`

should be`Math.pow(10, 2 * N)`

instead, this is important if*N*is uneven - Avoid multiple identical calculations: especially
`Math.pow(10, N)`

The fixed code gives the correct results for all examples that i have tested.

public static long recKaratsuba2(long x, long y) { if (x < 10 || y < 10) { return x * y; } int len = Long.toString(Math.max(x, y)).length(); double den = Math.pow(10, len / 2); long a = (long) (x / den); long b = (long) (x % den); long c = (long) (y / den); long d = (long) (y % den); long ac = recKaratsuba2(a, c); long bd = recKaratsuba2(b, d); long pos = recKaratsuba2(a + b, c + d); return (long) (bd + den * (ac * den + (pos - ac - bd))); }

## Recent Comments