Karatsuba Multiplication: Difference between revisions
Jump to navigation
Jump to search
[Next]
| Line 1: | Line 1: | ||
=Internal= | =Internal= | ||
* [[Algorithms#q23wLp|Algorithms | Divide and Conquer]] | * [[Algorithms#q23wLp|Algorithms | Divide and Conquer]] | ||
=TODO= | |||
<font color=darkkhaki> | |||
* 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 ? | |||
</font> | |||
=Overview= | =Overview= | ||
Revision as of 17:39, 20 September 2021
Internal
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 ?
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(n2).
TODO