B Long live Multiplication

  • Thread starter jedishrfu
  • Start date
  • Featured
10,231
3,788
10,231
3,788
I was disappointed to find that it worked only for incredibly large numbers and not at the range of numbers that grade school kids suffer with and so we are left with multiplication tables or the cool Trachtenberg method that never caught on despite its promise.
 
32,108
3,993
Quote from the article:
In the new study, the researchers considered only numbers with more than roughly ##10^{214857091104455251940635045059417341952}## digits when written in binary, in which numbers are encoded with a sequence of 0s and 1s. But the scientists didn’t actually perform any of these massive multiplications, because that’s vastly more digits than the number of atoms in the universe. That means there’s no way to do calculations like that on a computer, because there aren’t enough atoms to even represent such huge numbers, much less multiply them together. Instead, the mathematicians came up with a technique that they could prove theoretically would be speedier than other methods, at least for these large quantities.
I don't get the reasoning on why the multiplication couldn't be done. So what if there aren't that many atoms in the universe. We can do already do calculations with numbers much larger than the no. of atoms in the universe, and get the right answer.

Typical (insert your favorite pejorative) "journalist," which is synonymous with "can't do any math past arithmetic, and even has trouble with fractions and percents, at that."
 

fresh_42

Mentor
Insights Author
2018 Award
9,490
6,502
Typical (insert your favorite pejorative) "journalist," which is synonymous with "can't do any math past arithmetic, and even has trouble with fractions and percents, at that."
I like the roughly in front of this number.
 

jbriggs444

Science Advisor
6,968
2,289
We can do already do calculations with numbers much larger than the no. of atoms in the universe, and get the right answer.
Numbers whose decimal representations are much larger than the number of atoms in the universe are more challenging.
 

TeethWhitener

Science Advisor
Gold Member
1,190
640
Numbers whose decimal representations are much larger than the number of atoms in the universe are more challenging.
Maybe we can convince everyone to start representing numbers as their prime factorizations. Then multiplication would have a time complexity of just ##O(n)## (because it’s basically string concatenation) and, thanks to the prime counting function being logarithmic, we could represent much larger numbers efficiently. Though it might be difficult to remember my wife’s ##p_1^3p_3## rd birthday...
 
10,231
3,788
Maybe we can convince everyone to start representing numbers as their prime factorizations. Then multiplication would have a time complexity of just ##O(n)## (because it’s basically string concatenation) and, thanks to the prime counting function being logarithmic, we could represent much larger numbers efficiently. Though it might be difficult to remember my wife’s ##p_1^3p_3## rd birthday...
We could have an app for that and save your marriage.
 
32,372
8,350
I don't get the reasoning on why the multiplication couldn't be done. So what if there aren't that many atoms in the universe. We can do already do calculations with numbers much larger than the no. of atoms in the universe, and get the right answer.
Wrong power.
We can multiply numbers larger than 1080, numbers with 80 (decimal) digits - easily. But we cannot (in general) store numbers of the order of 101080, with 1080 digits. In some special cases you can, of course. As an example, ##10^{{10}^{80}} \cdot 10^{{10}^{80}} = 10^{2\cdot 10^{80}}##, but what the article is about is a multiplication scheme that works for all numbers. In all cases where we can store the numbers on computers in this universe the new multiplication method is not faster.
 
617
157
Thank you for this thread, as the topic had eluded PhysOrg news.

Per wry comment on another site, it might offer a nut-cracker for previously intractable 'integer' problems such as the arcane extremities of Diophantine stuff...
 
919
148
I'll make a table for multiplying ##n##-digit numbers:
AlgorithmRuntime
Explicit##O(n^2)##
This new one##O(n \log n)##
Karatsuba##O(n^{\log 3 / \log 2}) \approx O(n^{1.58})##
Toom-Cook (Toom-3)##O(n^{\log 5 / \log 3}) \approx O(n^{1.46})##
Schönhage-Strassen##O(n \log n \cdot \log \log n)##
Fürer##O(n \log n \cdot 2^{O(\log^* n)})##
Here, ##\log^* n## is the "iterated logarithm", how many times one has to take a logarithm before the result becomes less than 1.

These formulas omit overall multiplication constants, and these constants get larger in the asymptotically-faster algorithms.
 
919
148
Here I will estimate the effect of a large overall constant. Consider Karatsuba or Toom-Cook, with ##K n^c##. The crossover point for ordinary multiplication is at ##K n^c \approx n^2##, with solution ##n_{co} \approx K^{1/(2-c)}##. For ##c \approx 1.5## and ##K \approx 10##, ##n_{co} \approx 100##.

For the best asymptotic case, ##K n \log n \approx n^2##, with ##n_{co} \approx K \log K##. So in this most recent paper, ##K## must be very large.

I used the Wikipedia articles as sources for all but the first two algorithms.
 

Want to reply to this thread?

"Long live Multiplication" You must log in or register to reply here.

Physics Forums Values

We Value Quality
• Topics based on mainstream science
• Proper English grammar and spelling
We Value Civility
• Positive and compassionate attitudes
• Patience while debating
We Value Productivity
• Disciplined to remain on-topic
• Recognition of own weaknesses
• Solo and co-op problem solving

Top Threads

Top