Fibonacci Calculator

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:

1. fib(0) = 0
2. fib(1) = 1
3. 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] $$

Sources

#

Gitlab Repository