The multiplication of integers is a problem that has kept mathematicians busy since Antiquity. The “Babylonian” method we learn at school requires us to multiply each digit of the first number by each digit of the second one. But when both numbers have a billion digits each, that means a billion times a billion or 1018 operations.
At a rate of a billion operations per second, it would take a computer a little over 30 years to finish the job. In 1971, the mathematicians Schönhage and Strassen discovered a quicker way, cutting calculation time down to about 30 seconds on a modern laptop. In their article, they also predicted that another algorithm—yet to be found—could do an even faster job. Joris van der Hoeven, a CNRS researcher from the École Polytechnique Computer Science Laboratory LIX, and David Harvey from the University of New South Wales (Australia) have found that algorithm.
They present their work in a new article that is available to the scientific community through the online HAL archive. But one problem raised by Schönhage et Strassen remains to be solved: proving that no quicker method exists. This poses a new challenge for theoretical computer science.
Integer multiplication in time O(n log n). David Harvey, Joris van der Hoeven. Available on HAL : hal.archives-ouvertes.fr/hal-02070778
A faster method for multiplying very big numbers (2019, April 12)
retrieved 12 April 2019
This document is subject to copyright. Apart from any fair dealing for the purpose of private study or research, no
part may be reproduced without the written permission. The content is provided for information purposes only.