Karatsuba Multiplication

Consider integers **x** and **y** where **n** is the number of digits in the larger one.
Let’s also choose a number, **m** which is less than **n**. Then:

**x = x _{1} x 10^{m} + x_{0}** where

**x**

_{0}< 10^{m}**y = y _{1} y 10^{m} + y_{0}** where

**y**

_{0}< 10^{m}So

**x y = (x _{1} x 10^{m} + x_{0}) (y_{1} x 10^{m} + y_{0})**

**= x _{1}y_{1} x 10^{2m} + x_{1}y_{0} x 10^{m} + x_{0}y_{1} x 10^{m} + x_{0}y_{0}**

**= x _{1}y_{1} x 10^{2m} + (x_{1}y_{0} + x_{0}y_{1}) x 10^{m} + x_{0}y_{0}**

This requires four multiplications where each multiplication is of numbers having fewer digits than the original n.

Now

**x _{1}y_{0} + x_{0}y_{1} = (x_{1} + x_{0}) (y_{1} + y_{0}) – x_{1}y_{1} – x_{0}y_{0}**

which turns these two multiplications into three but two of them are the same as calculated above; namely **x _{1}y_{1}** and

**x**. Hence, we end up calculating the original x times y with three other multiplications plus a few additions. But note that each of these multiplications takes place between numbers having fewer digits than the original.

_{0}y_{0}An example may help solidify this in your mind.

**x** = 345,678

**y** = 3,875

here **n** is 6, the number of digits in the largest number. Let’s pick **m** = 3, about one half of **n**. Then

**x** = 345 x 1000 + 678 where **x _{1}** = 345 and

**x**= 678

_{0}**y** = 3 x 1000 + 875 where **y _{1}** = 3 and

**y**= 875

_{0}So

**x _{1}y_{1}** = 1,035

**x _{0}y_{0}** = 593,250

and **x _{1}y_{0} + x_{0}y_{1} = (x_{1} + x_{0}) (y_{1} + y_{0}) – x_{1}y_{1} – x_{0}y_{0} = x_{1}y_{1} x 10^{2m} + (x_{1}y_{0} + x_{0}y_{1}) x 10^{m} + x_{0}y_{0}**

= (1,023)(878) – 1,035 – 593,250 = 303,909

So **xy** = 1,035 x 1,000,000 + 303,900 x 1,000 + 593,250 = 1,229,502,250

Using a power of 10 means that instead of multiplying, we are simply shifting left and inserting zeros.

Additional information about the Karatsuba algorithm can be found here on Wikipedia.