Karatsuba Multiplication: Difference between revisions
Jump to navigation
Jump to search
[Next]
(→TODO) |
|||
| Line 1: | Line 1: | ||
=Internal= | =Internal= | ||
* [[Algorithms#q23wLp|Algorithms | Divide and Conquer]] | * [[Algorithms#q23wLp|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<sup>1</sup>) (d=1). a/b<sup>d</sup> = 4/2<sup>1</sup>, so we are in [[Master_Method#Case_3|Case 3]] of the master theorem. | |||
=TODO= | =TODO= | ||
<font color=darkkhaki> | <font color=darkkhaki> | ||
Revision as of 18:37, 21 September 2021
Internal
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(n1) (d=1). a/bd = 4/21, so we are in Case 3 of the master theorem.
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(n2).
TODO