BlogsDope image BlogsDope

Karatsuba Algorithm

July 23, 2020 C++ JAVA PYTHON ALGORITHM 2457

Given two numbers X and Y, calculate their multiplication using the Karatsuba Algorithm.
Input: X = “1234”, Y = “2345”
Output: Multiplication of x and y is 28,93,730.

Naive Method


The naive method is to follow the elementary school multiplication method, i.e. to multiply each digit of the second number with every digit of the first number and then add all the multiplication results.

  • C/C++
  • Python
  • Java
#include <string>
#include <iostream>
using namespace std;
int multiplication(int X, int Y)
{
    string x = to_string(X);
    string y = to_string(Y);
    int result = 0;

    // Looping over y
    for (int i = 0; i < y.length(); i++)
    {
        int carry = 0;         // intermediate carry
        string inter_res = ""; // intermediate result

        // Looping over x.
        for (int j = x.length() - 1; j >= 0; j--)
        {
            // intermediate multiplication of each digit and addition of carry.
            int num = (y[i] - '0') * (x[j] - '0') + carry;
            // if intermediate multiplication is of two digits and j>0
            //   then second digit is appended to intermediate result
            //and first digit is stored as carry
            if (num > 9 && j > 0)
            {
                inter_res = to_string(num % 10) + inter_res;
                carry = num / 10;
            }
            // else the digit is append to intermediate result
            //And assign carry as zero
            else
            {
                inter_res = to_string(num) + inter_res;
                carry = 0;
            }
        }
        // Adding the intermediate results

        result *= 10;
        result += stoi(inter_res);
    }
    return result;
}
int main()
{
    cout << multiplication(12, 5);
}
def multiplication(X, Y):
    # convert numbers into string
    x = str(X)
    y = str(Y)
    result = 0
    # looping over y
    for i in range(len(y)):
        carry = 0  # Intermediate carry
        inter_res = ""  # Intermediate result
        # looping over x
        for j in range(len(x) - 1, -1, -1):
            # intermediate multiplication of each digit and addition of carry
            num = int(y[i]) * int(x[j]) + carry
            # if intermediate multiplication is of two digits and j>0
            #   then second digit is appended to intermediate result
            #   and first digit is stored as carry
            if num > 9 and j > 0:
                inter_res = str(num % 10) + inter_res
                carry = num // 10
            # else the digit is append to intermediate result
            # And assign carry as zero
            else:
                inter_res = str(num) + inter_res
                carry = 0
        # Adding the intermediate results
        result *= 10
        result += int(inter_res)
    return result
public class MyClass {
  public static void main(String args[]) {
    System.out.println(multiplication(12, 5));
  }

  public static int multiplication(int X, int Y) {
    // Convert numbers into string
    String x = Integer.toString(X);
    String y = Integer.toString(Y);
    int result = 0;

    // Looping over y
    for (int i = 0; i < y.length(); i++) {
      int carry = 0; // intermediate carry
      String inter_res = ""; // intermediate result

      // Looping over x.
      for (int j = x.length() - 1; j >= 0; j--) {
        // intermediate multiplication of each digit and addition of carry.
        int num = Character.getNumericValue(y.charAt(i)) * Character.getNumericValue(x.charAt(j)) + carry;
        // if intermediate multiplication is of two digits and j>0
        // then second digit is appended to intermediate result
        // and first digit is stored as carry
        if (num > 9 && j > 0) {
          inter_res = Integer.toString(num % 10) + inter_res;
          carry = num / 10;
        }
        // else the digit is append to intermediate result
        // And assign carry as zero
        else {
          inter_res = Integer.toString(num) + inter_res;
          carry = 0;
        }
      }
      // Adding the intermediate results
      result *= 10;

      result += Integer.parseInt(inter_res);
    }
    return result;
  }
}

Therefore, the time complexity of the naive method is $O(n^2)$, where n is the number of digits.

Karatsuba Algorithm


The idea is to recursively divide an n-digit number into two halves (each half having half the digits) until they are small enough (having 1 digit) to be multiplied using the naive method. Consider two numbers X and Y having base m which are represented using the following equation,

$$X = m^{ceil(\frac{n}{2})}*a+b, Y = m^{ceil(\frac{n}{2})}*c+d$$

Here, the terms having ceil(n/2) will be more clear when you will see the implementation. So for simplicity purpose, you can take n as even for now.

The multiplication of X and Y is carried out in the following equations,

$$X*Y = (m^{ceil(\frac{n}{2})}*a+b) * (m^{ceil(\frac{n}{2})}*c+d)$$
$$\therefore X*Y = m^{2*ceil(\frac{n}{2})}(ad+bc)+bd$$

In the above equation, X and Y have n digits and a, b, c and d have n/2 digits each. There are four multiplications (ac, ad, bc, bd) of numbers having size n/2 (having number of digits equal to n/2). So basically, we divided our multiplication problem of size n into four sub-multiplications of size n/2. But still the time complexity of the recurrence relation formed $T(n) = 4T(\frac{n}{2}) + O(n)$ is $O(n^2)$. Therefore, the trick is to split the middle part of the above equation as shown below,

$$(ad+bc) = (a+b)(c+d) -ac -bd$$

