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₁ x 10^m + x₀      and x₀ < 10^m

y = y₁ x 10^m + y₀      and y₀ < 10^m

So

x y = (x₁ x 10^m + x₀) (y₁ x 10^m + y₀)

      = x₁y₁ x 10^2m + x₁y₀ x 10^m + x₀y₁ x 10^m + x₀y₀

      = x₁y₁ x 10^2m + (x₁y₀ + x₀y₁) x 10^m + x₀y₀

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

Now

x₁y₀ + x₀y₁ = (x₁ + x₀)(y₀ + y₁) - x₁y₁ - x₀y₀

which turns these two multiplications into three but two of them are the same as calculated above; namely x₁y₁ and x₀y₀.

Hence

xy = x₁y₁ x 10^2m + [(x₁ + x₀)(y₀ + y₁) - x₁y₁ - x₀y₁] x 10^m + x₀y₀

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₁ = 345 and x₀ = 678

y = 3 x 1000 + 875          where y₁ = 3 and y₀ = 875

So

x₁y₁ = 1,035                x₁y₀ = 301,875

x₀y₀ = 593,250            x₀y₁ = 2,034

and

x₁y₀ + x₀y₁ = (x₁ + x₀) (y₁ + y₀) - x₁y₁ - x₀y₀

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

so xy = 1,035 x 10⁶ + 303,900 x 10³ + 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.