Alternative Fibonacci implementation

· 3 min read

PostsProjectsResumeAboutGitHubhanskruse.eu

On Scott Hanselman’s blog there was another formula for Fibonacci that uses the golden ratio and some Mathemagic to calculate Fib(n). This formula is more useful if you want to calculate Fib(n) for a certain n and if you are not interested in the sequence. I used this formula in an alternative implementation of my FibEnumerable just to test for correctness.

' Fibonacci.vb created with MonoDevelop
' User: kruse at 14:10 22-1-2009
'
' To change standard headers go to Edit->Preferences->Coding->Standard Headers
'

Option Explicit On
Option Strict On

Imports System
Imports System.Collections
Imports System.Collections.Generic

Namespace EUNemopolis.Math
 Public Class FibEnumerable2
 Inherits IntegerEnumerable

  Protected Overrides Function NewEnumerator() as IEnumerator
   return New FibEnumerator()
  End Function

     Private Class FibEnumerator
     Inherits IntegerEnumerable.IntegerEnumerator
   Private const MAXN As Integer =45 'The maximum n for which Fib(n) fits in an integer
   Private _n As Integer

   Private Readonly Shared GoldenRation as Double = _
   (1.0 + System.Math.Sqrt(5.0)) / 2.0

   Public Function MoveNext() As Boolean _
   Implements System.Collections.IEnumerator.MoveNext
       if _n<MAXN then
        _n=_n+1
        if _n<2 then
         SetCurrent(_n)
        else
         Dim newCurrent as Integer
         newCurrent= _
         System.Math.Floor((System.Math.Pow(GoldenRation, _n) - _
         System.Math.Pow((1.0 - GoldenRation), _n)) / _
         System.Math.Sqrt(5.0))
         SetCurrent(newCurrent)
        End If
        Return True
       Else
        Return False
       End If
      End Function

   Protected Overrides Sub Init()
   'illegal value first. Foreach does a movenext
   'first before reading current value
    _n=-1
    SetCurrent(_n)
   End Sub
     End Class
    End Class
End Namespace

To see whether this gives the same result as the original implementation I altered my main program. I walk the sequence for n=0 up to and including n=45 for both implementations. I cache the results for the first implementation. In the second foreach loop I print the results for both implementations and the difference between them. If all is correct all differences should be zero. I can use both a list or a simple array for storing the results. I chose an array here just for having used array in VB.Net. I never use arrays in C#.

' Application.vb created with MonoDevelop
' User: kruse at 9:50 20-1-2009
'
' To change standard headers go to Edit->Preferences->Coding->Standard Headers
'
Imports System.Collections
Imports System.Collections.Generic
Imports EUNemopolis.Math
NameSpace EUNemopolis

Public Class Application
 Public Shared Sub Main()
  System.Console.WriteLine("Hello world!")
     Dim fibseq as IEnumerable(Of Integer)=new FibEnumerable()
     Dim fib as Integer
     Dim cache(45) as Integer
  Dim i as Integer
  i=-1
     for each fib in fibseq
      i=i+1
      cache(i)=fib
     next
     fibseq=new FibEnumerable2()
     i=-1
     for each fib in fibseq
      i=i+1
      cache(i)=fib
      System.Console.Writeline(String.Format("{0:d},{1:d},{2:d},{3:d}",i,fib,cache(i),fib-cache(i)))
     next
 End Sub
End Class
End NameSpace

And indeed the algorithm is correct for n=0 up to and including n=45. When you run it you will always see zero as the last value of the print statement.

Tags: vb.net