On Oct 4, 2007, at 11:15 , Gregory Hinton wrote:
On Oct 4, 2007, at 12:23 AM, Bert Freudenberg wrote:
On Oct 4, 2007, at 6:41 , Gregory Hinton wrote:
On Oct 3, 2007, at 7:31 AM, Michael Davies wrote:
If you're
interested in the numbers rather than the technique, there's a
couple
of alternative approaches to speed it up, iteration and matrix
manipulation.
Actually, in the case of the Fibonacci sequence, the best way to
speed it up is to use the closed-form formula:
nthFibonacci
|phi1 phi2 term1 term2|
phi1 := (1 + 5 sqrt) / 2.
phi2 := (1 - 5 sqrt) / 2.
term1 := phi1 raisedTo: self.
term2 := phi2 raisedTo: self.
^((term1 - term2) / (5 sqrt)) rounded.
Sorry, I realize the OP requested a recursive solution, but I
couldn't resist. :)
This is inaccurate for many numbers and fails for most:
"100 nthFibonacci" gives 354224848179262259200 (actually
354224848179261915075)
"1500 nthFibonacci" error
whereas the iterative version gives exact results and works as
long as we can store the result in memory. Iterative fib of 1500
takes 1.3 ms on my machine.
Hmmmm, good catch. I had overlooked the finite precision of
floating point.
Looks like it's accurate up to "75 nthFibonacci" but thereafter
diverges from reality.
This is why I prefer mathematics to computer science:
mathematicians can assume the existence of irrational numbers. ;)
Right. At least we use true Integers, in contrast to most popular
languages.
- Bert -
| 