Karatsuba Algorithm without BigInteger usage

Question

I have been trying to implement Karatsuba Algorithm in java without using BigInteger. My code is applicable only when both the integers are same & 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.

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<10 || j<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();
}

EDIT:

Thanks to Ziyao Wei, the problem was replacing "third" by "second". However I have another issue now which is:

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:

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<10 || j<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));

}

UPDATE:

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:

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<10 || j<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();
}

If somebody comes up with the solution for larger numbers (more than four digits) without using BigInteger then please do let me know. Thanks.

Answer 1

You formula is wrong.

first * Math.pow(10, n) + (third - first - second) * Math.pow(10, n / 2) + third

is wrong, the formula should be

first * Math.pow(10, n) + (third - first - second) * Math.pow(10, n / 2) + second

Wikipedia:

z0 = karatsuba(low1,low2)
z1 = karatsuba((low1+high1),(low2+high2))
z2 = karatsuba(high1,high2)
return (z2*10^(m))+((z1-z2-z0)*10^(m/2))+(z0)

Answer 2

The last bug is that round(n) should be 2*round(n/2). They obviously differ for odd n.

Concerning int n=getCount(i); it's a source of dissymetry, so it should be changed.
For efficiency it should not be replaced by max(getCount(i),getCount(j)) as I read in a comment above, but rather with min.
Indeed, Karatsuba only makes sense when splitting well balanced numbers.
Try and decompose the operations performed with max and min to be sure...

Answer 3

Finally, after several hours of thinking I've found right solution:

public static long karatsuba(long i, long j) {
    if (i < 10 || j < 10) {
        return i * j;
    }
    double n = Math.round(getCount(i));
    if (n % 2 == 1) {
        n++;
    }
    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, n)) + ((third - first - second) * Math.pow(10, Math.round(n / 2))) + second));
}

I can't explain why n can't be odd, but right now multiplication is working correctly for the bunch of tests I've written. I will explain this behavior as soon as I'll find out.

Update: I'm taking Algorithms: Design and Analysis, Part 1 course on coursera, and posted a question about this behavior. Here is an answer by Andrew Patton:

As mentioned elsewhere, the key with breaking up the inputs is to make sure that b and d are the same length, so that a and c have the same power of 10 as coefficients. Whatever that power is becomes your n/2; ... So, the value of the n in 10^n is not actually the total length of your inputs, but rather n/2*2.

So in case of 3 digit number following you example:

n = 3;   
n/2 = 2;
n != n/2 * 2;

So n should be equal n/2 * 2 = 4 in this example.

Hope this make sense.

Answer 4

Here is the correct implementation using longs:

import java.util.Scanner;

/**
 * x=5678 y=1234
 * 
 * a=56,b=78
 * 
 * c=12,d=34
 * 
 * step 0 = m = n/2 + n%2
 * 
 * step 1 = a*c
 * 
 * step 2 = b*d
 * 
 * step 3 = (a + b)*(c + d)
 * 
 * step 4 = 3) - 2) - 1)
 * 
 * step 5 = 1)*pow(10, m*2) + 2) + 4)*pow(10, m)
 *
 */
public class Karatsuba {

    public static void main(String[] args) {
        long x, y;
        try (Scanner s = new Scanner(System.in)) {
            x = s.nextLong();
            y = s.nextLong();
        }
        long result = karatsuba(x, y);
        System.out.println(result);
    }

    private static long karatsuba(long x, long y) {
        if (x < 10 && y < 10)
            return x * y;

        int n = Math.max(Long.valueOf(x).toString().length(), (Long.valueOf(y).toString().length()));
        int m = n / 2 + n % 2;

        long a = x / (long) Math.pow(10, m);
        long b = x % (long) Math.pow(10, m);
        long c = y / (long) Math.pow(10, m);
        long d = y % (long) Math.pow(10, m);
        long step1 = karatsuba(a, c);
        long step2 = karatsuba(b, d);
        long step3 = karatsuba(a + b, c + d);
        long step4 = step3 - step2 - step1;
        long step5 = step1 * (long) Math.pow(10, m * 2) + step2 + step4 * (long) Math.pow(10, m);
        return step5;
    }

}

Using BigIntegers:

import java.math.BigInteger;
import java.util.Scanner;

/**
 * x=5678 y=1234
 * 
 * a=56,b=78
 * 
 * c=12,d=34
 * 
 * step 0 = m = n/2 + n%2
 * 
 * step 1 = a*c
 * 
 * step 2 = b*d
 * 
 * step 3 = (a + b)*(c + d)
 * 
 * step 4 = 3) - 2) - 1)
 * 
 * step 5 = 1)*pow(10, m*2) + 2) + 4)*pow(10, m)
 *
 */
public class Karatsuba {

    public static void main(String[] args) {
        BigInteger x, y;
        try (Scanner s = new Scanner(System.in)) {
            x = s.nextBigInteger();
            y = s.nextBigInteger();
        }
        BigInteger result = karatsuba(x, y);
        System.out.println(result);
    }

    private static BigInteger karatsuba(BigInteger x, BigInteger y) {
        if (x.compareTo(BigInteger.valueOf(10)) < 0 && y.compareTo(BigInteger.valueOf(10)) < 0)
            return x.multiply(y);

        int n = Math.max(x.toString().length(), y.toString().length());
        int m = n / 2 + n % 2;

        BigInteger[] a_b = x.divideAndRemainder(BigInteger.valueOf(10).pow(m));
        BigInteger a = a_b[0];
        BigInteger b = a_b[1];
        BigInteger[] c_d = y.divideAndRemainder(BigInteger.valueOf(10).pow(m));
        BigInteger c = c_d[0];
        BigInteger d = c_d[1];

        BigInteger step1 = karatsuba(a, c);
        BigInteger step2 = karatsuba(b, d);
        BigInteger step3 = karatsuba(a.add(b), c.add(d));
        BigInteger step4 = step3.subtract(step2).subtract(step1);
        BigInteger step5 = step1.multiply(BigInteger.valueOf(10).pow(m * 2)).add(step2)
                .add(step4.multiply(BigInteger.valueOf(10).pow(m)));
        return step5;
    }

}