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.

@axiom not algorithm, formula.

@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

@Limitcycle er $(-\phi)^{-n}$

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.