Fibonacci Numbers

Program to compute the Fibonacci numbers, where F₀ = 0, F₁ = 1, and for all n >= 2, F_n is defined as F_n-1 + F_n-2.

The repo contains 3 algorithms to compute the Fibonacci numbers:

fib_recursive.cpp: recursive implementation (non-memoized), runs in O(2ⁿ) time
fib_iterative.cpp: iterative solution, runs in O(n) time and O(1) space
fib_matrix.cpp: matrix solution, runs in O(log n) time

The algorithms each contain mod implementations where computations are done mod 65536 to prevent integer overflow.

Time calculations can be found in Fibonacci_Times.ipynb.

Name		Name	Last commit message	Last commit date
Latest commit History 11 Commits
output		output
Fibonacci_Times.ipynb		Fibonacci_Times.ipynb
README.md		README.md
fib_iterative.cpp		fib_iterative.cpp
fib_iterative.hpp		fib_iterative.hpp
fib_matrix.cpp		fib_matrix.cpp
fib_matrix.hpp		fib_matrix.hpp
fib_recursive.cpp		fib_recursive.cpp
fib_recursive.hpp		fib_recursive.hpp
fib_test.cpp		fib_test.cpp
fib_test.hpp		fib_test.hpp
main.cpp		main.cpp

Provide feedback