Efficient Fibonacci Algorithms

Fibonacci has a closed-form solution! Forget writing loops, you can write one damn equation. Runs in constant time.

You mean how fast can it compute fib(40) without memorization? ;)

that Fibonacci implementation has exponential complexity

The "right" way to do Fibonacci is to use matrix multiplication to get the nth Fibonacci number in logarithmic time (google Fibonacci log n matrix).

This isn't faster unless you diagonalize the matrix. Then you get the closed form for fibonacci

I just ran it, fib is roughly six times faster

aka "How not to implement Fibonacci sequence"

Is this the next "how fast is Fibonacci" fiasco?

oh, fibonacci numbers, why do i take 10 seconds to figure it out

I was recently asked to calculate the fibonacci sequence value in an O(log n) time complexity. I had no clue how to do it and explained that I can solve it in O(N) easily but don't even know how to approach the O(log n) method. I knew there must be some trick using factors but didn't even know how to start the problem. I looked it up later and one of the ways is using matrix multiplication (an implementation I still wouldn't be able to do without seeing pseudocode).