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:

- Multiplication: and
- Addition: and
- Multiplication:
- Subtraction:
- Addition, with digit shifting:

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

- single-digit multiplication
- single-digit addition
- single-digit multiplication
- single-digit subtraction, twice
- 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

- https://brilliant.org/wiki/karatsuba-algorithm/
- The picture below from https://www.wired.com/story/mathematicians-discover-the-perfect-way-to-multiply/ makes the method easy to understand