13,198,465 members (62,871 online)
Tip/Trick
alternative version

Stats

17.2K views
8 bookmarked
Posted 13 Dec 2012

Fibonacci Without Loops or Recursion

, 17 Dec 2012
 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.

You may also be interested in...

 Pro

 First Prev Next
 Thoughts PIEBALDconsult8-Sep-13 13:55 PIEBALDconsult 8-Sep-13 13:55
 Re: Thoughts Andrew Rissing10-Sep-13 5:08 Andrew Rissing 10-Sep-13 5:08
 formula's missing part Member 33856988-Sep-13 11:30 Member 3385698 8-Sep-13 11:30
 Re: formula's missing part Andrew Rissing10-Sep-13 5:06 Andrew Rissing 10-Sep-13 5:06
 Re: formula's missing part Yuksel YILDIRIM14-Oct-13 15:56 Yuksel YILDIRIM 14-Oct-13 15:56
 My vote of 2 YvesDaoust17-Dec-12 1:57 YvesDaoust 17-Dec-12 1:57
 Can do better YvesDaoust17-Dec-12 1:51 YvesDaoust 17-Dec-12 1:51
 Re: Can do better Andrew Rissing17-Dec-12 4:48 Andrew Rissing 17-Dec-12 4:48
 Re: Can do better Andrew Rissing17-Dec-12 5:04 Andrew Rissing 17-Dec-12 5:04
 Re: Can do better YvesDaoust17-Dec-12 5:32 YvesDaoust 17-Dec-12 5:32
 This opens the way to deeper thinking on the problem. Considering all formulas of the form `Round(A.B^N)`, many values of parameters `A` and `B` will return correct integers for a number of values of `N`. There should be a way to maximize this range. For instance, let us keep `B = Phi` exactly. We need to have `Fk <= A.Phi^k + 0.5 < Fk + 1` for all `k`'s in range `0..N`. In other words, `(Fk - 0.5) / Phi^k <= A < (Fk + 0.5) / Phi^k`. Unless I am wrong, the intervals are nested so that the most constraining value is `k = N` and any `A` in range `(FN - 0.5) / Phi^N <= A < (FN + 0.5) / Phi^N` can do. More freedom is obtained by letting `B` vary as well. And we can even introduce an extra degree of freedom by using the more general form `Floor(A.B^N + C)` without complicating the formula so much.modified 17-Dec-12 11:50am.
 Re: Can do better Andrew Rissing17-Dec-12 12:04 Andrew Rissing 17-Dec-12 12:04
 Re: Can do better YvesDaoust17-Dec-12 20:34 YvesDaoust 17-Dec-12 20:34
 Re: Can do better Andrew Rissing18-Dec-12 4:24 Andrew Rissing 18-Dec-12 4:24
 My vote of 5 Manish Choudhary .NET expert14-Dec-12 18:50 Manish Choudhary .NET expert 14-Dec-12 18:50
 This is correct only for n up to 70 Matt T Heffron13-Dec-12 12:12 Matt T Heffron 13-Dec-12 12:12
 Re: This is correct only for n up to 70 Andrew Rissing13-Dec-12 12:45 Andrew Rissing 13-Dec-12 12:45
 Re: This is correct only for n up to 70 Andrew Rissing17-Dec-12 12:05 Andrew Rissing 17-Dec-12 12:05
 Last Visit: 31-Dec-99 18:00     Last Update: 21-Oct-17 15:51 Refresh 1