3 ms·
AIUI, it's just a linear penalty because, at worst, you have to run each computation backwards to "uncompute it". That's under the (necessary) assumption that
by SilasX 10y ago
AIUI, it's just a linear penalty because, at worst, you have to run each computation backwards to "uncompute it".
That's under the (necessary) assumption that you don't even try to avoid erasure operations that need for their own sake rather than as an intermediate step.
- aparent 10y agoIt is a bit more complicated then that. The only penalty to time is a constant factor if you are willing to use space proportional to the computation time. I did a bit of work on how to do time-space trade-offs in reversible circuits in my masters thesis http://hdl.handle.net/10012/10949 http://hdl.handle.net/10012/10949.