Content deleted Content added
rephrase |
+times |
||
Line 22:
</ref><ref name="knuthV2">
Knuth D.E. (1969) ''[[The Art of Computer Programming]]. v.2.'' Addison-Wesley Publ.Co., 724 pp.
</ref> It reduces the multiplication of two ''n''-digit numbers to at most <math> n^{\log_23}\approx n^{1.58}</math> single-digit multiplications in general (and exactly <math>n^{\log_23}</math> when ''n'' is a power of 2). It is therefore [[Asymptotic complexity|asymptotically faster]] than the [[long multiplication|traditional]] algorithm, which requires <math>n^2</math> single-digit products. For example, the Karatsuba algorithm requires 3<sup>10</sup> = 59,049 single-digit multiplications to multiply two 1024-digit numbers (''n'' = 1024 = 2<sup>10</sup>), whereas the traditional algorithm requires (2<sup>10</sup>)<sup>2</sup> = 1,048,576 (~17.758 times faster).
The Karatsuba algorithm was the first multiplication algorithm asymptotically faster than the quadratic "grade school" algorithm.
| |||