Difference between revisions of "WG211/M21Glueck"
From WG 2.11
| Line 1: | Line 1: | ||
| − | The design and implementation of efficient algorithms for reversible computing systems requires unconventional ways of thinking. Memoization is a classic program optimization technique that stores | + | The design and implementation of efficient algorithms for reversible computing systems requires unconventional ways of thinking. Memoization is a classic program optimization technique that stores computation results in memory. How memoization can be made reversible without adding unbounded tracing is not immediately clear. This work-in-progress presention discusses a unconventional solution using cyclic state transition systems to memoize reversibly recurrence functions. The costs compare favorably to classic memoization: bounded space and amortized linear running time. Joint work with Tetsuo Yokoyama. |
Revision as of 10:58, 10 August 2022
The design and implementation of efficient algorithms for reversible computing systems requires unconventional ways of thinking. Memoization is a classic program optimization technique that stores computation results in memory. How memoization can be made reversible without adding unbounded tracing is not immediately clear. This work-in-progress presention discusses a unconventional solution using cyclic state transition systems to memoize reversibly recurrence functions. The costs compare favorably to classic memoization: bounded space and amortized linear running time. Joint work with Tetsuo Yokoyama.
