Content deleted Content added
m →References: +it: |
No edit summary |
||
Line 1:
The '''Karatsuba''' [[multiplication algorithm]], a technique for quickly multiplying large numbers, was discovered by Anatolii Alexeevich Karatsuba in 1960 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 7:
:''x'' = ''x''<sub>1</sub>''B''<sup>''m''</sup> + ''x''<sub>2</sub>
:''y'' = ''y''<sub>1</sub>''B''<sup>''m''</sup> + ''y''<sub>2</sub>
where ''x''<sub>2</sub> and ''y''<sub>2</sub> are less than ''B''<sup>''m''</sup>; it is easily seen that there is a unique representation. We now have
Line 52:
==References==
* A. Karatsuba and Yu Ofman, "Multiplication of Many-Digital Numbers by Automatic Computers." ''Doklady Akad. Nauk SSSR'' Vol. 145 (1962), pp. 293–294. Translation in ''Physics-Doklady'' 7 (1963), pp. 595–596.
* Karatsuba A. A. The complexity of computations // Proc. Steklov Inst. Math., 211, 169–183 (1995); translation from Trudy Mat. Inst. Steklova, 211, 186–202 (1995).
*[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]]
* [http://www.ccas.ru/personal/karatsuba/divcen.htm Karatsuba Multiplication on Fast Algorithms and the FEE]
[[de:Karatsuba-Algorithmus]]
| |||