Not a year passes anymore without someone asking me about the rabbit problem. I’m sure you’re the same.
The Fibonacci sequence starts with 0 and 1. Each subsequent number is simply the sum of the previous 2 numbers.
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144
Most code based solutions I’ve seen use some form of recursion to calculate each Fibonacci number up to the required value of n. For larger numbers, this can be very slow. Here’s a simple implementation of Binet’s formula, which uses magic* rather than recursion.
* The magic part of the formula is the golden ratio, which is the ratio between each number in the sequence, and is nearly exactly the same for any 2 sequential numbers, no matter how high the numbers get. This, and many other amazing properties make the sequence one of the most fascinating and beautiful subjects in mathematics.
The method above is limited to +/- 92 values. Any higher or lower, and we wouldn’t be able to store the result in a long type (Int64).
If anyone spots any mistakes in my implementation, let me know in the comments. Any suggestions for ways to make this perform more efficiently are also welcome.