Karatsuba Algorithm for Multiplication

I came across a very simple and interesting way of performing 2 numerals multiplication when the length of the two numerals are of the same size. The algorithm is known as Karatsuba Algorithm for Multiplication.

The algorithm is as below:

When the numerals are of size n, perform the below:

1.     Split the numerals into 2 parts where each part is of size (n/2)

a.     Mark each part as a,b,c,d (See below for example)

2.   Apply the below equation

Let us look into how we achieved the above equation. In our example, we will use the below 2 numerals for multiplication

3456 * 5678 = ?

Splitting the numerals

Each of the numerals are of size 4. So the value of n=4 and the numerals must be split into half.

a = 34; b = 56; c = 56; d = 78

Applying the above-mentioned equation to the values, we get

 

The answer = 19623168 which is the same value as (3456 * 5678)

The above equation can be applied for 6 digits numerals where the n is 6 and each part will be split into 3 digits numerals. For example, 234567 * 345678

Each of the numerals are of size 6. So the value of n=4 and the numerals must be split into half.

a = 234; b = 567; c = 345; d = 678

Applying the above-mentioned equation to the values, we get

The answer = 81084651426 which is the same value as (234567 * 345678)

Deriving the equation

Let us 3456 * 5678 as an example to check how the above-mentioned equation is derived.

a = 34; b = 56; c = 56; d = 78 

Replacing the value of n,

Few additional thoughts:

The same logic can be applied for numerals of odd size or mismatched size by prefixing the numerals with 0s.

For example, 345 * 5678 can be converted to 0345 * 5678 and thereby making n as 4.