Revision as of 00:19, 5 April 2020 edit Veprolet (talk \| contribs) 3 edits Reverted pseudocode ← Previous edit		Revision as of 18:37, 26 May 2020 edit undo Gpear (talk \| contribs) 1 edit m I've changed the use of the word "classical" to "traditional" in the 3 places I found it. When discussing algorithms, classical usual refers to classical computers versus quantum computers, which is not the intended meaning here. It seems "traditional" is a more fitting word, although just directly referring to it as "long multiplication" might be clearest. Next edit →
Line 21: </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 faster than the [[long multiplication\|~~classical~~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 ~~classical~~traditional algorithm requires (2<sup>10</sup>)<sup>2</sup> = 1,048,576 (a speedup of 17.75 times). The Karatsuba algorithm was the first multiplication algorithm asymptotically faster than the quadratic "grade school" algorithm. Line 27: ==History== The standard procedure for multiplication of two ''n''-digit numbers requires a number of elementary operations proportional to <math>n^2\,\!</math>, or <math>O(n^2)\,\!</math> in [[big-O notation]]. [[Andrey Kolmogorov]] conjectured that the ~~classical~~traditional algorithm was ''[[asymptotically optimal]],'' meaning that any algorithm for that task would require <math>\Omega(n^2)\,\!</math> elementary operations. In 1960, Kolmogorov organized a seminar on mathematical problems in [[cybernetics]] at the [[Moscow State University]], where he stated the <math>\Omega(n^2)\,\!</math> conjecture and other problems in the [[Computational complexity theory\|complexity of computation]]. Within a week, Karatsuba, then a 23-year-old student, found an algorithm (later it was called "divide and conquer") that multiplies two ''n''-digit numbers in <math>O(n^{\log_2 3})</math> elementary steps, thus disproving the conjecture. Kolmogorov was very excited about the discovery; he communicated it at the next meeting of the seminar, which was then terminated. Kolmogorov gave some lectures on the Karatsuba result at conferences all over the world (see, for example, "Proceedings of the International Congress of Mathematicians 1962", pp. 351–356, and also

Karatsuba algorithm: Difference between revisions