Computing big, certified Fibonacci numbers

I've written before about computing big Fibonacci numbers, and about creating a certificate to verify a Fibonacci number has been calculated correctly. This post will revisit both, giving a different approach to computing big Fibonacci numbers that produces a certificate along the way.

As I've said before, I'm not aware of any practical reason to compute large Fibonacci numbers. However, the process illustrates techniques that are practical for other problems.

The fastest way to compute thenth Fibonacci number for sufficiently largenis Binet's formula:

F_n= round( ⁿ / 5 )

where is the golden ratio. The point wheren is sufficiently large" depends on your hardware and software, but in my experience I found the crossover to be somewhere 1,000 and 10,000.

The problem with Binet's formula is that it requires extended precision floating point math. You need extra guard digits to make sure the integer part of your result is entirely correct. How many guard digits you'll need isn't obviousa priori. This post gave a way of detecting errors, and it could be turned into a method for correcting errors.

But how do we know an error didn't slip by undetected?This question brings us back to the idea of certifying a Fibonacci number. A number f Fibonacci number if and only if one of 5f² 4 is a perfect square.

Binet's formula, implemented in finite precision, takes a positive integern and gives us a numberf that is approximately thenth Fibonacci number. Even in low-precision arithmetic, therelative error in the computation is small. And because the ratio of consecutive Fibonacci numbers is approximately , an approximation to F_n is far from the Fibonacci numbers F_{n - 1} and F_{n + 1}. So the closest Fibonacci number to an approximation of F_n is exactly F_n.

Now iff is approximately F_n, then 5f² is approximately a square. Find the integer r minimizing |5f² - r^2|. In Python you could do this with the isqrt function. Then either r^2 + 4 or r^2 - 4 is divisible by 5. You can know which one by looking at r^2 mod 5. Whichever one is, divide it by 5 and you have the square of F_n. You can take the square root exactly, in integer arithmetic, and you have F_n. Furthermore, the numberr that you computed along the way is the certificate of the calculation of F_n.

The post Computing big, certified Fibonacci numbers first appeared on John D. Cook.