logoalt Hacker News

adgjlsfhk1 • today at 4:01 AM • 2 replies • view on HN

The DFT result isn't RAM specific. It holds up in multi-tape turing machines. (it is, however, galactic).


Replies

hansvm • today at 5:04 AM

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.

➕ show 1 reply
lg5689 • today at 5:59 AM

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

➕ show 1 reply