# Karatsuba Algorithm

July 23, 2020 28963

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?
0 COMMENT