Multiplying two very large integers with Karatsuba algorithm

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



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

Leave a Reply

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

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

Google+ photo

You are commenting using your Google+ 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 )


Connecting to %s