Fibonacci Calculator
A simple fibonacci calculator with a few different approaches to get fib(n)
Motivation
I wanted to check out Rust for quite some time now, and finally convinced myself to try myself at it. This was also a great opportunity to get to know the rust ecosystem and especially cargo.
Features
This Calculator has the basic functionality implemented to calculate any fib(n) that fits inside a unsigned 128-bit integer for the precise methods or a 64-bit float for the approximation.
Approaches to fib(n)
Recursive
The first and most commonly seen approach is the recursive one. You quickly define the three following rules:
- fib(0) = 0
- fib(1) = 1
- fib(n) = fib(n-1) + fib(n-2)
and we’re all set! 🥳
Problem: This approach is extremely inefficient and slow the bigger the input n gets. The core reason is that we calculate many values repeatedly instead of using the known solution. This can easily be fixed by caching all prior results but it still is recursive and needs a cache to be even remotely efficient.
Iterative
TODO: put content here
Approximative
We can also make use of Binet's Formula.
$$ fib(n) = \frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt{5}}{2}\right)^{n} -\left(\frac{1-\sqrt{5}}{2}\right)^{n}\right] $$