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

logo