Of course, "memoization" is a silly neologism, redolent of 1950's office work ;-) when I teach this subject, I use the perfectly good word "memorization". Cris Moore Cristopher Moore Professor, Santa Fe Institute The Nature of Computation Cristopher Moore and Stephan Mertens Available now at all good bookstores, or through Oxford University Press http://www.nature-of-computation.org/ On Mar 9, 2013, at 10:24 AM, Victor Miller wrote:
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
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun