I want to calculate f^128(X) (mod N), where f is a polynomial and f^128 is f composed with itself 128 times.
First I calculate f(X) (mod N). Now my workspace is:
X, f(X), garbage.
I copy out the f(X) to some scratch space. Now my workspace is:
X, f(X), garbage, f(X).
Now I reverse my original computation to clear the garbage.
X, 0, 0, f(X).
Now I repeat this process to compute f(f(X)).
X, f(f(X)), garbage, f(X).
Now copy out f(f(X)) and uncompute.
X, 0, 0, f(X), f(f(X)).
Now I repeat my calculation of f(X), but backwards.
X, 0, 0, 0, f(f(X)).
Now I repeat my computation of f(f(X)), but starting from f(f(X)) instead of from X.
X, 0, 0, 0, f(f(X)), f(f(f(f(X))))
Now I reverse my computation of f(f(X)):
X, 0, 0, 0, 0, f(f(f(f(X))))
And so on.
I end up with
X, 0, 0, 0, 0, 0, 0, 0, 0, 0, f^128(X).
after about 2100 steps.
I've used 11 times more memory than required to compute f. But on the flipside, I've generated no waste heat, while just applying f over and over again would have generated 128 times the waste heat required to compute f.
1. First I calculate f(X) (mod N). Now my workspace is:
X, f(X), garbage-1.
2. I copy out the f(X) to some scratch space. Now my workspace is:
X, f(X), garbage-2, f(X).
3. Now I reverse my original computation to clear the garbage.
X, 0, 0, f(X).
Is garbage-1 the same as garbage-2? If so, how do you copy f(X) in step 2 without introducing more garbage? If not, how do you reverse the computation in step 3?
This post may be interesting to some LWers.
In summary: it looks like our universe can support reversible computers which don't create entropy. Reversible computers can simulate irreversible computers, with pretty mild time and space blowup. So if moral value comes from computation, negentropy probably won't be such an important resource for distant future folks, and if the universe lasts a long time we may be able to simulate astronomically long-lived civilizations (easily 10^(10^25) clock cycles, using current estimates and neglecting other obstructions).
Has this been discussed before, and/or is there some reason that it doesn't work or isn't relevant? I suspect that this consideration won't matter in the long run, but it is at least interesting and seems to significantly deflate (long-run) concerns about entropy.