Computing Fibonacci NumbersThis is fast. Computing the billionth Fibonacci number takes less than ten seconds on my machine.1 Take a second to think of how far we've come!
Now that we're at the mountaintop, let me take a second to give credit where credit is due. This algorithm was, as far as I can find, first implemented in the [GNU MP](gmplib.org) library I've been using for arithmetic this whole time. I believe it is due to Kevin Ryde, and it was first added in June 2001.
The formulas are surprisingly obscure—most references don't mention them, even the ones concerned with efficiently computing Fibonacci numbers. If you've made it this far, you've learned more about Fibonacci numbers than more or less anyone. There's no reason some even faster approach isn't out there, but it's extremely difficult to imagine any improvements to the core algorithm at this point. Feel free to prove me wrong!2
As a final victory lap, I'll show benchmarks for all of the algorithms we've talked about and summarize what we've accomplished and learned.
- I did say ten billion in the intro, didn't I? That takes around 90 seconds on my machine.↩
- There are a couple things I tried that might be a good starting point for you. There are formulas you can derive for , , and so on: a clever rewriting trick similar to the one above might allow you to compute and the values around it with fewer than 4 squares, for example, which would be faster than doing the formula twice. There are a lot of other identities as well: https://r-knott.surrey.ac.uk/Fibonacci/fibFormulae.html has a relatively long list, although there are so many out there. There's also definitely a lot of uncharted territory in the realm of computing Fibonacci numbers using GPUs or multiple computer cores.↩
82862 82862
This is fast. Computing the billionth Fibonacci number takes less than ten seconds on my machine.1 Take a second to think of how far we've come!
Now that we're at the mountaintop, let me take a second to give credit where credit is due. This algorithm was, as far as I can find, first implemented in the [GNU MP](gmplib.org) library I've been using for arithmetic this whole time. I believe it is due to Kevin Ryde, and it was first added in June 2001.
The formulas are surprisingly obscure—most references don't mention them, even the ones concerned with efficiently computing Fibonacci numbers. If you've made it this far, you've learned more about Fibonacci numbers than more or less anyone. There's no reason some even faster approach isn't out there, but it's extremely difficult to imagine any improvements to the core algorithm at this point. Feel free to prove me wrong!2
As a final victory lap, I'll show benchmarks for all of the algorithms we've talked about and summarize what we've accomplished and learned.
- I did say ten billion in the intro, didn't I? That takes around 90 seconds on my machine.↩
- There are a couple things I tried that might be a good starting point for you. There are formulas you can derive for , , and so on: a clever rewriting trick similar to the one above might allow you to compute and the values around it with fewer than 4 squares, for example, which would be faster than doing the formula twice. There are a lot of other identities as well: https://r-knott.surrey.ac.uk/Fibonacci/fibFormulae.html has a relatively long list, although there are so many out there. There's also definitely a lot of uncharted territory in the realm of computing Fibonacci numbers using GPUs or multiple computer cores.↩
82862 82862