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