Karatsuba Multiplication

Internal

• Algorithms | Divide and Conquer

Overview

Karatsuba multiplication is an integer multiplication algorithm that takes two integer of n digits. The straightforward iterative solution involves multiplying the first integer with each digit of the second integer, shifting and adding the results, so it involves at least two n loop, for a O(n²) time complexity. A naive recursive solution in absence of the Gauss optimization involves dividing each integer M and N in two halves M = [A B], N=[C D], recursively computing AD, BD, AC and CB, shifting and adding. Applying master theorem, the number of subproblems is 4 (a=4), the size of the subproblem is n/2 (b=2) and the amount of work required to combine the solutions after the recursive call is O(n¹) so d=1. a/b^d = 4/2¹ = 2, we find ourselves in the Case 3 of the master theorem, where the number of subproblems proliferate more rapidly than the shrinkage of work per subproblem, so the asymptotic running time bound is O(n^log_ba) = O(n²), no better than the straightforward iterative method.

Gauss Optimization

Assuming that we divide each integer in two halves, as in the naive recursive method M = [A B], N = [C D], Gauss optimization consists in observing that:

(A + B)(C + D) = AC + AD + BC + BD

The subproducts required to compute M * N are:

         A B
         C D
     ─────
       AD BD +
  AC BC

which is:

 10n AC + 10n/2 (AD + BC) + BD 

So if we compute AC, BD and (A+B)(C+D), we can compute (AD + BC) = (A+B)(C+D) - AC - BD = AC + AD + BC + BD - AC - BD = AD + BC

Time Complexity

If we apply the Gauss optimization, we reduce the number of recursive calls to 3 (a=3), the rest of the parameters remaining the same. a/b^d = 3/2¹ > 1, so we are also in Case 3 of the master theorem, and the running time complexity is O(n^log₂3)=O(n^{log 3}), which is better than O(n²).

TODO

• problem statement
• naïve solution
• Gauss trick
• complexity
• Karatsuba: explain the key idea – apply the master theorem to demonstrate that the complexity is still O(n2). The key insight for Karatsuba algorithm is the Gauss’ trick to reduce four sub-parts recursive multiplications to 3, and the complexity is ?

Link to Strassen.

Overview

Apply the Gauss' trick and end up with three recursive calls instead of four. This yields a O(n*logn) complexity. It if was four, the recursive complexity it would have been O(n²).

TODO

Playground

https://github.com/ovidiuf/playground/tree/master/learning/stanford-algorithms-specialization/01-karatsuba

[Next]