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

y = y₁ y 10^m + y₀   where 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, 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.

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

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

So

x₁y₁ = 1,035

x₀y₀ = 593,250

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

    = (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.