Revision as of 00:38, 19 November 2007 edit CRGreathouse (talk \| contribs) Autopatrolled, Administrators 13,002 edits m SS may not be the fastest anymore ← Previous edit		Revision as of 00:56, 26 November 2007 edit undo Linas (talk \| contribs) 25,539 edits m wikilink Karatsuba Next edit →
Line 1: The '''Karatsuba''' [[multiplication algorithm]], a technique for quickly multiplying large numbers, was discovered by [[Anatolii Alexeevich Karatsuba]] in 1960 and published in the joint paper with Yu. Ofman in 1962. Its [[time complexity]] is [[Big O notation\|Θ]]<math>(n^{\log_23})</math>. This makes it faster than the [[long multiplication\|classical]] Θ(''n''<sup>2</sup>) algorithm (<math>\log_23 \approx 1.585</math>). ==Algorithm==

Karatsuba algorithm: Difference between revisions