Click here to Skip to main content
15,867,568 members
Articles / Programming Languages / C#
Tip/Trick

Fibonacci Without Loops or Recursion

Rate me:
Please Sign up or sign in to vote.
4.00/5 (5 votes)
17 Dec 2012CPOL 33.2K   9   17
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)


Written By
Architect
United States United States
Since I've begun my profession as a software developer, I've learned one important fact - change is inevitable. Requirements change, code changes, and life changes.

So..If you're not moving forward, you're moving backwards.

Comments and Discussions

 
GeneralThoughts Pin
PIEBALDconsult8-Sep-13 13:55
mvePIEBALDconsult8-Sep-13 13:55 
GeneralRe: Thoughts Pin
Andrew Rissing10-Sep-13 5:08
Andrew Rissing10-Sep-13 5:08 
Questionformula's missing part Pin
Yuksel YILDIRIM8-Sep-13 11:30
Yuksel YILDIRIM8-Sep-13 11:30 
AnswerRe: formula's missing part Pin
Andrew Rissing10-Sep-13 5:06
Andrew Rissing10-Sep-13 5:06 
GeneralRe: formula's missing part Pin
Yuksel YILDIRIM14-Oct-13 15:56
Yuksel YILDIRIM14-Oct-13 15:56 
GeneralMy vote of 2 Pin
YvesDaoust17-Dec-12 1:57
YvesDaoust17-Dec-12 1:57 
See comment
QuestionCan do better Pin
YvesDaoust17-Dec-12 1:51
YvesDaoust17-Dec-12 1:51 
AnswerRe: Can do better Pin
Andrew Rissing17-Dec-12 4:48
Andrew Rissing17-Dec-12 4:48 
AnswerRe: Can do better Pin
Andrew Rissing17-Dec-12 5:04
Andrew Rissing17-Dec-12 5:04 
GeneralRe: Can do better Pin
YvesDaoust17-Dec-12 5:32
YvesDaoust17-Dec-12 5:32 
GeneralRe: Can do better Pin
Andrew Rissing17-Dec-12 12:04
Andrew Rissing17-Dec-12 12:04 
GeneralRe: Can do better Pin
YvesDaoust17-Dec-12 20:34
YvesDaoust17-Dec-12 20:34 
GeneralRe: Can do better Pin
Andrew Rissing18-Dec-12 4:24
Andrew Rissing18-Dec-12 4:24 
GeneralMy vote of 5 Pin
Manish Choudhary .NET expert14-Dec-12 18:50
Manish Choudhary .NET expert14-Dec-12 18:50 
BugThis is correct only for n up to 70 Pin
Matt T Heffron13-Dec-12 12:12
professionalMatt T Heffron13-Dec-12 12:12 
GeneralRe: This is correct only for n up to 70 Pin
Andrew Rissing13-Dec-12 12:45
Andrew Rissing13-Dec-12 12:45 
GeneralRe: This is correct only for n up to 70 Pin
Andrew Rissing17-Dec-12 12:05
Andrew Rissing17-Dec-12 12:05 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.