History
The standard procedure for multiplication of two n-digit numbers requires a number of elementary operations proportional to, or in the big-O notation. In 1952, Andrey Kolmogorov conjectured that the classical algorithm was asymptotically optimal, meaning that any algorithm for that task would require elementary operations.
In 1960, Kolmogorov organized a seminar on mathematical problems in cybernetics at the Moscow State University, where he stated the conjecture and other problems in the 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 elementary steps, thus disproving the conjecture. Kolmogorov was very agitated about the discovery; he communicated it at the next meeting of the seminar, which was then terminated. Kolmogorov published the method in 1962, in the Proceedings of the USSR Academy of Sciences. The article had been written by Kolmogorov, possibly in collaboration with Yuri Ofman, but listed "A. Karatsuba and Yu. Ofman" as the authors. Karatsuba only became aware of the paper when he received the reprints from the publisher.
Read more about this topic: Karatsuba Algorithm
Famous quotes containing the word history:
“In history an additional result is commonly produced by human actions beyond that which they aim at and obtain—that which they immediately recognize and desire. They gratify their own interest; but something further is thereby accomplished, latent in the actions in question, though not present to their consciousness, and not included in their design.”
—Georg Wilhelm Friedrich Hegel (1770–1831)
“Don’t you realize that this is a new empire? Why, folks, there’s never been anything like this since creation. Creation, huh, that took six days, this was done in one. History made in an hour. Why it’s a miracle out of the Old Testament!”
—Howard Estabrook (1884–1978)
“Man watches his history on the screen with apathy and an occasional passing flicker of horror or indignation.”
—Conor Cruise O’Brien (b. 1917)