Karatsuba algorithm: Difference between revisions

Revision as of 11:06, 27 June 2022

Revision as of 05:50, 30 August 2022

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 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. For example, the Karatsubatraditional algorithm requires 3(2¹⁰)² = 591,049048,576 single-digit multiplications to multiply two 1024-digit numbers (''n'' = 1024 = 2¹⁰), whereas the traditionalKaratsuba algorithm requires (23¹⁰)² = 159,048,576049 thus being (~17.758 times faster).

The Karatsuba algorithm was the first multiplication algorithm asymptotically faster than the quadratic "grade school" algorithm.