On 4/4/10 5:08 AM, Leo Butler wrote:
>
> On Sun, 4 Apr 2010, Alasdair McAndrew wrote:
>
> < Recursive functions are generally slow and inefficient, and relying on your system to keep track of previously computed values can be dodgy. I prefer a two step
> < approach:
> <
> < (%i1) pr(n):=if primep(n) then 1 else 0;
> < (%o1) pr(n) := if primep(n) then 1 else 0
> < (%i2) countprimes(n):=sum(pr(i),i,1,n);
> < (%o2) countprimes(n) := sum(pr(i), i, 1, n)
> < (%i3) countprimes(10000);
> < (%o3) 1229
>
> I think that a bit of thought will show that it depends on the
> application. And, I don't know what you mean about relying on
> your system to remember values being dodgy. One must remember
> that values will survive redefinition unless the array is
> removed, but possibly you mean some more.
>
> Anyway, consider a case where recursive array functions shine:
>
> pr(n):=if primep(n) then 1 else 0$
> countprimes(n):=sum(pr(i),i,1,n)$
> remarray(pi)$
> pi[n]:=if n = 1 then 0 elseif primep(n) then pi[n-1]+1 else pi[n-1]$
> makelist(countprimes(i),i,1,500)$
> makelist(pi[i],i,1,500)$
>
> Evaluation took 6.5400 seconds (6.5800 elapsed) using 47.216 MB.
> Evaluation took 0.0500 seconds (0.0600 elapsed) using 479.297 KB.
>
> The recursive array function takes approximately 1/100 the time.
>
While I disagree with Alasdair's statement that recursive functions are
slow and inefficient, I think you're kind of cheating here. :-) Your
array function cheats because it memoizes previous computations. If
Alasdair's version were allowed to memoize previous results, I think it
would be quite fast too.
The nice thing about your array function is that the memoization is easy
to write and use and understand.
Ray