Karatsuba Multiplication

Internal

• Algorithms | Divide and Conquer

Time Complexity

In absence of Gauss optimization, the naive recursive algorithm makes 4 recursive calls (a=4), each call on half of the problem (b=2). Upon the exit from recursion, the combine phase performs additions using a number of operations proportional to the size of the current problem, so the combine phase is O(n¹) (d=1). a/b^d = 4/2¹ = 2, so we are in Case 3 of the master theorem, and the running time is upper bound by O(n^log₂4)=O(n²), no better than the straightforward iterative algorithm.

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]