Integer Multiplication using Karatsuba algorithm

Normal Integer method
If we consider the integer multiplication, we need 2 integers and output is also integer.

Suppose we have to multiply 5678*1234. In the normal way, we will realize following:

  5678
X 1234
------------
  22712     //first number multiply as is i.e. 4*5678
 17034-     //2nd time, shift (left) and then multiply the number as 3*5678
11356--     //shift twice
5678---     //shift thrice
------------
7006652

So, each time we multiply, depending on the digit of the 2nd number, we shift and then multiply. Now, lets compute its time complexity.

For the first partial product, we got 22712 by multiplying 4*5678. So, we needed 4 basic operations(i.e. sum) and also we needed to take care of carries, which requires 2*4 operations at max. So, it requires at max 2n operations, depending on the number. So, for all the digits 2n² operations. Finally we have to add up these numbers, which will again require at max - 2n².
So, overall operations count <= constant.n² (constant like 4)

The algorithm designer's mantra - Perhaps the most important principle for the good algorithm designer is to refuse to be content. (By Aho, Hopcroft and Ullman - The design analysis of computer algorithms 1974)

So, is there a better method?

Karatsuba multiplication

So, first half of X is a, and so on.
X = 5678 = ab i.e. a = 56, b=78
Y = 1234 = cd i.e. c = 12, d = 34
n=4, as number of digits is 4 in both X and Y.

Algorithm:

Compute 1 = a.c
Compute 2 = b.d
Compute 3 = (a+b).(c+d)
Compute 4 = 3-2-1
Compute 5 = (1 * 10^n)+2 + (4*(10^(n/2))
5 is our answer.

Eg.
1 = 56*12 =  672
2 = 78*34 = 2652
3 =(56+78)*(12+34) =  6164
4 = 2840
5 =
672*10000
+2652
+6164*100
=7006652
which equal to our number.

Lets see if it does better than 3rd grade algorithms. Before we go into the details of Karatsuba algorithm, we have to see integer multiplication using recursive algorithms.

Recursive algorithm for 3rd grade algorithm
Write X = 10^n/2 a+b, Y = 10^n/2c+d
a,b,c,d are n/2 digit numbers and X and Y are n digit number.
example:a=56, b=78,c=12,d=34 for X being 5678 and Y being 1234.

X.Y = 10n a.c. + 10n/2 (ad+bc)+ bd

Idea : Recursively compute ac,ad,bc, and bd until and unless we find the base conditions. So, here we have to compute 4 items recursively. The 2nd term ad+bc is important but the individual term ad and bc are not, only the sum is important. So, lets see if we can address this i.e reducing 4 recursive calls to 3.

Recursive algorithm for Karatsuba algorithm

Now, lets refine this algorithm using Karatsuba algorithm
X.Y = 10n a.c. + 10n/2 (ad+bc)+ bd
So, in the last algorithm we needed 4 recursive calls, but we care more about ad+bc rather than ad and bc.

1. Recursively compute ac
2. Recursively compute bd
3. Recursively compute (a+b)(c+d) = ac+ad+bc+bd
Gauss's trick = 3 - 1 - 2 implies 3 gives us ad+bc

Upshot, only 3 recursive multiplication call. To, compute further we need understanding of master method. Time complexity of Karatsuba algorithm is O(n ^log₂3) i.e. O(n^1.59). Also, the normal recursion method takes O(n²). So, Karatsuba algorithm is much better.