Fibonacci Numbers
Windows only

by Dale Fugier (Last updated:  Wednesday, December 5, 2018)

Overview

By definition, Fibonacci numbers are a series of numbers where the first two Fibonacci numbers are 0 and 1, and each remaining number is the sum of the previous two.

The formula for calculating Fibonacci numbers is: F(n)=F(n−1)+F(n−2)

with seed values: F(0)=0 and F(1)=1

There are a number of methods that one can use to calculate these numbers. Here are a few…

Recursion

You can calculate Fibonacci numbers using a recursive function…

'''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
' Compute Fibonacci number using recursion
'''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
Function Fib_1(n)
  If (n < 2) Then
    Fib_1 = n
  Else
    Fib_1 = Fib_1(n-1) + Fib_1(n-2)
  End If
End Function

…but, it is not always the fastest method.

Dynamic Iteration

One of the reasons the recursive algorithm can be slow is we keep recomputing the same subproblems over and over again. In this iterative approach, we solve each subproblem once and then look up the solution later when we need it instead of repeatedly recomputing it…

'''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
' Compute Fibonacci number using dynamic iteration
'''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
Function Fib_2(n)
  Dim f, i
  If (n < 2) Then
    Fib_2 = n
  Else
    ReDim f(n-1)
    f(0) = 1
    f(1) = 1
    For i = 2 To n - 1
      f(i) = f(i-1) + f(i-2)
    Next
    Fib_2 = f(n-1)
  End If
End Function

Space Complexity Iteration

It turns out that the dynamic iteration can be modified to use a much smaller amount of space. Each step through the loop uses only the previous two values of F(n), so instead of storing these values in an array, we can simply use two variables. This requires some swapping around of values so that everything stays in the appropriate places.

'''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
' Compute Fibonacci number using space complexity iteration
'''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
Function Fib_3(n)
  Dim a, b, c, i
  If (n < 2) Then
    Fib_3 = n
  Else  
    a = 1
    b = 1
    For i = 2 To n -1
      c = a + b
      a = b
      b = c
    Next           
    Fib_3 = b
  End If
End Function

Binet’s Formula

Binet’s Formula for calculating the nth Fibonacci number is fast because it uses neither recursion nor iteration…

'''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
' Compute Fibonacci number using Binet's formula
'''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
Function Fib_4(n)
   Fib_4 = Round(((Sqr(5) + 1) / 2) ^ n / Sqr(5))
End Function

Testing

You can use the following test code to benchmark the above functions:

'''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
' Tests the Fibonacci functions
'''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
Sub TestFibonacci
 
  Dim s, a, n, i, st, et
 
  a = Array("Recursion", "Dynamic", "Space", "Binet")
  s = Rhino.GetString("Fibonacci algorithm to use",,a)
  If IsNull(s) Then Exit Sub
 
  n = Rhino.GetInteger("Number of iterations", 20, 1, 100)
  If IsNull(n) Then Exit Sub
 
  Select Case s
    ' Iterative
    Case "Recursion"
      st = Timer
      For i = 0 To n - 1
        Rhino.Print Fib_1(i)
      Next
      et = Timer
    ' Recursive
    Case "Dynamic"
      st = Timer
      For i = 0 To n - 1
        Rhino.Print Fib_2(i)
      Next
      et = Timer
    ' Space
    Case "Space"
      st = Timer
      For i = 0 To n - 1
        Rhino.Print Fib_3(i)
      Next
      et = Timer
    'Binet  
    Case Else
      st = Timer
      For i = 0 To n - 1
        Rhino.Print Fib_4(i)
      Next
      et = Timer
  End Select
 
  Call Rhino.Print(s & " calculation completed in " & FormatNumber(et-st,3) & " seconds.")
 
End Sub