3 ms·

Is "Perfect" really an appropriate qualifier here? Did the source article present a proof that O(n log n) is the lowest growth order for this kind of task? Or

Is "Perfect" really an appropriate qualifier here? Did the source article present a proof that O(n log n) is the lowest growth order for this kind of task? Or am I just out of the loop and it's already known that this is the case? Update: Apparently, the article actually says that the approach is not perfect.

smadge 8y ago
From the article: “Harvey and van der Hoeven’s algorithm proves that multiplication can be done in n × log n steps. However, it doesn’t prove that there’s no faster way to do it. Establishing that this is the best possible approach is much more difficult.”
- davesque 8y ago
  Thanks. I skimmed it but didn't read thoroughly.
gumby 8y ago
The article says that it may be the fastest: > At the end of February, a team of computer scientists at Aarhus University posted a paper [ https://arxiv.org/abs/1902.10935 https://arxiv.org/abs/1902.10935 ] arguing that if another unproven conjecture is also true, this is indeed the fastest way multiplication can be done.
- thomasahle 8y ago
  It's a really great paper. It is a bit funny though to state it as giving more confidence to the multiplication lower bound, since multiplication has clearly been studied a lot more than network coding. So it makes more sense to think of it as a new possible attack vector to prove the lower bound, if that makes sense.
notfed 8y ago
Even if n*log(n) turns out to be asymptotically "perfect", I'm curious what the constant overhead is. If it takes 15 minutes to multiply two 64-bit numbers, it might not be as "perfect".
- colatkinson 8y ago
  From this article written by the author [0], the overhead is very high. So I don't think you'll be seeing this implemented in your CPU any time soon. The usefulness seems to be that (1) it's a cool new piece of theory and (2) it's significant if you're doing computational work on ridiculously large numbers, like massive primes or something. Gaps between theoretically optimal and practically optimal algorithms are extremely common. [0]: https://theconversation.com/weve-found-a-quicker-way-to-multiply-really-big-numbers-114923 https://theconversation.com/weve-found-a-quicker-way-to-mult...

smadge 8y ago

From the article: “Harvey and van der Hoeven’s algorithm proves that multiplication can be done in n × log n steps. However, it doesn’t prove that there’s no faster way to do it. Establishing that this is the best possible approach is much more difficult.”

davesque 8y ago
Thanks. I skimmed it but didn't read thoroughly.

gumby 8y ago

The article says that it may be the fastest: > At the end of February, a team of computer scientists at Aarhus University posted a paper [ https://arxiv.org/abs/1902.10935 https://arxiv.org/abs/1902.10935 ] arguing that if another unproven conjecture is also true, this is indeed the fastest way multiplication can be done.

thomasahle 8y ago
It's a really great paper. It is a bit funny though to state it as giving more confidence to the multiplication lower bound, since multiplication has clearly been studied a lot more than network coding. So it makes more sense to think of it as a new possible attack vector to prove the lower bound, if that makes sense.

notfed 8y ago

Even if n*log(n) turns out to be asymptotically "perfect", I'm curious what the constant overhead is. If it takes 15 minutes to multiply two 64-bit numbers, it might not be as "perfect".

colatkinson 8y ago
From this article written by the author [0], the overhead is very high. So I don't think you'll be seeing this implemented in your CPU any time soon. The usefulness seems to be that (1) it's a cool new piece of theory and (2) it's significant if you're doing computational work on ridiculously large numbers, like massive primes or something. Gaps between theoretically optimal and practically optimal algorithms are extremely common. [0]: https://theconversation.com/weve-found-a-quicker-way-to-multiply-really-big-numbers-114923 https://theconversation.com/weve-found-a-quicker-way-to-mult...