On Sun, 4 Apr 2010, Raymond Toy wrote:
< 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.
Cheating is the name of the game ;-).
Actually, even if you define
countprimes[n]:=countprimes(n);
the speed-up only occurs on the second call; in the first call,
countprimes(n) invokes primep n times. So in making a list of
function values of length n, you need n*(n+1)/2 calls to primep.
On the other hand, in making a list of function values of pi[n],
primep is called ~n times.
Even if you memorize the primep function, the recursive array function
is still faster.
pr[n]:=if primep(n) then 1 else 0$ /* memorize primep */
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 1.4000 seconds (1.4100 elapsed) using 19.547 MB.
Evaluation took 0.0600 seconds (0.0600 elapsed) using 479.297 KB.
There is a noticeable speed-up, but only by 4x not 100x. I guess the
overhead of using sum must be pretty large.
<
< The nice thing about your array function is that the memoization is easy
< to write and use and understand.
Ok, I did cheat in my choice of test.
Leo
--
The University of Edinburgh is a charitable body, registered in
Scotland, with registration number SC005336.