As the multiplications ac and bd are already calculated in the equation (1), we reduced the multiplications ad and bc into one multiplication $(a+b)∗(c+d)$. Therefore, there are now three multiplications of size n/2 (having number of digits equal to n/2) and the recurrence relation formed is $T(n) = 3T(\frac{n}{2}) + O(n)$.

The resultant equation becomes as shown below,

$$X*Y = m^{2*ceil(\frac{n}{2})}*(ac) + m^{ceil(\frac{n}{2})}*((a+b)*(c+d)-ac-bd)+bd$$

Hence, the time complexity of the above recurrence using the Master’s Theorem is $O(n^{\log_2(3)})$ or $O(n^{1.59})$.

The above resultant equation is implemented in the following pseudocode for base-10 (m = 10),

1. The first step is to determine the maximum size (number of digits) of the input numbers which is achieved by converting the numbers into strings and calculating the length of the strings as shown below,
size = maximum(Length(string(X)), Length(string(Y)))

2. The next step is to divide X into (a and b) and Y into (c and d) such that their later parts (b and d) always get the extra digit in case the size (n) is odd,

n = ceil(size/2)
p = power(10,n) // equivalent to 10n
a = floor(X/p)
b = X%p
c = floor(Y/p)
d = Y%p

$X = m^{ceil(\frac{n}{2})}*a+b, Y = m^{ceil(\frac{n}{2})}*c+d$

For example, if X is 2023  and Y is 3003, then n = 2, p = 100, a = 20, b = 23, c = 30, d = 3.
Therefore, X = 102 * 20 + 23 and Y = 102 * 30 + 3

3. 

Now recur the above steps for further multiplication of the divided numbers at steps 1 and 2 until the base case is achieved i.e. when X and Y become less than 10.

// Here karatsuba is recurrence call.
ac = karatsuba(a,c)
bd = karatsuba(b,d)
e = karatsuba(a+c, b+d) - ac - bd

4. And the last step is to return the resultant equation as shown,
return power(10,2*n)*ac + power(10,n)*e + bd

PseudoCode:


Function karatsuba(X, Y){
	// base case
	If (X < 10 and Y < 10)
		return X*Y;

	// determine the size of numbers
	size = maximum(Length(string(X)), Length(string(Y)))


	// Split X and Y
n = ceil(size/2)
p = power(10,n) // equivalent to 10n
a = floor(X/p)
b = X%p
c = floor(Y/p)
d = Y%p

// Recur until base case
ac = karatsuba(a,c)
bd = karatsuba(b,d)
e = karatsuba(a+c, b+d) - ac - bd
	
	// Return the Multiplication
	return power(10,2*n)*ac + power(10,n)*e + b

}
  • C/C++
  • Python
  • Java
#include <stdio.h>
#include <math.h>

// Get size of the numbers
int getSize(long num)
{
    int count = 0;
    while (num > 0)
    {
        count++;
        num /= 10;
    }
    return count;
}

long karatsuba(long X, long Y)
{
    // Base Case
    if (X < 10 && Y < 10)
        return X * Y;

    // determine the size of X and Y
    int size = fmax(getSize(X), getSize(Y));

    // Split X and Y
    int n = (int)ceil(size / 2.0);
    long p = (long)pow(10, n);
    long a = (long)floor(X / (double)p);
    long b = X % p;
    long c = (long)floor(Y / (double)p);
    long d = Y % p;

    // Recur until base case
    long ac = karatsuba(a, c);
    long bd = karatsuba(b, d);
    long e = karatsuba(a + b, c + d) - ac - bd;

    // return the equation
    return (long)(pow(10 * 1L, 2 * n) * ac + pow(10 * 1L, n) * e + bd);
}
from math import ceil, floor


def karatsuba(X, Y):
    # Base case
    if X < 10 and Y < 10:
        return X * Y

    # determine the size of X and Y
    size = max(len(str(X)), len(str(Y)))

    # Split X and Y
    n = ceil(size // 2)
    p = 10 ** n
    a = floor(X // p)
    b = X % p
    c = floor(Y // p)
    d = Y % p

    # Recur until base case
    ac = karatsuba(a, c)
    bd = karatsuba(b, d)
    e = karatsuba(a + b, c + d) - ac - bd

    # return the equation
    return int(10 ** (2 * n) * ac + (10 ** n) * e + bd)
long karatsuba(long X, long Y)
    {
        // Base Case
        if(X<10 && Y<10)return X*Y;
        
        // determine the size of X and Y 
        int size = Math.max((Long.toString(X)).length(), (Long.toString(Y)).length());
        
        // Split X and Y
        int n = (int)Math.ceil(size/2.0);
        long p = (long)Math.pow(10,n);
        long a = (long)Math.floor(X/(double)p);
        long b = X%p;
        long c = (long)Math.floor(Y/(double)p);
        long d = Y%p;
        
        // Recur until base case
        long ac = karatsuba(a, c);
        long bd = karatsuba(b, d);
        long e = karatsuba(a+b, c+d) - ac - bd;
        
        // return the equation
        return (long)(Math.pow(10*1L, 2*n)*ac + Math.pow(10*1L, n)*e + bd);
    }
}

Liked the post?
Editor's Picks
0 COMMENT

Please login to view or add comment(s).