Revision as of 21:15, 23 March 2007 edit 138.38.248.128 (talk) →Example: Delink 10 ← Previous edit		Revision as of 16:36, 26 March 2007 edit undo 82.20.51.169 (talk) Karatsuba's name Next edit →
Line 1: The '''Karatsuba''' [[multiplication algorithm]], a technique for quickly multiplying large numbers, was discovered by A.Anatolii Alexeevich Karatsuba and published together 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>).

Karatsuba algorithm: Difference between revisions