Revision as of 21:21, 22 November 2006 edit Stevenj (talk \| contribs) Extended confirmed users 14,849 edits note that \log23 \approx 1.585 ← Previous edit		Revision as of 21:21, 22 November 2006 edit undo Stevenj (talk \| contribs) Extended confirmed users 14,849 edits m whoops Next edit →
Line 1: The '''Karatsuba''' [[multiplication algorithm]], a technique for quickly multiplying large numbers, was discovered by A. 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 classical [[Big O notation\|Θ]](''n''<sup>2</sup>) algorithm (<math>\~~log23~~log_23 \approx 1.585</math>), although for small numbers it is not as fast.

Karatsuba algorithm: Difference between revisions