Karatsuba Multiplication: Difference between revisions

From NovaOrdis Knowledge Base
Jump to navigation Jump to search
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

Playground

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