Karatsuba Multiplication: Difference between revisions
Jump to navigation
Jump to search
[Next]
| Line 2: | Line 2: | ||
* [[Algorithms#q23wLp|Algorithms | Divide and Conquer]] | * [[Algorithms#q23wLp|Algorithms | Divide and Conquer]] | ||
=Time Complexity= | =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. | 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> = 2, so we are in [[Master_Method#Case_3|Case 3]] of the master theorem, and the running time is upper bound by O(n<sup>log<sub>b</sub>4</sup>)=O(n<sup>2</sub>), not better than the straightforward iterative algoritm. | ||
=TODO= | =TODO= | ||
Revision as of 18:38, 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 = 2, so we are in Case 3 of the master theorem, and the running time is upper bound by O(nlogb4)=O(n2), not better than the straightforward iterative algoritm.
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