Difference between revisions of "WG211/M21Glueck"
From WG 2.11
(Created page with "The design and implementation of efficient algorithms for reversible computing systems requires an unconventional way of thinking. Memoization is a classic program optimizatio...") |
|||
| Line 1: | Line 1: | ||
| − | The design and implementation of efficient algorithms for reversible computing systems requires | + | 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 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 the 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.
