Click here to Skip to main content
65,938 articles
CodeProject is changing. Read more.
Articles / Languages / C#

Fibonacci Without Loops or Recursion

4.00/5 (5 votes)
17 Dec 2012CPOL 36.1K  
A method for calculating a Fibonacci number without using loops or recursion.

Introduction

While reading one of our Insider News posts which linked to Evan Miller's site,  he mentioned a mathematical means of producing a Fibonacci number without using loops or recursion.   I decided to post the C# version of it here, but in no way do I claim credit to creating this.   I thought it was interesting enough to share for those who might not read the Insider News articles.  

You can read more about this closed-form solution on wiki.

The Code

C#
public static long Fibonacci(long n)
{
    return (long)Math.Round(0.44721359549995682d * Math.Pow(1.6180339887498949d, n));
}   

NOTE: Due to limits of precision, the preceding formula is only accurate up to n = 77. 

UPDATE

Based on YvesDaoust's recommendation, I've updated the formula to use a simpler version of the closed form solution (also found on Wiki), as it proves to be faster and more compact.

Furthermore, I've adjusted the constants slightly to improve the function's accuracy.

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)