3 ms·

It only really kicks in over the previous best at about n>2^2^4000 iirc. This is a theoretical paper, but it is possible that some of the new fourier transform

• Someone 8y ago
  Not that it matters, but the constant used in the paper is 4096, not 4000. This algorithm is proven to be O(n log n) only for numbers with at least 2^4096 ≪ 10^1200 bits. For comparison, we estimate there are 10^80 or so atoms in the known universe, so we would need quite a bit of progress in physics to even store one such number; this clearly is theoretical computer science. On the plus side, they didn’t set out to minimize that constant, and think it can easily [1] be decreased significantly. [1] ‘easily’ in the mathematical sense of “we think everybody who understands this paper and is willing to do potentially a lot of hard work will be able to pull it of”
  • klyrs 8y ago
    > This algorithm is proven to be O(n log n) only for numbers with at least 2^4096... No worries, all the rest runs in O(1)..