A very recent paper on this is "Selective Memoization" http://arxiv.org/pdf/1106.0447.pdf which gives lots of other references. Victor On Sat, Mar 9, 2013 at 11:36 AM, Henry Baker <hbaker1@pipeline.com> wrote:
Found it! (I've been trying to find this reference for several months.)
Hilden, J. "Elimination of recursive calls using a small table of randomly selected function values." BIT 16,1 (1976), 60-73.
I'm sure Hilden's wasn't the first memo implementation which forgot some entries, but Hilden's paper focused on this particular issue the best.
At 07:43 AM 3/9/2013, Joerg Arndt wrote:
* Henry Baker <hbaker1@pipeline.com> [Mar 09. 2013 16:22]:
[...]
We now note that it doesn't harm performance "too" much if we sometimes forget a particular result and have to recompute it; this is somewhat akin to a "page fault" in a virtual memory system.
There are very many ways this could be made precise...
In fact, for many applications, a finite, fixed-size "memo table" is often good enough for government work.
For some definition of "many" and "enough".
Question: does anyone here have an academic _reference_ for this last statement that a fixed-size memo table is good enough?
I seem to recall reading a short paper (in English) from the 1960's or 1970's which made precisely this point about fixed-size memo tables.
[...]
Cormen et al., Introduction to Algorithms, (2nd ed.) doesn't seem to give a single reference about memoization.
A few "old enough" ones may be
Samuel, A. L. , IBM J. Res. Dev., 3, 210 (1959).
Michie, D. , Research Memorandum MIP-R-29, Dept. Machine Intelligence and Perception (Edinburgh Univ., 1968).
Burstall, R. M. , and Popplestone, R. J. , Machine Intelligence 2 (edit. by Dale, E., and Michie, D.), 207 (Oliver and Boyd, Edinburgh, 1968); POP-2 Papers (Oliver and Boyd, Edinburgh, 1968).
Popplestone, R. J. , Research Memorandum MIP-R-30, Dept. Machine Intelligence and Perception (Edinburgh Univ., 1968).
Michie, D. , and Chambers, R. A. , Machine Intelligence 2 (edit. by Dale, E., and Michie, D.), 137 (Oliver and Boyd, Edinburgh, 1968).
Michie, D. , and Chambers, R. A. , Experimental Programming Reports : No. 14, Dept. Machine Intelligence and Perception (Edinburgh Univ., 1968); in Towards a Theoretical Biology (edit. by Waddington, C. H.), 1 (Edinburgh University Press) (in the press).
Donaldson, P. E. K. , Proc. Third Intern. Conf. Medical Electronics, 173 (1960). Eastwood, E. , Proc. I.E.E., 115, 203 (1968).
Zeeman, E. C. , and Buneman, O. P. , Towards a Theoretical Biology (edit. by Waddington, C. H.), 1, 140 (Edinburgh University Press, 1968).
Fredkin, E. , in The Programming Language LISP : Its Operation and Applications (edit. by Berkeley, E. C., and Bobrow, D. G.) (MIT Press, 1964).
Pivar, M. , and Finkelstein, M. , in The Programming Language LISP : Its Operation and Applications (edit. by Berkeley, E. C., and Bobrow, D. G.) (MIT Press, 1964).
This was cheerfuly copied & pasted from http://www.nature.com/nature/journal/v218/n5136/abs/218019a0.html
Suggest to check Knuth's TAOCP.
Best, jj
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun