[Newbies] Re: Beginners Digest, Vol 18, Issue 2
Gregory Hinton
gregory.hinton at gmail.com
Thu Oct 4 09:15:37 UTC 2007
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. ;)
More information about the Beginners
mailing list