Content deleted Content added
m →Complexity: updated GMP base URL |
Cronholm144 (talk | contribs) clean up and/or add/rm math rating template using AWB |
||
Line 1:
The '''Karatsuba''' [[multiplication algorithm]], a technique for quickly multiplying large numbers, was discovered by 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>).
==Algorithm==
Line 115 ⟶ 114:
*[http://mathworld.wolfram.com/KaratsubaMultiplication.html Karatsuba Multiplication on MathWorld]
*Bernstein, D. J., "[http://cr.yp.to/papers/m3.pdf Multidigit multiplication for mathematicians]". Covers Karatsuba and many other multiplication algorithms.
[[Category:Arbitrary precision algorithms]]
| |||