# Karatsuba Multiplication.

The Karatsuba algorithm works by reducing a very large multiplication into several multiplications and additions of numbers much smaller than the originals. This significantly speeds up the processing when multiplying very large numbers.

Consider integers x and y where both are n digits in size (if they are not, then add zeros to the front of the smaller number to make it so). Letâ€™s also choose a number, m which is less than n. Then:

x = x_{1} x 10^{m} + x_{0} and x_{0} < 10^{m}

y = y_{1} x 10^{m} + y_{0} and 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_{0} + y_{1}) - 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_{0}y_{0}.

Hence

xy = x_{1}y_{1} x 10^{2m} + [(x_{1} + x_{0})(y_{0} + y_{1}) - x_{1}y_{1} - x_{0}y_{1}] x 10^{m}
+ x_{0}y_{0}

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. If m is chosen to be half of n then the multiplication takes place with numbers half the size of the original.

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 larger number. Let's pick m = 3, about one half of n. Then

x = 345 x 1000 + 678 where x_{1} = 345 and x_{0} = 678

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

So

x_{1}y_{1} = 1,035 x_{1}y_{0} = 301,875

x_{0}y_{0} = 593,250 x_{0}y_{1} = 2,034

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}

= (345 + 678) x (3 + 875) - 1,035 - 593,250 = 898,194 - 1,035 - 593,250 = 303,909

so xy = 1,035 x 10^{6} + 303,900 x 10^{3} + 593,250

= 1,035 x 1,000,000 + 303,909 x 1000 + 593,250 = 1,339,502,250

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

Now all this extra shifting and adding causes a bit of overhead for the computer so Karastuba multiplication isn't done for small numbers. In its implementation on this site, Karatsuba isn't invoked unless both numbers consist of at least 900 digits each.