'This file is named fibonacci.vb
'to do: use memoization to avoid long runtimes with the recursive function
'also practices using arrays

Imports System
Imports Microsoft.VisualBasic
Public Module FibonacciNumbers

'global array for memoized solution
Dim mem(100) As Double

'**********************************************************
' Iterative solution (using loops)
'**********************************************************
   Function fib_i(ByVal x As Integer) As Double
      Dim i As Integer
      Dim p1, p2, sum As Double

      p1 = 1
      p2 = 1
      For i = 3 To x
         sum = p1 + p2
         p1 = p2
         p2 = sum
      Next i
      fib_i = sum
   End Function

'**********************************************************
' Recursive function without memoization (very inefficient)
'**********************************************************
   Function fib_r(ByVal x As Integer) As Double
      if x<=2 then
         fib_r = 1
      else
         fib_r = fib_r(x-1) + fib_r(x-2)
      end if
   End Function

'**********************************************************
' Recursive function using memoization
'**********************************************************
   Function fib_rmemo(ByVal x As Integer) As Double
      if x<=2 then
         fib_rmemo = 1
      else
         if mem(x-1) = -1 Then mem(x-1) = fib_rmemo(x-1)
         if mem(x-2) = -1 Then mem(x-2) = fib_rmemo(x-2)
         fib_rmemo = mem(x-1) + mem(x-2)
      end if
   End Function


   Sub Main()
      Dim j As Integer
      Dim k, l, m As Double
      Dim startTime, endTime As Date
      Dim diffTime As TimeSpan

'Dim OldTime As Date = Today
'Dim NewTime As Date = Now
'Dim DifferenceInSeconds As Long = DateDiff(DateInterval.Second, OldTime, NewTime)
'Dim SpanFromSeconds As TimeSpan = New TimeSpan(0, 0, DifferenceInSeconds)

'Dim StartTime As Date = Now   ' Starting date/time.
' Run the process that is to be timed.
'Dim RunLength As System.TimeSpan = Now.Subtract(StartTime)
'Dim Millisecs As Integer = RunLength.Milliseconds



      'initialize memoization array
      for j = 0 to 99
         mem(j) = -1
      next j

      System.Console.Write("Enter the index of the Fibonacci number you want: ")
      j = System.Console.Readline()

      startTime = Now
      k = fib_i(j)
      diffTime = Now.Subtract(startTime)
      System.Console.Writeline("Fib(" & j & ") = " & k & " (iterative solution took " & diffTime.seconds & " seconds)")

      startTime = Now
      l = fib_r(j)
      diffTime = Now.Subtract(startTime)
      System.Console.Writeline("Fib(" & j & ") = " & l & " (recursive solution took " & diffTime.seconds & " seconds)")

      startTime = Now
      m = fib_rmemo(j)
      diffTime = Now.Subtract(startTime)
      System.Console.Writeline("Fib(" & j & ") = " & m & " (memoized recursive solution took " & diffTime.seconds & " seconds)")

   End Sub
End Module

'run the following command to compile
'vbc fibonacci.vb