Karatsuba algorithm: Difference between revisions

Revision as of 21:30, 8 June 2022

Revision as of 22:04, 8 June 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 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 requiresperforms <math>n^2</math> single-digit products. For example, the Karatsuba algorithm requires 3¹⁰ = 59,049 single-digit multiplications to multiply two 1024-digit numbers (''n'' = 1024 = 2¹⁰), whereas the traditional algorithm requires (2¹⁰)² = 1,048,576 (~17.758 times faster).

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

Line 35:

===Basic step===

The basic stepprinciple of Karatsuba's algorithm is [[Divide-and-conquer algorithm|divide-and-conquer]], using a formula that allows one to compute the product of two large numbers <math>x</math> and <math>y</math> using three multiplications of smaller numbers, each with about half as many digits as <math>x</math> or <math>y</math>, plus some additions and digit shifts. This basic step is, in fact, a generalization of [[Multiplication algorithm#Complex multiplication algorithm|a similar complex multiplication algorithm]], where the [[imaginary unit]] {{mvar|i}} is replaced by a power of the [[radix|base]].

Let <math>x</math> and <math>y</math> be represented as <math>n</math>-digit strings in some base <math>B</math>. For any positive integer <math>m</math> less than <math>n</math>, one can write the two given numbers as