[Newbies] Re: Beginners Digest, Vol 18, Issue 2

[Bert Freudenberg]

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 -