[Haskell-cafe] Question about memory usage
Andrew Coppin
andrewcoppin at btinternet.com
Mon Aug 16 14:37:55 EDT 2010
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).
More information about the Haskell-Cafe
mailing list