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

Nth Fib number in constant time? Yes please! #math #programming

@axiom not algorithm, formula.

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

Follow

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

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

SG@Limitcycle@mathstodon.xyz@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