# Integer multiplication analysis

The straightforward algorithm for multiplying 2 n-digit integers require n^2 multiplications and O(n) additions.

Total multiplications are 25:

12345
* 12345
-------
5 * 5 * 10^0
+     4 * 5 * 10^1
+     ...
+     1 * 5 * 10^4
+     ...
+     1 * (1 * 10^4) * (1 * 10^4)
-------

Hence, it runs in time $$O(n^{2})$$.

If we observe the following:

$$(10^m * a + b)(10^m c + d) = 10^{2m} a c + 10^m(a d + b c) + b d$$

We only need 3 m-digit numbers, $$ac$$, $$bd$$ and $$bd + bc$$.

We can get these with 3 multiplications, $$a*c$$, $$b*d$$, $$a*c + b * d - (a - b) * (c - d)$$

TODO: abstract to n-multiplications