# 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.”

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.

### About the Author

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

## Featured Videos

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