[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