This is a way of doing multiplication of large numbers that I learned today. It allows the multiplication below $$O(n^2)$$ complexity.

Consider the simple case of two multiple digit decimal numbers, written in the form of $$a\times 10^k+b$$ and $$c\times 10^k + d$$ for some positive integer $$k$$. Then their product is

$ac\times 10^{2k} + (ad+bc)\times 10^k + bd$

But we can find that $$(a+b)\times (c+d) = ac+ad+bc+bd$$ so we can simply calculate the product by the algorithm below:

1. Multiplication: $$ac$$ and $$bd$$
2. Addition: $$a+b$$ and $$c+d$$
3. Multiplication: $$(a+b)\times(c+d)$$
4. Subtraction: $$ad+bc = (a+b)(c+d) - ac - bd$$
5. Addition, with digit shifting: $$ac\times 10^{2k} + (ad+bc)\times 10^k + bd$$

So if each of $$a,b,c,d$$ are of $$k$$ digits, the naive multiplication will do $$(2k)^2$$ single-digit multiplications. The Karatsuba method will do:

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

So a total of $$3k^2$$ multiplications and $$10k$$ addition/subtractions, which is an obvious reduction from $$4k^2$$ multiplications. Recursive application gives a complexity of $$\Theta(n^{\log_2 3})$$ for multiplying two $$n$$-digit numbers.

Generalizing the Karatsuba method, we can assume the two numbers are of the form $$a\times p^k+b$$ and $$c\times p^k+d$$ for a $$p$$-ary number. But we need both $$b$$ and $$d$$ to be $$k$$ digits to apply this method.

If we do not only split a $$n$$-digit number into two, like above, but $$m\ge 2$$ numbers, then we have the Toom-Cook multiplication, of complexity $$\Theta(c(m)n^\epsilon)$$ where $$c$$ the complexity of addition of small constants, $$n^\epsilon$$ the time for sub-multiplication; $$\epsilon = \log(2m − 1) / \log(m)$$

## Reference 