Hacker News Reader

Comment by eldenring | Hacker News Reader

I don't think that is necessarily true, the post is making a stronger point than what you describe

> Indeed, the algorithm requires you to multiply complex numbers whose magnitudes grow superpolynomially with n. If you stored these numbers as bits, the memory requirement would effectively be exponential in the input length. It assumes you can multiply such arbitrarily large complex numbers together in a single operation.

Another way to think about what the author said, imagine you had access to an oracle which could execute arbitrary precision arithmetic expressions in constant time. You could encode a wide range of computations in these and execute impossible algorithms.

View on HN

Replace the complex numbers with a finite field and O(1) arithmetic stops being an unrealistic assumption, as you can actually perform the required operations in constant time on a real computer. You can't do that for infinitely-precise complex numbers, but you'll never be able to provide an infinitely-precise complex number as the input anyway. If you start with finite-precision numbers (e.g. 64-bit floats) you can do all operations in a finite-field representation (e.g. the Ozaki scheme II is an actually practical implementation of that idea for matrix multiplication https://arxiv.org/abs/2504.08009 ) and the magnitude of intermediate values is no longer a problem.

Are you certain that applies here? The length of the intermediate numbers grows superpolynomially, so you would be sure to overflow fixed width numbers. Floats are not a field.

Yes, floats are not a field, which is why you don't use floating point except to convert to and from a different representation. Overflow is expected and cancels out as long as the final result is uniquely representable. See the paper I linked, which implements 64-bit floating point matrix multiplication using 8-bit numbers with wrapping overflow modulo a set of small coprime integers. The result is reconstructed at the end using the Chinese Remainder Theorem.

This reminds me of 'O(1)' hash maps, but far more egregious.

What's wrong with `O(1)` hash maps? I'm not aware of any underhanded tricks related to, for example, cuckoo hashing.

Hash maps are only O(1) for sufficiently small n. You need O(log n) bits just to write out the hash.

It's not any faster in practice to write a byte than a word (log(n) bits)

That depends on the scale. A couple jobs ago we had enough objects that an 80-bit key wouldn't have had a low enough collision rate (better models of computation for that domain include sqrt/cube-root ideas to account for information propagation in physical space). Sometimes you have to use more constrained devices so that your max effective constant-time word size (for the same computational cost -- not to quite be confused with the CPU's "native" word size, whatever that means in your circumstances) is 8, 16 or 32 bits (or, most recently at my last job, for _reasons_, 11 bits), making even quite small tables not quite O(1).

Many compsci researchers like the word-ram model of computation to avoid a bunch of extraneous log factors and to apply exactly the intuition you're describing, so that hashtables are actually O(1). That's not a bad habit. It introduces extra log factors in other places though, so I think it's a bit of a wash, and given that it doesn't model the actual register machines we use it feels a bit intellectually dishonest to me.

actually thinking about it more I think my oracle model is more powerful than the computer used in openai's fft but maybe its a good way to think about it.

Reply on news.ycombinator.com