Click here to Skip to main content
13,000,982 members (69,474 online)
Click here to Skip to main content
Add your own
alternative version


8 bookmarked
Posted 13 Dec 2012

Fibonacci Without Loops or Recursion

, 17 Dec 2012
Rate this:
Please Sign up or sign in to vote.
A method for calculating a Fibonacci number without using loops or recursion.


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

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. 


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.


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


About the Author

Andrew Rissing
Software Developer (Senior)
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.

You may also be interested in...

Comments and Discussions

GeneralThoughts Pin
PIEBALDconsult8-Sep-13 13:55
professionalPIEBALDconsult8-Sep-13 13:55 
GeneralRe: Thoughts Pin
Andrew Rissing10-Sep-13 5:08
memberAndrew Rissing10-Sep-13 5:08 
Questionformula's missing part Pin
Member 33856988-Sep-13 11:30
memberMember 33856988-Sep-13 11:30 
AnswerRe: formula's missing part Pin
Andrew Rissing10-Sep-13 5:06
memberAndrew Rissing10-Sep-13 5:06 
GeneralRe: formula's missing part Pin
Yuksel YILDIRIM14-Oct-13 15:56
memberYuksel YILDIRIM14-Oct-13 15:56 
GeneralMy vote of 2 Pin
YvesDaoust17-Dec-12 1:57
memberYvesDaoust17-Dec-12 1:57 
QuestionCan do better Pin
YvesDaoust17-Dec-12 1:51
memberYvesDaoust17-Dec-12 1:51 
AnswerRe: Can do better Pin
Andrew Rissing17-Dec-12 4:48
memberAndrew Rissing17-Dec-12 4:48 
AnswerRe: Can do better Pin
Andrew Rissing17-Dec-12 5:04
memberAndrew Rissing17-Dec-12 5:04 
GeneralRe: Can do better Pin
YvesDaoust17-Dec-12 5:32
memberYvesDaoust17-Dec-12 5:32 
GeneralRe: Can do better Pin
Andrew Rissing17-Dec-12 12:04
memberAndrew Rissing17-Dec-12 12:04 
GeneralRe: Can do better Pin
YvesDaoust17-Dec-12 20:34
memberYvesDaoust17-Dec-12 20:34 
GeneralRe: Can do better Pin
Andrew Rissing18-Dec-12 4:24
memberAndrew Rissing18-Dec-12 4:24 
GeneralMy vote of 5 Pin
Manish Choudhary .NET expert14-Dec-12 18:50
memberManish Choudhary .NET expert14-Dec-12 18:50 
BugThis is correct only for n up to 70 Pin
Matt T Heffron13-Dec-12 12:12
memberMatt T Heffron13-Dec-12 12:12 
This is correct only for the first 70 Fibonacci numbers.
At number 71 the closed form is 1 too big:
308061521170130 closed form
308061521170129 loop
Presumably, this is due to rounding errors and precision becoming significant.
Changing the Math.Round() to Math.Floor() only gets you one additional correct value.

Also, on average over computing the 70 values, the closed form is about 25% slower.

  using System;
  using System.Diagnostics;
  class Program
    static void Main(string[] args)
      Stopwatch swCF = new Stopwatch();
      Stopwatch swLoop = new Stopwatch();
      const int repeats = 10000;
      for (int rep = 0; rep < repeats; rep++)
        for (long i = 1; i <= 100; i++)
          long cf = FibonacciCF(i);
          long lp = FibonacciLoop(i);
          if (cf != lp)
            if (rep == 0)
              // only report this ONCE!!
              Console.WriteLine("mismatch at {0}: cf={1} lp={2}", i, cf, lp);
      Console.WriteLine("Repeats = {0}", repeats);
      Console.WriteLine("Closed form time: {0}", TimeSpan.FromTicks(swCF.ElapsedTicks));
      Console.WriteLine("Loop time: {0}", TimeSpan.FromTicks(swLoop.ElapsedTicks));
      Console.WriteLine("Press Enter to complete...");
    // compute sqrt(5) only once, outside of timing.
    private static readonly double SquareRootOf5 = Math.Sqrt(5.0d);
    public static long FibonacciCF(long n)
      //double SquareRootOf5 = Math.Sqrt(5.0d);
      return (long)Math.Round((
          (Math.Pow(0.5d + 0.5d * SquareRootOf5, n) -
          Math.Pow(0.5d - 0.5d * SquareRootOf5, n)) /
    public static long FibonacciLoop(long n)
      long prev = 0;
      long curr = 1;
      for (long i = 1; i < n; i++)
        long oldprev = prev;
        prev = curr;
        curr += oldprev;
      return curr;

GeneralRe: This is correct only for n up to 70 Pin
Andrew Rissing13-Dec-12 12:45
memberAndrew Rissing13-Dec-12 12:45 
GeneralRe: This is correct only for n up to 70 Pin
Andrew Rissing17-Dec-12 12:05
memberAndrew 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.

Permalink | Advertise | Privacy | Terms of Use | Mobile
Web02 | 2.8.170624.1 | Last Updated 17 Dec 2012
Article Copyright 2012 by Andrew Rissing
Everything else Copyright © CodeProject, 1999-2017
Layout: fixed | fluid