Roel van Dijk wrote:
On Sat, Aug 14, 2010 at 5:41 PM, Andrew Coppin
<andrewcop...@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).
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
