Hacker News new | past | comments | ask | show | jobs | submit
The DFT result isn't RAM specific. It holds up in multi-tape turing machines. (it is, however, galactic).
That doesn't sound right. Previous results proved that with bounded values you couldn't beat O(nlogn), among other things. The OpenAI result explicitly used arbitrary-precision complex arithmetic. Yes, it's galactic [0], but either it's wrong or the previous results were wrong, no?

[0] Very much not something I care much about in these sorts of conversations. Even if it weren't galactic, a random logn factor here and there usually loses to cache efficiency and whatnot. Their speedups were less than that, and I'd already assumed we were in the realm of applied math rather than real engineering.

loading story #50255100
Are you thinking of the int multiplication result instead? The DFT result uses a computation model with unlimited precision reals.
loading story #50255283