Free Republic Browse · Search General/Chat Topics · Post Article

Mathematicians Have Discovered an Entirely New Way to Multiply Large Numbers
Science Alert ^ | 10/17/19 | Peter Dockrill

Posted on 10/22/2019 2:00:33 AM PDT by LibWhacker

A pair of mathematicians from Australia and France have devised an alternative way to multiply numbers together, while solving an algorithmic puzzle that has perplexed some of the greatest math minds for almost half a century.

For most of us, the way we multiply relatively small numbers is by remembering our times tables – an incredibly handy aid first pioneered by the Babylonians some 4,000 years ago.

But what if the numbers get bigger? Well, if the figures get unwieldy – and assuming we don't have a calculator or computer, of course – most of us would then turn to long multiplication: another useful trick we learn in school, and a trusty technique for multiplying basically any two numbers together.

There's just one problem with long multiplication. It's slow.

The reason it's slow is because for every single digit in each number in the problem, you need to perform a separate multiplication operation, before adding all the products up.

This might not be a problem for you and me, who probably rarely resort to long multiplication ourselves. But it's a drawback school kids are familiar with, laboriously trudging through their calculations as they learn the magic of multiplication.

More significantly, it's a problem for computers, since their own bottlenecks in performing calculations are imposed by the limits of the abstract mathematics we ourselves can comprehend.

Basically, long multiplication is an algorithm, but it's just not a particularly efficient one, since the process is inevitably painstaking.

As it happens, mathematicians actually have a way of calculating just how painstaking long multiplication is.

As mathematician David Harvey from UNSW in Australia explains in the video below, in a multiplication where both the numbers have 3 digits (n = 3), the number of separate multiplication operations involved is actually 9, which is n2:

The problem with this is that as the numbers get bigger, the amount of work involved scales up too, always being represented by n to the power of 2.

While it's inefficient, the long multiplication algorithm was actually the most advanced multiplication algorithm we had until the 1960s, when Russian mathematician Anatoly Karatsuba discovered that n1.58 was possible.

A decade later, a pair of German mathematicians made another breakthrough: the Schönhage–Strassen algorithm, which conjectured – but never proved – that further refinements were possible, too.

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

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

According to the researchers, multiplying two numbers together with a billion digits each by the process of long multiplication would take a computer months to calculate.

Using the Schönhage-Strassen algorithm, it would take under 30 seconds, and with their theoretical proof, it would be even quicker – theoretically – and may even represent the fastest multiplication algorithm that's mathematically possible.

"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," Harvey says.

"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's worth noting the new algorithm would only ever be useful for multiplying very big numbers together. How big exactly?

"We have no idea," the researchers explain in an FAQ, although one example they give in the paper equates to 10214857091104455251940635045059417341952, which is a very, very, very big number.

The world's maths community is still absorbing the new findings, which have yet to be peer-reviewed, but are already making waves.

"I was very much astonished that it had been done," theoretical computer scientist Martin Fürer from Penn State University told Science News.

Fürer himself tried to revamp the Schönhage-Strassen algorithm over a decade ago, but eventually discontinued the work, telling Science News, "It seemed quite hopeless to me".

But hope has been restored, provided mathematicians can verify the work.

"If the result is correct, it's a major achievement in computational complexity theory," mathematician and computer scientist Fredrik Johansson from INRIA Bordeaux and Institut de Mathématiques de Bordeaux told New Scientist.

"The new ideas in this work are likely to inspire further research and could lead to practical improvements down the road."

Meanwhile, Harvey and his co-researcher, Joris van der Hoeven from École Polytechnique in France, say their algorithm needs to be optimised, and they're just hoping they haven't stuffed something up in their proof.

"A lot of the work was convincing ourselves that it's actually correct," Harvey told AAP. "I'm still terrified that it might turn out to be wrong."

TOPICS: Computers/Internet; Science
KEYWORDS: discover; math; mathematicians; method; multiplication; new
first 1-2021-4041-6061-68 next last

1 posted on 10/22/2019 2:00:33 AM PDT by LibWhacker

To: LibWhacker

If it takes a thousand years to prove a thesis that reduces the solution to a few minutes, what is gained?

2 posted on 10/22/2019 2:08:04 AM PDT by Louis Foxwell (A deep and terrible ignorance born of abject corruption is required to hate our president.)

To: Louis Foxwell
I wonder if they could solve Korman’s enigma? 😁
3 posted on 10/22/2019 2:12:07 AM PDT by Mark17 (Once saved, always saved. I do not care if some do not like that. It will NEVER be my problem)

To: LibWhacker

assuming you don’t have a calculator? I think its safe to say that less than 0.00000165 % of the population on the planet will ever reference this article for a simpler way to multiply numbers of such largess.

4 posted on 10/22/2019 2:13:13 AM PDT by mythenjoseph

To: Louis Foxwell

