Computing Fibonacci Numbers

Python has a lot of features that are convenient for math. One of them is operator overloading, or changing how +, -, *, etc., work. We can use this to make numbers of the form $a + b \sqrt{5}$ easy to work with. Using this feature, we can make a custom Z5 object (so called because the mathematical way of describing this group of numbers is $\mathbb{Z}(\sqrt{5})$) that represents one of these numbers.

If we play our cards right, we never even need to compute $\sqrt{5}$. Let's look at the full unrounded version of Binet's formula:

$$F(n) = \frac{(1 + \sqrt{5}) ^ n - (1 - \sqrt{5})^n}{2^n \sqrt{5}}$$

Similarly to how complex conjugates work, it turns out that $(1 - \sqrt{5})^n$ will simply be $(1 + \sqrt{5})^n$ with the sign of the $\sqrt{5}$ coefficient flipped. This is why Binet's formula always gives an integer result: the integral parts cancel, and the $\sqrt{5}$ will cleanly cancel without ever having to be computed. Dividing by powers of 2 is very simple for computers, because that's just chopping off zeros in binary. This lets us implement a new Fibonacci function, as seen opposite.¹