Computing Fibonacci Numbers

Multiplication Speed

One thing to remember is that multiplying very large integers and multiplying very precise decimals end up being roughly the same speed. If we compute $\phi \sqrt{5}$ to 10 decimal digits of precision, we have the multiplication $1.618033989 \times 2.236067978$. If we wanted to, we could multiply $1618033989 \times 2236067978$ and then just shift the decimal place back when we're done.

To get the right answer at the end of Binet's formula, we need a little more precision than there are decimal digits in the answer. The final result only has to have the first decimal digit correct to round properly, but rounding errors can accumulate, and we're always leaving out the factor of $\psi^n$. That means our working precision needs to be higher than the number of digits in the answer by a fair margin: I'm using a 1% buffer (defaulting to Python's 53-bit precision as a minimum), which works for all of the tests I'm doing.

Here I've done a rudimentary test of the speed of computing this product with different levels of precision. We plot on a log-log scale—the straight line at the end is an exponential curve.¹ We can see that, once we get values large enough that the meat of the computation dominates everything else, multiplying very precise decimals and very large integers has essentially the same time cost.