On Sat, 3 Apr 2010, Stanislav Maslovski wrote:
< On Sat, Apr 03, 2010 at 11:18:45PM +0400, Stanislav Maslovski wrote:
< > Well, I can do that too in this Maxima, but for some reason only
< > gradually. That is, if try it in one step, it fails:
< >
< > (%i1) pi[n]:=if n = 2 then 1 elseif primep(n) then pi[n-1]+1 else
< > pi[n-1]$
< >
< > (%i2) pi[5000];
< >
< > Maxima encountered a Lisp error:
< >
< > Error in PROGN [or a callee]: Bind stack overflow.
< >
< > Automatically continuing.
< > To enable the Lisp debugger set *debugger-hook* to nil.
< >
< > Now, if I restart Maxima and do this, it works:
< >
< > (%i1) pi[n]:=if n = 2 then 1 elseif primep(n) then pi[n-1]+1 else pi[n-1]$
< >
< > (%i2) for n: 100 thru 5000 step 100 do print(pi[n]);
< > 25
< > 46
< > 62
< > ...
< > 646
< > 654
< > 669
<
< I thought a little bit more about it and I think I understand now
< what is going on. Basically, in a recursive function like that, the
< pi[n]s are not evaluated (and therefore their values are not stored
< anywhere for reuse) until stack is filled with nested calls for
< pi[500], pi[499], ... pi[1]. The fact that pi[] is an array function
< does not prevent this from happening. Right?
Yes, and no. If pi were a function, then its recursive definition would
require all those nested calls to evaluate pi(500) each time. But since
pi is an array function, you can arrange that it only has 100 nested
calls at each step, as in your example above. This is because the array
function 'remembers' all the values computed. You can see this by
running your loop, then asking maxima to compute pi[5000] straightaway.
Leo
--
The University of Edinburgh is a charitable body, registered in
Scotland, with registration number SC005336.