Multiplication Hits the Speed Limit

A paper posted online in March 2019 presents what may be essentially the fastest possible algorithm for one of the oldest problems in mathematics: whole number multiplication. The new algorithm, which can multiply two n-digit numbers in approximately n(logn) steps, breaks all previous records and reaches what mathematicians conjectured decades ago should be the fundamental speed limit for any multiplication procedure.

"This problem has been around since antiquity," said Joshua Cooper of the University of South Carolina in Columbia. "It's extraordinary to see the state of the art reach what people believe is the truth" about how fast multiplication can be carried out.