Re: Limiting mma caching (??)

*Subject*: [mg2641] Re: Limiting mma caching (??)*From*: wagner at bullwinkle.cs.Colorado.EDU (Dave Wagner)*Date*: Thu, 30 Nov 1995 21:02:29 -0500*Approved*: usenet@wri.com*Distribution*: local*Newsgroups*: wri.mathgroup*Organization*: Wolfram Research, Inc.

In article <49dplb$8a6 at dragonfly.wri.com>, Mark Van de Vyver <mvyver at ecel.uwa.edu.au> wrote: >Hi, > >I've the following query / suggestion. > >Is it possible to limit the amount of caching that mma does? > >For example: > >factorial[0] = 1; >factorial[n] = n * factorial[n-1]; > >With factorial[5], there are five numbers held in memory. > >In larger recursions this chews up memory quite fast. >A useful feature would be to be able to limit mma to holding the last 'x' >numbers in memory. >Is it possible to implement such a feature, or would it have to be built in >by Wolfram? Well, I feel a duty to answer this question, seeing as how I wrote an article about using this technique. Funny thing is, I was thinking about this exact problem last night! What you'd want to do is set up a definition like the following: (Local) In[55]:= Clear[factorial] factorial[0] = 1; factorial[n_] := ( factorial[n] = n * factorial[n-1]; If[n>1, Unset[factorial[#]]&[n-1]]; factorial[n] ) The basic idea here is that after you compute factorial[n], you don't need factorial[n-1] any longer, so you get rid of it. The mechanics of doing this are somewhat subtle. Since Unset holds its argument, you can't simply call "Unset[factorial[n-1]]". You have to get an actual numeric value inside the factorial inside the Unset. I've done this using a pure function trick; there are other tricks involving Hold and rule substitution that would do the same thing, although not as elegantly. The If is necessary so that the base case doesn't get removed! If you wanted to save, say, the last 10 values, you could do something like "If[n > 11, Unset[factorial[#]]&[n-10]]". Of course, all of this extra calculation slows things down. Observe what happens: (Local) In[58]:= factorial[10] (Local) Out[58]= 3628800 (Local) In[59]:= ?factorial Global`factorial factorial[0] = 1 factorial[10] = 3628800 factorial[n_] := (factorial[n] = n*factorial[n - 1]; If[n > 1, ((factorial[#1] =. ) & )[n - 1]]; factorial[n]) If you call factorial with a larger argument, the recursion will "bottom out" at the cached value of factorial[10], which will then be removed: (Local) In[60]:= factorial[20] (Local) Out[60]= 2432902008176640000 (Local) In[61]:= ?factorial Global`factorial factorial[0] = 1 factorial[20] = 2432902008176640000 factorial[n_] := (factorial[n] = n*factorial[n - 1]; If[n > 1, ((factorial[#1] =. ) & )[n - 1]]; factorial[n]) On the other hand, if you evaluate factorial of a smaller number, then the previous cached value isn't removed. Hopefully this isn't a problem. (Local) In[62]:= factorial[5] (Local) Out[62]= 120 (Local) In[63]:= ?factorial Global`factorial factorial[0] = 1 factorial[5] = 120 factorial[20] = 2432902008176640000 factorial[n_] := (factorial[n] = n*factorial[n - 1]; If[n > 1, ((factorial[#1] =. ) & )[n - 1]]; factorial[n]) Things get slightly trickier with a more complicated example, such as the fibonacci function. (Local) In[64]:= Clear[fib] fib[0] = fib[1] = 1; fib[n_] := ( fib[n] = fib[n-1] + fib[n-2]; If[n > 3, Unset[fib[#]]&[n-2]]; fib[n] ) Here, I've saved the last two cached values by Unset'ing fib[n-2]. This is fairly subtle: the recursive call to fib[n-1] computes fib[n-2] and Unsets fib[n-3]; then the recursive call to fib[n-2] doesn't require any recursion because fib[n-2] is still cached. (I had to think about this about 5 times before I could convince myself it was right!) Here's proof: (Local) In[92]:= Trace[fib[8], fib[__]] (Local) Out[92]= {fib[8], {{{fib[7], {{{fib[6], {{{fib[5], {{{fib[4], {{{fib[3], {{{fib[2], {{{fib[1]}, {fib[0]}}}, {fib[2]}}, {fib[1]}}}, {fib[3]}}, {fib[2]}}}, {fib[4]}}, {fib[3]}}}, {fib[5]}}, {fib[4]}}}, {fib[6]}}, {fib[5]}} }, {fib[7]}}, {fib[6]}}}, {fib[8]}} (Local) In[93]:= ?fib Global`fib fib[0] = 1 fib[1] = 1 fib[7] = 21 fib[8] = 34 fib[n_] := (fib[n] = fib[n - 1] + fib[n - 2]; If[n > 3, ((fib[#1] =. ) & )[n - 2]]; fib[n]) Dave Wagner Principia Consulting (303) 786-8371 dbwagner at princon.com http://www.princon.com/princon