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

[jedishrfu]

A new way to multiply one that only a computer could love if only it had enough bits to do it:

https://www.sciencenews.org/article/mathematicians-may-have-found-fastest-way-multiply-huge-numbers

 

[jedishrfu]

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.

 

[Mark44]

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]

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]

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]

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

 

[jedishrfu]

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.

 

[mfb]

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 10⁸⁰, numbers with 80 (decimal) digits - easily. But we cannot (in general) store numbers of the order of 10¹⁰⁸⁰, with 10⁸⁰ 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.

 

[Nik_2213]

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

 

[lpetrich]

I'll make a table for multiplying $n$-digit numbers:

Algorithm	Runtime
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.

 

[lpetrich]

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.

 

[jedishrfu]

Here’s a Quanta article describing the new multiplication scheme in more detail

https://www.quantamagazine.org/a-ne...he-door-to-better-quantum-computers-20190424/