[Haskell-cafe] Question about memory usage

[Andrew Coppin]

Roel van Dijk wrote:
> On Sat, Aug 14, 2010 at 5:41 PM, Andrew Coppin
> <andrewcoppin at btinternet.com> wrote:
>   
>>  (Then again, the Fibonacci numbers can be computed
>> in O(1) time, and nobody ever needs Fibonacci numbers in the first place, so
>> this is obviously example code.)
>>     
>
> A bit off-topic, but I don't think there exists a function that
> computes fibonacci numbers in O(1) time. There exists a closed-form
> expression to calculate the nth Fibonacci number, but the complexity
> of that expression is not O(1):
>
> phi = (1 + sqrt 5) / 2
> fib n = ((phi ** n) - (1 - phi) ** n) / sqrt 5
>
> The use of (**) should make the complexity at least O(n). Please
> correct me if I'm wrong (or sloppy).
>   

This depends on your definition of "operation".

As somebody else pointed out, if you're only dealing with 
limited-precision arithmetic, you can probably consider all the 
arithmetic operations to be O(1), in which case the Nth Fibonacci number 
is O(1). Only if you're dealing with utterly huge numbers do you need to 
even care about how long it takes to add two numbers.

This neatly leads us back to my second assertion: In all my years of 
computer programming, I've never seen one single program that actually 
*needs* the Fibonacci numbers in the first place (let alone in 
arbitrary-precision).