Computing Fibonacci Numbers

The Best of Both Worlds

What if we could use Binet's formula without needing this extra precision early on?

When you compute values involving square roots by hand, I imagine you probably wait until the end and only then pull out a calculator if you need the answer in decimal. For example, if you're computing $(1 + \sqrt{2})(3 + \sqrt{2})$, you might first just work the exact answer by expanding the product, getting $5 + 4 \sqrt{2}$, and then computing this to whatever precision you need.

We can steal this approach. In the same way that complex numbers result by adding a new element $i = \sqrt{-1}$ and all of the new numbers you can make by adding and multiplying it with the existing ones, we can imagine setting $j = \sqrt{5}$ and representing numbers as $a + bj$.

Let's write out the rules of adding and multiplying in this new number system:

$$\gdef\zv#1#2{#1 + #2 \sqrt{5}} \begin{aligned} \left(\zv{a}{b}\right) + \left(\zv{c}{d}\right) &= \zv{\left(a + c\right)}{\left(b + d\right)} \\ \left(\zv{a}{b}\right) \times \left(\zv{c}{d}\right) &= ac + ad \sqrt{5} + bc \sqrt{5} + bd \sqrt{5} \sqrt{5} \\ &= \zv{(ac + 5bd)}{(ad + bc)} \\ \end{aligned}$$