Stay up to date with notifications from The Independent

Notifications can be managed in browser preferences.

Mathematicians discover new way of multiplying large numbers

The findings may represent the 'fastest multiplication algorithm mathematically possible'

Chelsea Ritschel
Wednesday 17 April 2019 20:02 BST
Comments
Mathematicians on a new way of multiplying big numbers

Your support helps us to tell the story

From reproductive rights to climate change to Big Tech, The Independent is on the ground when the story is developing. Whether it's investigating the financials of Elon Musk's pro-Trump PAC or producing our latest documentary, 'The A Word', which shines a light on the American women fighting for reproductive rights, we know how important it is to parse out the facts from the messaging.

At such a critical moment in US history, we need reporters on the ground. Your donation allows us to keep sending journalists to speak to both sides of the story.

The Independent is trusted by Americans across the entire political spectrum. And unlike many other quality news outlets, we choose not to lock Americans out of our reporting and analysis with paywalls. We believe quality journalism should be available to everyone, paid for by those who can afford it.

Your support makes all the difference.

Mathematicians have reportedly discovered a new way of multiplying two numbers together.

The new technique is for really large numbers, and if it passes a peer-review, could be the fastest possible way of multiplying whole numbers.

According to the mathematicians, from Australia and France, long multiplication used to be the only way to multiply - but proved tedious and time-consuming when the numbers became too large.

Even for computers, the long multiplication algorithm, defined as n to the power of, could reportedly take months if each number had a billion digits.

But in a new paper published on the document archive HAL, David Harvey from the University of New South Wales and Joris van der Hoeven of the French national research agency CNRS and École Polytechnique in Palaiseau revealed that a new technique suggested years ago actually works.

The technique, the Schönhage–Strassen algorithm, which “predicted that there should exist an algorithm that multiples n-digit numbers using essentially n*log(n) basic operations,” according to Harvey, was suggested but never proved by German mathematicians.

The new paper proves that the technique is successful in cutting down the time it takes to multiply numbers, with billion-digit numbers theoretically multipled in under 30 seconds using the Schönhage-Strassen algorithm.

“Our paper gives the first known example of an algorithm that achieves this,” Harvey said. “People have been hunting for such an algorithm for almost 50 years. It was not a forgone conclusion that someone would eventually be successful.”

Of the revelation, mathematician and computer scientist Fredrik Johansson from INRIA Bordeaux and Institut de Mathématiques de Bordeaux told New Scientist: "If the result is correct, it's a major achievement in computational complexity theory. The new ideas in this work are likely to inspire further research and could lead to practical improvements down the road."

Support free-thinking journalism and attend Independent events

Unfortunately, the method likely won’t make all multiplying faster unless you are using really big numbers. In a FAQ section, the researchers asserted the technique was useful for numbers with more than 10^214857091104455251940635045059417341952 digits.

Join our commenting forum

Join thought-provoking conversations, follow other Independent readers and see their replies

Comments

Thank you for registering

Please refresh the page or navigate to another page on the site to be automatically logged inPlease refresh your browser to be logged in