4 ms·

> Sort of like the n lg n multiplication algorithm: it's nice that we can do it in principle, but you'd never actually use it. As a regular user of O(n*log(n))

> Sort of like the n lg n multiplication algorithm: it's nice that we can do it in principle, but you'd never actually use it. As a regular user of O(n*log(n)) multiplication algorithms in my daily work, I find your comment amusing.

amelius 5y ago
Isn't it part of just about every bignum library out there?
- enriquto 5y ago
  Yes, I had not thought about that even.
- Sukera 5y ago
  Not necessarily, no - the "perfectly efficient" algorithms often have prohibitively high constants in front of the theoretically perfect big-O, making them only useful/faster for numbers with so many digits that you can't realistically represent a lot of them, even on modern super computers. On top of that, caching effects and different implementations can make algorithmically "worse" code perform better for longer than naively assumed when comparing their big-O.
dataflow 5y ago
Are you sure you're using this algorithm [1] in your daily work and not a different one? It's the only known O(n log n) multiplication algorithm AFAIK. And if so, can I ask what it's useful for? I thought it was a galactic algorithm. [1] https://hal.archives-ouvertes.fr/hal-02070778/document https://hal.archives-ouvertes.fr/hal-02070778/document
- enriquto 5y ago
  No, I don't multiply integers, but polynomials, where the standard "fast" algorithm is nlogn
  - dataflow 5y ago
    Oh. I think the comment you replied to was talking about integer multiplication, not polynomial.
  - adgjlsfhk1 5y ago
    to be specific, this is nlogn arithmetic operations, which isn't nlogn if you are doing exact math.
    - enriquto 5y ago
      sure, my coefficients are just floating-point numbers. I work in signal processing and when the OP said "multiplication" I could only think about applying a linear filter to a signal.
- adgjlsfhk1 5y ago
  It's unknown whether it is a galactic algorithm (with some minor tweaks). According to the author, the version they published is optimized for simplicity and paper length rather than speed, but he thinks a lot of the constants can be made much lower. It's still quite likely galactic, but with some tweaks, it might not be. Also, in practice, I think their first algorithm that is nlogn subject to unproven (but likely) conjectures about the distribution of primes is more likely to be good computationally, but I am way out of my depth here.
bakul 5y ago
The Schönhage–Strassen algorithm is O(n*log(n)*log(log(n))) time algorithm. Fürer's algorithm is better (& impractical) but still worse than O(n*log(n)). Harvey and van der Hoeven's algorithm is conjectured to be O(n*log(n)) but not yet proven. No idea if it is practical! https://hal.archives-ouvertes.fr/hal-02070778v2/document https://hal.archives-ouvertes.fr/hal-02070778v2/document
- scapp 5y ago
  Wait, is there something wrong with the paper you linked? Theorem 1.1 says > There is an integer multiplication algorithm achieving M(n) = O(n log n). You don't call something a theorem if it's a conjecture.
  - bakul 5y ago
    See this: https://newsroom.unsw.edu.au/news/science-tech/maths-whiz-solves-48-year-old-multiplication-problem https://newsroom.unsw.edu.au/news/science-tech/maths-whiz-so... Where one of the authors says "So in this sense, our work is expected to be the end of the road for this problem, although we don't know yet how to prove this rigorously.” Though I confess I am not up on the latest happenings in this area!
    - tzs 5y ago
      The author is not saying that they don't know how to prove rigorously that their algorithm is O(n log(n)). They have rigorously proven that. What they are saying is that they don't know how to prove that you can't do better than O(n log(n)). Schönhage and Strassen conjectured that O(n log(n)) was the lower limit for this problem, and it seems that most experts believe they were right abut that. Hence, the expectation that with the discovery of an actual O(n log(n)) algorithm we are at the end of the road for this problem.
      - bakul 5y ago
        Thanks for the correction. Should've read the paper when less tired!
Strilanc 5y ago
I maybe should have been more explicit: I was referring to the bit-operation cost of big integer multiplication. The only claimed O(n lg n) algorithm for this task [1] notes: > Let n_0 = 2^(d^12) >= 2^4096 and suppose we wish to multiply numbers with n bits. [...] For n > n_0 we will describe a recursive algorithm [...] 2^4096 bits is enormous. That's way way way past the point where you could fit the numbers into the observable universe. Past the point where the expansion of space has become a real problem. You really should just use the O(n lg n lglg n) algorithm instead [2]. Your other comments indicate you work with polynomials with floating point coefficients. Yes, there are O(n lg n) algorithms for that case. And they are very practical. 1: https://hal.archives-ouvertes.fr/hal-02070778v2/document https://hal.archives-ouvertes.fr/hal-02070778v2/document 2: https://en.wikipedia.org/wiki/Sch%C3%B6nhage%E2%80%93Strassen_algorithm https://en.wikipedia.org/wiki/Sch%C3%B6nhage%E2%80%93Strasse...
dekhn 5y ago
the point is that most people doing MM aren't doing theoretically optimal (for large N) algorithms, there are more practical algorithms with a higher computational cost that finish faster, for reasonable engineering reasons.

amelius 5y ago

Isn't it part of just about every bignum library out there?

enriquto 5y ago
Yes, I had not thought about that even.
Sukera 5y ago
Not necessarily, no - the "perfectly efficient" algorithms often have prohibitively high constants in front of the theoretically perfect big-O, making them only useful/faster for numbers with so many digits that you can't realistically represent a lot of them, even on modern super computers. On top of that, caching effects and different implementations can make algorithmically "worse" code perform better for longer than naively assumed when comparing their big-O.

dataflow 5y ago

Are you sure you're using this algorithm [1] in your daily work and not a different one? It's the only known O(n log n) multiplication algorithm AFAIK. And if so, can I ask what it's useful for? I thought it was a galactic algorithm. [1] https://hal.archives-ouvertes.fr/hal-02070778/document https://hal.archives-ouvertes.fr/hal-02070778/document

enriquto 5y ago
No, I don't multiply integers, but polynomials, where the standard "fast" algorithm is nlogn
- dataflow 5y ago
  Oh. I think the comment you replied to was talking about integer multiplication, not polynomial.
- adgjlsfhk1 5y ago
  to be specific, this is nlogn arithmetic operations, which isn't nlogn if you are doing exact math.
  - enriquto 5y ago
    sure, my coefficients are just floating-point numbers. I work in signal processing and when the OP said "multiplication" I could only think about applying a linear filter to a signal.
adgjlsfhk1 5y ago
It's unknown whether it is a galactic algorithm (with some minor tweaks). According to the author, the version they published is optimized for simplicity and paper length rather than speed, but he thinks a lot of the constants can be made much lower. It's still quite likely galactic, but with some tweaks, it might not be. Also, in practice, I think their first algorithm that is nlogn subject to unproven (but likely) conjectures about the distribution of primes is more likely to be good computationally, but I am way out of my depth here.

bakul 5y ago

The Schönhage–Strassen algorithm is O(n*log(n)*log(log(n))) time algorithm. Fürer's algorithm is better (& impractical) but still worse than O(n*log(n)). Harvey and van der Hoeven's algorithm is conjectured to be O(n*log(n)) but not yet proven. No idea if it is practical! https://hal.archives-ouvertes.fr/hal-02070778v2/document https://hal.archives-ouvertes.fr/hal-02070778v2/document

scapp 5y ago
Wait, is there something wrong with the paper you linked? Theorem 1.1 says > There is an integer multiplication algorithm achieving M(n) = O(n log n). You don't call something a theorem if it's a conjecture.
- bakul 5y ago
  See this: https://newsroom.unsw.edu.au/news/science-tech/maths-whiz-solves-48-year-old-multiplication-problem https://newsroom.unsw.edu.au/news/science-tech/maths-whiz-so... Where one of the authors says "So in this sense, our work is expected to be the end of the road for this problem, although we don't know yet how to prove this rigorously.” Though I confess I am not up on the latest happenings in this area!
  - tzs 5y ago
    The author is not saying that they don't know how to prove rigorously that their algorithm is O(n log(n)). They have rigorously proven that. What they are saying is that they don't know how to prove that you can't do better than O(n log(n)). Schönhage and Strassen conjectured that O(n log(n)) was the lower limit for this problem, and it seems that most experts believe they were right abut that. Hence, the expectation that with the discovery of an actual O(n log(n)) algorithm we are at the end of the road for this problem.
    - bakul 5y ago
      Thanks for the correction. Should've read the paper when less tired!

Strilanc 5y ago

I maybe should have been more explicit: I was referring to the bit-operation cost of big integer multiplication. The only claimed O(n lg n) algorithm for this task [1] notes: > Let n_0 = 2^(d^12) >= 2^4096 and suppose we wish to multiply numbers with n bits. [...] For n > n_0 we will describe a recursive algorithm [...] 2^4096 bits is enormous. That's way way way past the point where you could fit the numbers into the observable universe. Past the point where the expansion of space has become a real problem. You really should just use the O(n lg n lglg n) algorithm instead [2]. Your other comments indicate you work with polynomials with floating point coefficients. Yes, there are O(n lg n) algorithms for that case. And they are very practical. 1: https://hal.archives-ouvertes.fr/hal-02070778v2/document https://hal.archives-ouvertes.fr/hal-02070778v2/document 2: https://en.wikipedia.org/wiki/Sch%C3%B6nhage%E2%80%93Strassen_algorithm https://en.wikipedia.org/wiki/Sch%C3%B6nhage%E2%80%93Strasse...

dekhn 5y ago

the point is that most people doing MM aren't doing theoretically optimal (for large N) algorithms, there are more practical algorithms with a higher computational cost that finish faster, for reasonable engineering reasons.