Hacker News Reader

It's true your solution will work, but you're essentially trading space complexity for time complexity. With 2^524288 states, instead of requiring more RAM than there are atoms in the universe worth of RAM, you'll now need more seconds of compute time than we have left before the heat death of the universe.

View on HN

Note that the time taken is linear with respect to the original execution.

A cycle of n instructions starting at instruction n0 will be detected in between n0 and n0+n iterations (i.e. <= 3*(n0+n) underlying instructions) since n0 iterations gets both into the cycle and the offset between them will become 0 some time in the next n iterations.

n could be very large, of course (e.g, using all of memory as a giant counter so the cycle length is huge), but the cycle detection is not really making your problem worse.

Reply on news.ycombinator.com