Content deleted Content added
RolandIllig (talk | contribs) →Basic step: describe the tricky shortcut in more detail |
→top: I didn't want to get into this because I find this article indigestible, but it looks like this is OR so I'm removing it |
||
Line 23:
</ref><ref name="knuthV2">
Knuth D.E. (1969) ''[[The Art of Computer Programming]]. v.2.'' Addison-Wesley Publ.Co., 724 pp.
</ref> It is a [[divide-and-conquer algorithm]] that reduces the multiplication of two ''n''-digit numbers to three multiplications of ''n''/2-digit numbers and, by repeating this reduction, to at most <math> n^{\log_23}\approx n^{1.58}</math> single-digit multiplications. It is therefore [[Asymptotic complexity|asymptotically faster]] than the [[long multiplication|traditional]] algorithm, which performs <math>n^2</math> single-digit products
The Karatsuba algorithm was the first multiplication algorithm asymptotically faster than the quadratic "grade school" algorithm.
| |||