Calculating the Nth Fibonacci Number – C#

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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

Create a website or blog at WordPress.com

Up ↑

%d bloggers like this: