> 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.
As a regular user of O(n*log(n)) multiplication algorithms in my daily work, I find your comment amusing.
> 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.
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!
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.
> 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
2: https://en.wikipedia.org/wiki/Sch%C3%B6nhage%E2%80%93Strasse...
And if so, can I ask what it's useful for? I thought it was a galactic algorithm.