3 ms·

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

• 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!