Karatsuba algorithm: Difference between revisions

Revision as of 02:48, 10 September 2006

Revision as of 07:04, 14 September 2006

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''²) algorithm, although for small numbers it is not as fast.