MathGroup Archive 1995

[Date Index] [Thread Index] [Author Index]

Search the Archive

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






  • Prev by Date: Re: Bug in symbolic inversion of matrices
  • Next by Date: Re: Question about thread
  • Previous by thread: Limiting mma caching (??)
  • Next by thread: 3D calculations