CODEWITHSUNDEEP
javaalgorithmmathmultiplication
Khan
Khan

Reputation: 213

Karatsuba Algorithm without BigInteger usage

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.

Upvotes: 10

Views: 7263

Answers (9)

Ihor M.
Ihor M.

Reputation: 3148

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

}

Upvotes: 1

Achilles
Achilles

Reputation: 36

Instead of rounding off with Math.round(), I am adding 1 to the value of input size(the min of the # of digits in either x or y), if the input size is odd. For example if X = 127 & Y = 162, then input size is 3. Increment it by 1 to make it 4. Then, a = X/Math.pow(10,input_size/2) = 1. b = X%Math.pow(10,input_size/2) = 27. Similarly, c = 1 and d = 62. Now, if we calculate X*Y = (ac)*Math.pow(10,input_size)+(ad+bc)*Math.pow(10,input_size/2)+bd; it gives the correct answer. Just remember, we increment input size by 1 only when it's odd. The full implementation is here - https://github.com/parag-vijay/data_structures/blob/master/java/KaratsubaMultiplication.java

Upvotes: 0

Alexander Smirnov
Alexander Smirnov

Reputation: 141

/** Function to multiply two numbers **/
    public long multiply(long x, long y)
    {
        int size1 = getSize(x);
        int size2 = getSize(y);
        /** Maximum of lengths of number **/
        int N = Math.max(size1, size2);
        /** for small values directly multiply **/        
        if (N < 10)
            return x * y;
        /** max length divided, rounded up **/    
        N = (N / 2) + (N % 2);    
        /** multiplier **/
        long m = (long)Math.pow(10, N);

        /** compute sub expressions **/        
        long b = x / m;
        long a = x - (b * m);
        long d = y / m;
        long c = y - (d * N);
        /** compute sub expressions **/
        long z0 = multiply(a, c);
        long z1 = multiply(a + b, c + d);
        long z2 = multiply(b, d);          

        return z0 + ((z1 - z0 - z2) * m) + (z2 * (long)(Math.pow(10, 2 * N)));        
    }
    /** Function to calculate length or number of digits in a number **/
    public int getSize(long num)
    {
        int ctr = 0;
        while (num != 0)
        {
            ctr++;
            num /= 10;
        }
        return ctr;
    }

That is realization for BigInteger:

http://www.nayuki.io/res/karatsuba-multiplication/KaratsubaMultiplication.java

Upvotes: -1

Oleksii Duzhyi
Oleksii Duzhyi

Reputation: 1223

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.

Upvotes: 1

Lutz Lehmann
Lutz Lehmann

Reputation: 25972

You set i=a*B+b and j=c*B+d, where B=10^m and m=n/2. Then

i*j=B^2*(a*c)+B*(a*c+b*d-(a-b)*(c-d))+c*d

However, in half the cases B^2=10^(2m) is not equal to 10^n, since for odd n one has n=2*m+1, so in this case, B^2=10^(n-1).

So I would suggest to define once m=n/2 or better m=(n+1)/2, B=(long)Math.pow(10,m) and use it to compute a,b,c,d and in the final summation use the factor B*B.

Upvotes: 0

Sachin
Sachin

Reputation: 155

Here is the correct approach (your answer modified):

public class KaratsubaMultiplication {

public static void main(String[] args) {
    //correct answer
    long ans=karatsuba(234,6788);
    System.out.println("actual    " + ans);
    System.out.println("expected  " + 234*6788);

    long ans0=karatsuba(68,156);
    System.out.println("actual    " +ans0);
    System.out.println("expected  " + 68*156);

    long ans1=karatsuba(1234,5678);
    System.out.println("actual    " + ans1);
    System.out.println("expected  " + 1234*5678);

    long ans2=karatsuba(122,456);
    System.out.println("actual    " +ans2);
    System.out.println("expected  " + 122*456);

    long ans3=karatsuba(102456,102465);
    System.out.println("actual    " + ans3);
    System.out.println("expected  " + 102456l * 102465l);
}


private static long karatsuba(long i, long j) {
    if (i<10 || j<10){
        return i*j;
    }

    double n=Long.toString(i).length();


    long a=(long) (i/Math.pow(10, Math.floor(n/2d)));
    long b=(long) (i%Math.pow(10, Math.floor(n/2d)));
    long c=(long) (j/Math.pow(10, Math.floor(n/2d)));
    long d=(long) (j%Math.pow(10, Math.floor(n/2d)));

    long first=karatsuba(a,c);

    long second=karatsuba(b,d);

    long third=karatsuba(a+b,c+d);

    return (long) (
           (first * Math.pow(10, Math.floor(n/2d) * 2)) +
           ((third-second-first) * Math.pow(10, Math.floor(n/2))) +
           second
           );

}

}

Upvotes: 0

aka.nice
aka.nice

Reputation: 9362

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...

Upvotes: 2

Rincer
Rincer

Reputation: 23

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

where 

degree = floor(n/2)

no roundings, atleast that is what I know...

For example, 

normal: 5/2 = 2.5
floor: 5/2 = 2
round: 5/2 = 3

And therefore, what you do... 

round(n)

is not the same as 

2*floor(n/2)

That is what I think,

Regards

Upvotes: 0

zw324
zw324

Reputation: 27180

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)

Upvotes: 5

Related Questions