Think what the calculus has done for us. It took well over a thousand years to come up with it.

5 posted on 10/22/2019 2:19:53 AM PDT by LibWhacker

To: LibWhacker
one example they give in the paper equates to 10214857091104455251940635045059417341952, which is a very, very, very big number.

Actually, one of the smallest numbers there is. Admittedly, one the largest numbers you will ever encounter, but there are infinitely more numbers larger than it, and only a finite number smaller.

6 posted on 10/22/2019 2:24:13 AM PDT by Lonesome in Massachussets (Be vewy, vewy quiet. Adam Fudd is hunting Wussians!)

To: Louis Foxwell

I assume this means that computer algorithms will compute faster, meaning software can be written that is faster and more efficient, speeding computers up without boosting IP the hardware.

7 posted on 10/22/2019 2:25:22 AM PDT by sinsofsolarempirefan

To: mythenjoseph

Not to worry the DOE and colleges are grooming our children as activists and social justice warriors no need for math they already know 2+2=5

8 posted on 10/22/2019 2:39:27 AM PDT by ronnie raygun (nic dip.com)

To: LibWhacker; Chode
With a REALLY BIG PENCIL ✏️?
9 posted on 10/22/2019 2:43:58 AM PDT by mabarker1 ((Congress- the opposite of PROGRESS!A fraud,a hypocrite,a liar. I'm ,,! I a member of Congress)

To: sinsofsolarempirefan

One nightmare scenario is the ability to factor large numbers, where “large” means a number whose factorization would require a time scale comparable to a human lifetime or an economic cost much greater than the value of decryption. Decryption of military or financial messages can be very valuable. Breaking the Axis codes during World War II was literally worth billions of dollars, and at a small fraction of the cost.

Public key encryption depends on the fact that such factorization is impractical. There are murmurs that quantum computing could break this problem, but I do not understand quantum computing, and have not heard of any practical results (and why would I?). Multiplication might be used in brute force assaults, and suddenly high school kids could read top secret military transmissions.

10 posted on 10/22/2019 2:51:42 AM PDT by Lonesome in Massachussets (Be vewy, vewy quiet. Adam Fudd is hunting Wussians!)

To: Louis Foxwell

It can be applied empirically to speed up large number computations even in the absence of full theoretical proof.

11 posted on 10/22/2019 2:52:00 AM PDT by Rockingham

To: Rockingham

12 posted on 10/22/2019 2:57:48 AM PDT by usconservative (When The Ballot Box No Longer Counts, The Ammunition Box Does. (What's In Your Ammo Box?))

To: Lonesome in Massachussets

“If the result is correct...”.

There’s only one correct result to two numbers multiplied. How will they know it’s correct?

13 posted on 10/22/2019 3:38:35 AM PDT by Rennes Templar (Heaven has a wall and gates. Hell has open borders.)

To: LibWhacker

Another solution in search of a problem.

14 posted on 10/22/2019 3:52:41 AM PDT by aquila48 (Do not let them make you care!)

To: LibWhacker

Will it kill common core?

15 posted on 10/22/2019 4:05:36 AM PDT by FES0844

To: mabarker1
bigger than those grade school ones that's for sure
16 posted on 10/22/2019 4:14:51 AM PDT by Chode

To: Louis Foxwell
G = N (T - {M + 1,000Y})?

G = gain
N = number of times the calculation is made using the new method
T = time to calculate using the old method
M = a few minutes
Y = years

17 posted on 10/22/2019 4:18:55 AM PDT by Savage Beast (As Trump shines the Light of Truth, the Rats scurry for cover! It's funny to watch! MAGA!)

To: LibWhacker

Times tables were drilled into me by the Domican nuns. At my advanced age, I’m still pretty fast. As for no calculators or computers to aid in multiplication, I still can use my slide rule with good speed. Admittedly, it can’t be used for ALL multiplication and division, but it works.

BTW, does anyone still have theirs. Mine is a Sun Hemmi for Chemical Engineers (back side has atomic weights and numbers, plus temperature and pressure conversion scales. No log functions). Bought it in Hong Kong for \$5; cost in US was \$16 back in 1960.

18 posted on 10/22/2019 4:31:11 AM PDT by NTHockey (Rules of engagement #1: Take no prisoners. And to the NSA trolls, FU)

To: Rennes Templar
“If the result is correct...”.

If the proof is correct, if the resulting algorithms work. One could apply the results to problems that are practical to solve and check for consistency with methods currently in use. That still does not formally prove that the method is correct, any more than the observation that 3, 5 and 7 are all prime proves all odd numbers are prime, it only proves that we have not yet discovered any counterexamples.

19 posted on 10/22/2019 4:38:12 AM PDT by Lonesome in Massachussets (Be vewy, vewy quiet. Adam Fudd is hunting Wussians!)

To: Rennes Templar

Using long form

20 posted on 10/22/2019 4:38:45 AM PDT by libh8er