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:
“You that would judge me do not judge alone
This book or that, come to this hallowed place
Where my friends’ portraits hang and look thereon;
Ireland’s history in their lineaments trace;
Think where man’s glory most begins and ends
And say my glory was I had such friends.”
—William Butler Yeats (1865–1939)
“While the Republic has already acquired a history world-wide, America is still unsettled and unexplored. Like the English in New Holland, we live only on the shores of a continent even yet, and hardly know where the rivers come from which float our navy.”
—Henry David Thoreau (1817–1862)
“The thing that struck me forcefully was the feeling of great age about the place. Standing on that old parade ground, which is now a cricket field, I could feel the dead generations crowding me. Here was the oldest settlement of freedmen in the Western world, no doubt. Men who had thrown off the bands of slavery by their own courage and ingenuity. The courage and daring of the Maroons strike like a purple beam across the history of Jamaica.”
—Zora Neale Hurston (1891–1960)