Aussie maths whiz solves 48-year-old multiplication problem

  Last updated April 23, 2019 at 3:16 pm

Topics:  

A decades-old maths riddle has been solved to allow multiplication of huge numbers much faster. And no-one will ever do it better, they say.




A Sydney mathematician has cracked a maths problem that has stood for almost half a century which will enable computers to multiply huge numbers together much more quickly.


Associate Professor David Harvey, from UNSW’s School of Mathematics and Statistics, has developed a new method for multiplying together huge numbers, which is much faster than the familiar “long multiplication” method that we all learn at primary school.


“More technically, we have proved a 1971 conjecture of Schönhage and Strassen about the complexity of integer multiplication,” A/Professor Harvey says.


“They predicted that there should exist an algorithm that multiplies n-digit numbers using essentially n * log(n) basic operations.


“Our paper gives the first known example of an algorithm that achieves this.”


math maths long multiplication algorithm David Harvey

Associate Professor David Harvey demonstrating the old-school method of multiplication which is impractical when multiplying astronomically large numbers together. Picture: Natalie Choi/UNSW


Big numbers = big problems


In other words, if we were to multiply the numbers 314 by 159 with the usual primary school method, we would need to calculate 9 digit-by-digit products (see video). In general, if n represents the number of digits in each number, the answer can be arrived at in n2 operations.


Schönhage and Strassen themselves invented an algorithm needing fewer than n2 operations, but were unable to get it down to n * log(n).


Harvey says that the Schönhage-Strassen algorithm is already quite fast: a computer using the primary school method would take months to multiply two numbers with a billion digits, but can do it in under 30 seconds using the Schönhage-Strassen algorithm.


But for numbers with enough digits – billion, trillions or even gazillions – the new algorithm, developed by Harvey and his collaborator Joris van der Hoeven at École Polytechnique (France), would outrun even Schönhage and Strassen’s algorithm.


No-one will ever find a faster method


A/Professor Harvey says that Schönhage and Strassen also predicted that n * log(n) is the ‘best possible’ result – that no-one will ever find a faster multiplication algorithm.


“So in this sense, our work is expected to be the end of the road for this problem, although we don’t know yet how to prove this rigorously.”


While it’s still early days, A/Professor Harvey imagines that this breakthrough has an enormous number of consequences.


“It means you can do all sorts of arithmetic more efficiently, for example division and square roots. You could also calculate digits of pi more efficiently than before. It even has applications to problems involving huge prime numbers.”


A/Professor Harvey says he was surprised that such a fast multiplication algorithm is even possible.


“People have been hunting for such an algorithm for almost 50 years. It was not a forgone conclusion that someone would eventually be successful. It might have turned out that Schönhage and Strassen were wrong, and that no such algorithm is possible.


“But now we know better,” he says.


The work was posted recently online at HAL.


Related


Australian maths students being taught by out-of-field teachers


Honeybees can do maths


Rethinking how we teach maths in schools




About the Author

UNSW Newsroom
The latest and best news from the University of New South Wales.

Published By

Featured Videos

Placeholder
A future of nanobots in 180 seconds
Placeholder
Multi-user VR opens new worlds for medical research
Placeholder
Precision atom qubits achieve major quantum computing milestone
Placeholder
World's first complete design of a silicon quantum computer chip
Placeholder
Micro-factories - turning the world's waste burden into economic opportunities
Placeholder
Flip-flop qubits: a whole new quantum computing architecture
Placeholder
Ancient Babylonian tablet - world's first trig table
Placeholder
Life on Earth - and Mars?
Placeholder
“Desirable defects: Nano-scale structures of piezoelectrics” – Patrick Tung
Placeholder
Keeping Your Phone Safe from Hackers
Placeholder
Thru Fuze - a revolution in chronic back pain treatment (2015)
Placeholder
Breakthrough for stem cell therapies (2016)
Placeholder
The fortune contained in your mobile phone
Placeholder
Underwater With Emma Johnston
Placeholder
Flip-flop qubits: a whole new quantum computing architecture
Placeholder
The “Dressed Qubit” - breakthrough in quantum state stability (2016)
Placeholder
Pinpointing qubits in a silicon quantum computer (2016)
Placeholder
How to build a quantum computer in silicon (2015)
Placeholder
Quantum computer coding in silicon now possible (2015)
Placeholder
Crucial hurdle overcome for quantum computing (2015)
Placeholder
New world record for silicon quantum computing (2014)
Placeholder
Quantum data at the atom's heart (2013)
Placeholder
Towards a quantum internet (2013)
Placeholder
Single-atom transistor (2012)
Placeholder
Down to the Wire (2012)
Placeholder
Landmark in quantum computing (2012)
Placeholder
1. How Quantum Computers Will Change Our World
Placeholder
Quantum Computing Concepts – What will a quantum computer do?
Placeholder
Quantum Computing Concepts – Quantum Hardware
Placeholder
Quantum Computing Concepts – Quantum Algorithms
Placeholder
Quantum Computing Concepts – Quantum Logic
Placeholder
Quantum Computing Concepts – Entanglement
Placeholder
Quantum Computing Concepts - Quantum Measurement
Placeholder
Quantum Computing Concepts – Spin
Placeholder
Quantum Computing Concepts - Quantum Bits
Placeholder
Quantum Computing Concepts - Binary Logic
Placeholder
Rose Amal - Sustainable fuels from the Sun
Placeholder
Veena Sahajwalla - The E-Waste Alchemist
Placeholder
Katharina Gaus - Extreme Close-up on Immunity
Placeholder
In her element - Professor Emma Johnston
Placeholder
Martina Stenzel - Targeting Tumours with Tiny Assassins
Placeholder
How Did We Get Here? - Why are we all athletes?
Placeholder
How Did We Get Here? - Megafauna murder mystery
Placeholder
How Did We Get Here? - Why are we so hairy?
Placeholder
How Did We Get Here? - Why grannies matter
Placeholder
How Did We Get Here? - Why do only humans experience puberty?
Placeholder
How Did We Get Here? - Evolution of the backside
Placeholder
How Did We Get Here? - Why we use symbols
Placeholder
How Did We Get Here? - Evolutionary MasterChefs
Placeholder
How Did We Get Here? - The Paleo Diet fad
Placeholder
How Did We Get Here? - Are races real?
Placeholder
How Did We Get Here? - Are We Still Evolving?
Placeholder
How Did We Get Here? - Dangly Bits
Placeholder
Catastrophic Science: Climate Migrants
Placeholder
Catastrophic Science: De-Extinction
Placeholder
Catastrophic Science: Nuclear Disasters
Placeholder
Catastrophic Science: Storm Surges
Placeholder
Catastrophic Science: How the Japan tsunami changed science
Placeholder
Catastrophic Science: How the World Trade Centre collapsed
Placeholder
Catastrophic Science: Bushfires