Is this new multiplication method the key to faster quantum computers?

  • B
  • Thread starter jedishrfu
  • Start date
  • Tags
    Multiplication
  • Featured
In summary, mathematicians have discovered a new way to multiply large numbers that is theoretically faster than other methods, but it only works for numbers with more than roughly ##10^{214857091104455251940635045059417341952}## digits when written in binary. This is because there are not enough atoms in the universe to represent or perform calculations with numbers of this size. However, the new method could have potential applications in solving previously intractable problems, such as those involving extremely large prime numbers. It has a time complexity of ##O(n \log n)##, making it faster than other methods like Karatsuba and Toom-Cook.
Mathematics news on Phys.org
  • #2
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.
 
  • #3
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."
 
  • #4
Mark44 said:
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.
 
  • Haha
Likes FactChecker
  • #5
Mark44 said:
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.
 
  • #6
jbriggs444 said:
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...
 
  • Like
Likes jedishrfu
  • #7
TeethWhitener said:
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.
 
  • Haha
Likes TeethWhitener
  • #8
Mark44 said:
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.
 
  • Like
Likes dRic2
  • #9
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...
 
  • #10
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.
 
  • Like
Likes Greg Bernhardt and fresh_42
  • #11
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.
 

1. What is "Long live Multiplication"?

"Long live Multiplication" is a phrase commonly used to express the importance and usefulness of multiplication in various fields of science, mathematics, and everyday life.

2. Why is multiplication important in science?

Multiplication is important in science because it allows us to quickly and accurately calculate quantities, measurements, and relationships between variables. It is also essential for understanding more complex mathematical concepts and equations used in scientific research.

3. What are some real-world applications of multiplication in science?

Multiplication is used in various scientific fields such as physics, chemistry, and biology. For example, it is used to calculate the force of gravity, convert units of measurement, and determine the number of molecules in a substance.

4. How can I improve my multiplication skills for science?

Practice is key to improving multiplication skills for science. You can also use online resources, such as multiplication games and worksheets, to strengthen your skills. Additionally, understanding the concepts behind multiplication and its applications in science can also help improve your skills.

5. Are there any shortcuts for multiplication in science?

Yes, there are some shortcuts for multiplication in science, such as using the commutative and associative properties, as well as the distributive property. These properties allow you to rearrange and break down multiplication problems into simpler ones, making them easier to solve.

Similar threads

  • Programming and Computer Science
Replies
14
Views
1K
  • General Math
Replies
1
Views
1K
Replies
3
Views
1K
  • General Math
Replies
5
Views
1K
Replies
33
Views
5K
Replies
1
Views
1K
  • Biology and Medical
Replies
7
Views
1K
Replies
36
Views
6K
Replies
8
Views
1K
  • Computing and Technology
Replies
32
Views
860
Back
Top