Posted on 10/21/2019 2:51:31 PM PDT by Red Badger
Because the method you learned in middle school is ridiculously slow.
Multiplying large numbers is hard. In 1971, two German professors predicted an algorithm that would make it easier, but no one ever proved it. Until now. Mathematicians from Australia and France say their algorithm can make multiplication and other kinds of arithmetic much more efficient.
================================================================
From grade school onward, complex multiplication has been a headache. But an assistant professor from the University of New South Wales Sydney in Australia has developed a new method for multiplying giant numbers together that's more efficient than the "long multiplication" so many are taught at an early age.
“More technically, we have proved a 1971 conjecture of Schönhage and Strassen about the complexity of integer multiplication,” associate professor David Harvey says in the video below.
VIDEO AT LINK
The Schönhage–Strassen algorithm, developed by two German mathematicians, was actually the fastest method of multiplication from 1971 through 2007. Although a faster method was developed in 2007, it's rarely used today.
Schönhage and Strassen predicted that an algorithm multiplying n-digit numbers using n * log(n) basic operations should exist, Harvey says. His paper is the first known proof that it does.
Harvey picks the example of 314 multiplied by 159—a large equation, sure, but much larger ones are used every day in real-life scenarios. To solve the problem, most people are taught to multiply each individual number together, and then add up the sums:
9 is multiplied by 4, 1, and 3; then 5 is multiplied by 4, 1, and 3, and so on. The result ends up with 9 digit-by-digit products.
This method is called n2 or n squared, because one must multiple n by n a number of times. It will get the correct answer, but Schönhage and Strassen designed a faster method. It was able to move beyond n2 and into something smaller, but a challenge still presented itself in the form of n * log(n).
For some, seeing a word in the middle of a math problem might be enough to make their eyes glaze over like they did in algebra class. As a refresher: log is short for logarithm, which helps people decipher exponents that make numbers squared or cubed or even something higher. So 2⁵ is 32, but expressed logarithmically, it would look like log₂(32)=5. While it may seem like a mouthful, logarithms are crucial when numbers get much larger.
The Schönhage-Strassen method is very fast, Harvey says. If a computer were to use the squared method taught in school on a problem where two numbers had a billion digits each, it would take months. A computer using the Schönhage-Strassen method could do so in 30 seconds.
But if the numbers keep rising into the trillions and beyond, the algorithm developed by Harvey and collaborator Joris van der Hoeven at École Polytechnique in France could find solutions faster than the 1971 Schönhage-Strassen algorithm.
“It means you can do all sorts of arithmetic more efficiently, for example division and square roots," he says. "You could also calculate digits of pi more efficiently than before. It even has applications to problems involving huge prime numbers.
“People have been hunting for such an algorithm for almost 50 years," he continues. 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.
Faster than I can punch the numbers into a calculator?
So he knew how to multiply. How fast, I don't know. If spread out evenly over his adult life that would be only about 9 kids a year.
“Faster than I can punch the numbers into a calculator?”
You didn’t read the article!
This same method came to me in 10th grade in 1972, in an epiphany. I showed my teacher, but we were entering the period of calculators so it was useless.
Is it faster than The Trachtenberg Speed of speed math? Remember all those ads in magazines back in the 1960s?
Schönhage–Strassen algorithm
https://en.wikipedia.org/wiki/Sch%C3%B6nhage%E2%80%93Strassen_algorithm
It’s not a very clear explanation.
I figured it out though.
The fastest multiplication is done by illegals.
Too bad he doesn’t demonstrate it. We’d all like to see how fast it works.
Augustus the Strong must have had trouble doing the math when trying to keep track of all those offspring. He could have done that math a bit faster if he had just had more fingers and toes to work with...
The way I just solved the problem in my head was like this: 1) 314 X 1.5 (one and a half of 314) and I get 450 + 21 which is 471. But since it's 150 instead of 1.5, make that 47,100.
2) 314 X 9 = 314 X 3 X 3 = 942 X 3 = 2826.
3) 47,100 + 2826 = 49,926. Each one of those steps is fairly easy to do in your head -- a heck of lot easier than figuring out logarithms.
Except computers don’t multiply digit by digit.
I need an algorithm to help me read faster.
I don’t usually monkey around with Riemann zeta functions but...I do remember about Ramanujan and the taxicab number!
A much better explanation and fun too!
https://plus.maths.org/content/infinity-or-just-112
The trick
So how did the people in the Numberphile video “prove” that the natural numbers all add up to -1/12? The real answer is that they didn’t. Watching the video is like watching a magician and trying to spot them slipping the rabbit into the hat.
Hallmark loved him...366 kids, that’s a birthday card a day to buy.
Back in the day you used your slide rule to do calcutions or resorted to tables of logarithms. Multiplication is accomplished by adding the logarithms of the numbers then looking up the antilog of the sum in another set of tables. I still have my old slide rule and also kept a well worn book of logs. My grandkids will someday be amused. Intetesting the Saturn V moon rocket was designed with this technology.
Disclaimer: Opinions posted on Free Republic are those of the individual posters and do not necessarily represent the opinion of Free Republic or its management. All materials posted herein are protected by copyright law and the exemption for fair use of copyrighted works.