points by adgjlsfhk1 3 days ago | 0 comments
The DFT result isn't RAM specific. It holds up in multi-tape turing machines. (it is, however, galactic).
[–] hansvm 3 days ago
[–] adgjlsfhk1 3 days ago
> but either it's wrong or the previous results were wrong, no?
Not quite. This result uses polylog(n) precision which isn't bounded, so it escapes the previous bounds. This doesn't noticably affect the runtime because not all of the math needs this extra precision (in this case you need a couple computations in higher precision but less than n operations), so the extra precision can be payed for even in a TM/circuit model.
[–] lg5689 3 days ago
Are you thinking of the int multiplication result instead? The DFT result uses a computation model with unlimited precision reals.
[–] adgjlsfhk1 3 days ago
no. The DFT result as published uses unlimited precision, but the comparison with the int multiplication shows that the unlimited precision just makes the paper shorter/easier rather than being an exploit in the computation model.
[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.