This is a way of doing multiplication of large numbers that I learned today. It allows the multiplication below complexity.

Consider the simple case of two multiple digit decimal numbers, written in the form of and for some positive integer . Then their product is

But we can find that so we can simply calculate the product by the algorithm below:

  1. Multiplication: and
  2. Addition: and
  3. Multiplication:
  4. Subtraction:
  5. Addition, with digit shifting:

So if each of are of digits, the naive multiplication will do single-digit multiplications. The Karatsuba method will do:

  1. single-digit multiplication
  2. single-digit addition
  3. single-digit multiplication
  4. single-digit subtraction, twice
  5. single-digit addition, twice

So a total of multiplications and addition/subtractions, which is an obvious reduction from multiplications. Recursive application gives a complexity of for multiplying two -digit numbers.

Generalizing the Karatsuba method, we can assume the two numbers are of the form and for a -ary number. But we need both and to be digits to apply this method.

If we do not only split a -digit number into two, like above, but numbers, then we have the Toom-Cook multiplication, of complexity where the complexity of addition of small constants, the time for sub-multiplication;

Reference