Content deleted Content added
wikilink binary splitting |
|||
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>). The Karatsuba algorithm can be considered to be the earliest example of a [[binary splitting algorithm]], or more generally, a [[divide and conquer algorithm]].
==Algorithm==
| |||