Two researchers have developed a new method for multiplying very large numbers. A potentially historic advance for IT.
Adaptation of the proportions of a recipe, calculation of percentages, solving of mathematical problems, computer programs … The multiplication is crucial in many domains. No wonder, then, that it is one of the four rudimentary algebraic operations taught at school — with addition, subtraction, and division. Now, in recent works, Joris van Der Hoeven of the Computer Science Laboratory of the École Polytechnique1 in Palaiseau (Essonne) and his Australian colleague David Harvey of the University of New South Wales have managed to develop a method to multiply faster whole numbers (without a comma). What “help to increase the computing speed of computers”, rejoices Joris van der Hoeven.
The incredible slowness of the classical method
“The new algorithm allows to multiply two 100-digit numbers in just 200 operations instead of 10,000”
To understand, let’s go back to the classical multiplication method learned at school. It consists in superimposing the two numbers to multiply, to multiply each digit of the first number by each digit of the second and to add the results.
Thus, to multiply two integers each formed by 3 digits, it takes 3×3 single-digit multiplications, ie 9 operations, plus an addition of the 9 results. For two 5-digit numbers each, 5×5, or 25 multiplications plus an addition of the results. More generally, for a number with n digits, this requires n×n, or n² multiplications. Thus, the larger the number multiplied, the greater the number of necessary operations.
“For two numbers of one billion digits each, it takes one billion times a billion multiplications or one billion billion (or 10¹⁸) steps. So if we assume that it takes a second to do a billion operations, as is the case for a current average computer, it ultimately requires a billion seconds, or… nearly 32 years!” Says Joris van der Hoeven. Hence the interest of developing faster techniques.
An original algorithm
In the past, several multiplication algorithms faster than the classical technique have already been designed. Notably, in 1971 the German mathematicians Arnold Schönhage and Volker Strassen arrived at a process which reduces the number of operations necessary to n×(log (n))× log(log (n)) .
“This advance has reduced the time of multiplication of two numbers of a billion digits each to about thirty seconds on a laptop today, against, for recall, more than 30 years”
says Joris van der Hoeven. Moreover, the algorithm of Arnold Schönhage and Volker Strassen is now used by most software to calculate with large numbers.
Schönhage and Strassen also predicted the existence of an even faster algorithm, which made it possible to multiply numbers into numbers in only n (log (n)) operations. “Our recent article gives the first known example of an algorithm that allows this,” says Joris Van Der Hoeven. The New Year to Ally-to-the-New-Year-to-the-Power-to-Buy — “multiplications, but also, and most importantly, additions and subtractions,” stresses the researcher — at Cx (nx (log n)), where C is a constant that depends on the speed of the machine performing the calculations. For example is C 1, Multiplication of Two Numbers with 10 digits would require 10 x log (10), or 10 operations; against 10 x 10, or 100 operations with the conventional technique. And the multiplication of two numbers at 100 digits, 200 operations rather than 10,000.
“If this new technique has been verified by experts — it has been confirmed by a major process of basic research in the field of computer complexity,” notes Fredrik Johansson, researcher at the Institute of Mathematics Bordeaux3.
Valid only for very large numbers
Problem: for now, the new method is no longer valid for large numbers, “with more than 20 billion billion digits,” Jorge van der Hoeven. Let astronomical numbers, difficult even to conceive! For comparison, the age of the universe is “only” 14 billion years… To understand ,the new method is no longer useful for simple multiplications of everyday life … and we will so, for example, fill out the tax return!
“We have a demonstrating to a self to one one either more short and a simple possible; This meant limiting very large numbers, says Joris Van Der Hoeven. That said, we expect to identify variants of the algorithm that can be applied to smaller numbers. “
What is mathematical research?
The new algorithm is expected to improve computing speed in some areas. “For example, in mathematics, calculate the innumerable decisions of the number Pi π ( (3,14159…), a constant involved in many formulas of mathematics, engineering, and physics”, says Joris Van Der Hoeven.
Note: last March Google has announced a new record, with the calculation of 31 000 billion decimals after the decimal point.
“Variants of our algorithm could also be implemented in software using the Fast Fourier Transform (FFT) algorithm, commonly used to process and interpret digitized signals in various fields: computer simulation, fluids, image processing, etc. Adds the computer scientist.
Will it ever be possible to discover an even faster algorithm? “Probably not: in 1971, Schönhage and Strassen predicted that the best possible result,” says Joris Van Der Hoeven, whose publication has been reduced to 6 articles on this topic.
“This time, unless we have a big surprise, we have surely put an end to this search.”
