Multiplying two very large integers with Karatsuba algorithm

So: what’s the product of the following two 64-digit numbers?

9251592653589793238462643383279502884197169399375105820974944456

8978281828459045235360287471352662497757247093699959574966967789

You are given two 64 digit numbers and are asked to find the result. Our grade school multiplication takes O(n2) time. We can do better than this using the Karatsuba multiplication technique. Googling Karatsuba will give you plenty explanations to this algorithm, so I won’t go into it here. I did find the example walkthrough in the slides from MIT highly useful in implementing the algorithm. (Link to those slides is here).

Below is how I implemented the Karatsuba multiplication algorithm recursively:

Click here to go to GitHub for below code

package algorithms;
import java.math.BigInteger;

public class Karatsuba {
    public static BigInteger karatsubaMultiply(BigInteger n, BigInteger m) {
    if (isSingle(n) && isSingle(m)) {
        return n.multiply(m);
    }
    int numAndSumOfN[] = getNumAndSumOfDigits(n);
    int numAndSumOfM[] = getNumAndSumOfDigits(m);
    BigInteger firstHalfN = n.divide(BigInteger.valueOf((long) Math.pow(10.0,(numAndSumOfN[0] / 2))));
    BigInteger secondHalfN = n.mod(BigInteger.valueOf((long) Math.pow(10.0,(numAndSumOfN[0] / 2))));

    BigInteger firstHalfM = m.divide(BigInteger.valueOf((long) Math.pow(10.0,(numAndSumOfM[0] / 2))));
    BigInteger secondHalfM = m.mod(BigInteger.valueOf((long) Math.pow(10.0,(numAndSumOfM[0] / 2))));

    BigInteger a = karatsubaMultiply(firstHalfN,firstHalfM);
    BigInteger d = karatsubaMultiply(secondHalfN, secondHalfM);
    // Note that numAndSumOfN[1] has the sum of digits at 1st index,
    // similarly for M
    // Below is same as finding e(i.e result) = [(Sum of firstHalfN + secondHalfN) * (Sum of firstHalfM + secondHalfM)]-a-d
    BigInteger e = karatsubaMultiply((firstHalfN.add(secondHalfN)),(firstHalfM.add(secondHalfM))).subtract(a).subtract(d);

    BigInteger aResult= a.multiply(BigInteger.valueOf((long) Math.pow(10, numAndSumOfN[0])));
    BigInteger eResult= e.multiply(BigInteger.valueOf((long) Math.pow(10,numAndSumOfN[0]/2)));
    //xy = a*10^n + e * r^n/2 + d
    return aResult.add(eResult).add(d);
    }

public static boolean isSingle(BigInteger n) {
    if (n.intValue() = 0)
    return true;
    return false;
    }

public static int[] getNumAndSumOfDigits(BigInteger n) {
    int numOfDigits = 0;
    int sumOfDigits = 0;

// Convert BigInteger to String and then count the digits and also sum
// of digits, faster than using mod 10
    String digits = n.toString();
    for (int i = 0; i < digits.length(); i++) {
    sumOfDigits += Character.getNumericValue(digits.charAt(i));
    numOfDigits++;
    }
    int[] numAndSum = { numOfDigits, sumOfDigits };
    return numAndSum;

    }

}

Now call the above karatsuba method in your main method:

package algorithms;
import java.math.BigInteger;

public class Main {
    public static void main(String[] args) {
        BigInteger n = new BigInteger("1234");
        BigInteger m = new BigInteger("4321");
        System.out.println(Karatsuba.karatsubaMultiply(n, m));
    }
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s