idiom for recurrence relations
- To: mathgroup at smc.vnet.net
- Subject: [mg26714] idiom for recurrence relations
- From: maharrix at my-deja.com
- Date: Thu, 18 Jan 2001 00:57:18 -0500 (EST)
- Sender: owner-wri-mathgroup at wolfram.com
I have a problem which is mostly esthetic, but could have efficiency
repercussions. First, the general question: What is the best way to
implement recurrence relations (e.g. Fibonacci[n])?
The obvious and simplest way is to define base cases and an inductive
case (I'll use Fibonnaci as the generic example:
F[0]:=0; F[1]:=1; F[n_]:=F[n-1]+F[n-2]
). This can be sped up using memoization F[n_]:=F[n]=... Great, but this
fills up internal memory (nothing can get garbage collected since all
the computed values must hang around forever; this can be bad when you
have lots of recurrence relations, graphics and a long session).
So the next solution would be to implement it as an imperative program
keeping only the necessary values to compute the next in the sequence
(e.g.
While[i<=n,temp=f2; f2=f2+f1; f1=temp;i++]
). Again, great, but the Mathematica docs repeatedly say that list operations
are much faster than imperative ones.
So my solution is to use Nest:
F[n_] := First@Nest[{#[[2]], #[[2]]+#[[1]]} &, {0, 1}, n]];
Is this the best (fastest, simplest, most appropriate, or most memory
efficient, etc.) way to do it? It seems somehow ugly (too many [[, #,
etc.) but it is shorter in number of characters to encode it (not what I
would usually consider highest on my list of things to optimize (but
that's not to say terribly low either))
The whole point is to be able to create recurrence relations easily in a
single function efficiently. I'd also like to create them as lambdda
functions (as above, as Function[pair, {pair[[2]],pair[[2]]+pair[[1]]}]
)
So, how do the above rate and what are the reasonable alternatives?
Thanks for any help,
Mitch
Sent via Deja.com
http://www.deja.com/
- Follow-Ups:
- Re: idiom for recurrence relations
- From: Daniel Lichtblau <danl@wolfram.com>
- Re: idiom for recurrence relations