From University of New South Wales: “Maths whiz solves 48-year-old multiplication problem”

U NSW bloc

From University of New South Wales

04 Apr 2019
Lachlan Gilbert

A UNSW 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 demonstrating the old-school method of multiplication which is impractical when multiplying astronomically large numbers together. Picture: Natalie Choi/UNSW

A UNSW Sydney mathematician has helped solve a decades-old maths riddle that allows multiplication of huge numbers in a much faster time.

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

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.

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.

See the full article here .


Please help promote STEM in your local schools.

Stem Education Coalition

U NSW Campus

Welcome to UNSW Australia (The University of New South Wales), one of Australia’s leading research and teaching universities. At UNSW, we take pride in the broad range and high quality of our teaching programs. Our teaching gains strength and currency from our research activities, strong industry links and our international nature; UNSW has a strong regional and global engagement.

In developing new ideas and promoting lasting knowledge we are creating an academic environment where outstanding students and scholars from around the world can be inspired to excel in their programs of study and research. Partnerships with both local and global communities allow UNSW to share knowledge, debate and research outcomes. UNSW’s public events include concert performances, open days and public forums on issues such as the environment, healthcare and global politics. We encourage you to explore the UNSW website so you can find out more about what we do.