I love it when elegant mathematical formulas help you solve programming problems seamlessly.

Nth Fib number in constant time? Yes please!

@Limitcycle Uh, there is no algorithm which computes the nth fibonacci number in constant time. The best algorithm is \(O(\log n)\) for smallnums.

@Limitcycle I don't understand what you mean by "constant time" then.

@axiom it is O(1) as the size of n is independent of the time it takes for the program to return the nth Fibonacci number. If n=1 or n=10,000, it will return the answer in the same amount of time.

@axiom the drawback however is that the formula uses the Golden ratio, which is infinitely long, so after some n the program fails in returning the correct nth Fib number due to the computers finite precision

@Limitcycle Hmm, I guess I believe that since it is possible to do float exponentiation in constant time...

@Limitcycle I suspect though that this method is much worse in both practical runtime and range of inputs than the simple matrix-squaring algorithm.


@axiom you would probably be right. The formula (and thus the program) is given by defining a function Fib(n) that returns \((phi^n) - (-phi)^(-n))/sqrt(5)\ where phi = the Golden ratio, and the returned number is the nth Fib number

@Limitcycle one small improvement is to not bother with the \(-\phi^n\) term since you can just round instead

Sign in to participate in the conversation

A Mastodon instance for maths people. The kind of people who make \(\pi z^2 \times a\) jokes.

Use \( and \) for inline LaTeX, and \[ and \] for display mode.