Finds the nth Fibonacci number, starting at n = 0,
$python nthFibonacci 100
Python 2.7 and the Python math library.
The code uses the matrix exponential algorithm detailed here:
The code is tested using the script testnthFibonacci.py run with:
$ python testnthFibonacci.py
There are several ways to solve this, I looked at 3.
a. Simple recursion
if n == 0:
elif n == 1:
This is neat but will be O(x^n) complex and use O(n) in memory space.
b. Use the Binet formula:
Fn = round(phi^n/sqrt(5)) Tried this first. It is a single calculation, so is independant of n for speed and memory. Unfortunately it runs into resolution errors for n > 70. This could be improved using packages like bigfloat, but these are not custom in Python.
c. The matrix exponential algorithm, using the expressions:
F(2n) = ( 2 F(n-1) - F(n) ) F(n)
F(2n-1) = Fn^2 + F(n-1)^2
see : https://en.wikipedia.org/wiki/Fibonacci_number#Matrix_form
It recursively halves the stack, so grows by O(log2(n)) in both time and memory.