The First Algorithm for Multiplying (optimization of the consequence)

It is associated with the name of the Soviet and Russian mathematician Anatoly Karatsuba. In 1960, during or after Andrey Kolmogorov’s lecture, he came up with the idea that it is possible to optimize the existing algorithm for multiplying numbers. He found a way to multiply the numbers in 2n steps instead of n², suggesting instead of a large number of multiplications to spend a smaller number of additions and subtractions. The Karatsuba method made it possible to multiply numbers using only n^1,58 multiplications by a single number. Karatsuba method will require 165 trillion steps to multiply two numbers out of a billion characters. Its advantage is manifested, starting with numbers having at least 10 000 decimal digit.

The Second Algorithm for Multiplying (process optimization)

1971. Two German mathematicians Arnold Schönhage and Volker Strassen published a method allowing to multiply large numbers in n × log n × log(log n) small multiplications. They also suggested the existence of a more efficient algorithm that requires only n × log n multiplications by one sign. In 2007, the Swiss mathematician Martin Fuhrer of the University of Pennsylvania in the USA proposed an asymptotically faster method with the number of steps per sign n × log n × 2^log*n, where log*n is an iterated algorithm n.

The Third Algorithm for Multiplying (changing the cause, reaching a new level)

Over the past decade, mathematicians have found increasingly fast multiplication algorithms, each of which has gradually crept to the mark in n × log n, not quite reaching it. In March 2019, Harvey and van der Hoeven’s algorithm appeared. It proves that the multiplication can be carried out in n × log n steps by one sign.

“I was very much astonished that it had been done,” says theoretical computer scientist Martin Fürer of Penn State. He discovered another multiplication speedup in 2007, but gave up on making further improvements. “It seemed quite hopeless to me.” (from ScienceNews)

Summary

From publications in the media: “How such mathematical techniques can accelerate real calculations? According to Harvey, it would take about a month for a modern computer to multiply two numbers with a billion decimals. The application of the algorithm Cengage-Strassen will allow you to keep it to 30 seconds. And the algorithm, the method of construction of which offers Harvey himself, to cope with the task even faster.”

But for current tasks: “The best we can hope for is we’re three times faster,” van der Hoeven said. “It won’t be spectacular.”

“In physics you have important constants like the speed of light which allow you to describe all kinds of phenomena,” van der Hoeven said. “If you want to know how fast computers can solve certain mathematical problems, then integer multiplication pops up as some kind of basic building brick with respect to which you can express those kinds of speeds.”