Methods to compute the n-th Fibonacci number:

• O(N) DP using the recurrence: fib(n) = fib(n-1) + fib(n-2)
• O(logN) matrix exponentiation
• O(1) approximation: (phi^n-(1/phi^n))/sqrt(5), correct up to fib(69) using doubles

Properties:

Zeckendorf's theorem:

Every positive integer can be written in a unique way as a sum of one or more distinct Fibonacci numbers such that the sum does not include any 2 consecutive Fibonacci numbers.

It can be computer by greedily subtracting the largest possible Fibonacci number until the integer is zero.