Tip/Trick

# Fibonacci Without Loops or Recursion

, 17 Dec 2012 CPOL
 Rate this:
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.

## 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.

## 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.

## Share

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

 First Prev Next
 Thoughts PIEBALDconsult 8-Sep-13 14:55
 Re: Thoughts Andrew Rissing 10-Sep-13 6:08
 formula's missing part Member 3385698 8-Sep-13 12:30
 Re: formula's missing part Andrew Rissing 10-Sep-13 6:06
 Re: formula's missing part Yuksel YILDIRIM 14-Oct-13 16:56
 My vote of 2 YvesDaoust 17-Dec-12 2:57
 Can do better YvesDaoust 17-Dec-12 2:51
 Re: Can do better Andrew Rissing 17-Dec-12 5:48
 Re: Can do better Andrew Rissing 17-Dec-12 6:04
 Re: Can do better [modified] YvesDaoust 17-Dec-12 6:32
 Re: Can do better Andrew Rissing 17-Dec-12 13:04
 Re: Can do better YvesDaoust 17-Dec-12 21:34
 Re: Can do better Andrew Rissing 18-Dec-12 5:24
 My vote of 5 Manish Choudhary .NET expert 14-Dec-12 19:50
 This is correct only for n up to 70 Matt T Heffron 13-Dec-12 13: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++) { swCF.Start(); long cf = FibonacciCF(i); swCF.Stop(); swLoop.Start(); long lp = FibonacciLoop(i); swLoop.Stop(); if (cf != lp) { if (rep == 0) { // only report this ONCE!! Console.WriteLine("mismatch at {0}: cf={1} lp={2}", i, cf, lp); } break; } } } 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..."); Console.ReadLine(); }   // 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)) / SquareRootOf5)); } 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; } } ```
 Re: This is correct only for n up to 70 Andrew Rissing 13-Dec-12 13:45
 Re: This is correct only for n up to 70 Andrew Rissing 17-Dec-12 13:05
 Last Visit: 31-Dec-99 19:00     Last Update: 29-Mar-15 17:13 Refresh 1