Revision as of 00:25, 12 August 2006 edit CRGreathouse (talk \| contribs) Autopatrolled, Administrators 13,002 edits GMP reference to crossover complexity ← Previous edit		Revision as of 00:27, 12 August 2006 edit undo CRGreathouse (talk \| contribs) Autopatrolled, Administrators 13,002 edits m Grammar Next edit →
Line 1: The '''Karatsuba ~~multiplication~~''' [[multiplication algorithm]], a technique for quickly multiplying large ~~numbres~~numbers, was discovered by Karatsuba and Ofman in 1962. Its [[time complexity]] is [[Big O notation\|Θ]]<math>(n^{\log_23})</math>. This makes it faster than the classical [[Big O notation\|Θ]](''n''<sup>2</sup>) algorithm, although for small numbers it is not as fast.

Karatsuba algorithm: Difference between revisions