A faster method for multiplying very big numbers

numbers
Credit: CC0 Public Domain

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 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 science.


Explore further

We've found a quicker way to multiply really big numbers

More information: Integer multiplication in time O(n log n). David Harvey, Joris van der Hoeven. Available on HAL : hal.archives-ouvertes.fr/hal-02070778
Provided by CNRS
Citation: A faster method for multiplying very big numbers (2019, April 12) retrieved 15 December 2019 from https://phys.org/news/2019-04-faster-method-big.html
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.
21 shares

Feedback to editors

User comments