Fibonacci Numbers

[xenou]

Hi,

This is a short program to output a fibonacci sequence. Can anyone think of another way to create this algorithm? The problem is one of the questions at the end of a chapter in a book about programming. Assume you have only the most basic flow control knowledge and can only use primitive types (technically I'm not even supposed to know how to declare an array yet, either).

[COLOR="Navy"]Sub[/COLOR] FibNums()
[COLOR="Navy"]Dim[/COLOR] arr(2) [COLOR="Navy"]As[/COLOR] [COLOR="Navy"]Long[/COLOR]
[COLOR="Navy"]Dim[/COLOR] nextNum [COLOR="Navy"]As[/COLOR] [COLOR="Navy"]Long[/COLOR]
[COLOR="Navy"]Dim[/COLOR] x [COLOR="Navy"]As[/COLOR] [COLOR="Navy"]Long[/COLOR]
[COLOR="Navy"]Dim[/COLOR] rsp [COLOR="Navy"]As[/COLOR] [COLOR="Navy"]Long[/COLOR]
[COLOR="Navy"]Dim[/COLOR] msg [COLOR="Navy"]As[/COLOR] [COLOR="Navy"]String[/COLOR]

    [COLOR="SeaGreen"]'//Seed First Two Fibonacci numbers[/COLOR]
    arr(0) = 0
    arr(1) = 1

    [COLOR="SeaGreen"]'//User inputs how many Fibonacci numbers to list[/COLOR]
    rsp = CLng(Application.InputBox("How many Fibonacci numbers do you want [enter a number zero or greater]:"))
    [COLOR="Navy"]If[/COLOR] CLng(rsp) > 0 [COLOR="Navy"]Then[/COLOR]
        msg = "1"
        [COLOR="Navy"]For[/COLOR] x = 2 [COLOR="Navy"]To[/COLOR] CLng(rsp)
            nextNum = arr(0) + arr(1)
            msg = msg & " " & nextNum
            arr(0) = arr(1)
            arr(1) = nextNum
        [COLOR="Navy"]Next[/COLOR] x
        MsgBox msg
    [COLOR="Navy"]End[/COLOR] [COLOR="Navy"]If[/COLOR]
[COLOR="Navy"]End[/COLOR] [COLOR="Navy"]Sub[/COLOR]

 

[shg]

As a UDF, ...

Function Fibonacci(n As Long) As Double
    Const sqr5      As Double = 5 ^ 0.5
    Const phi       As Double = (1 + sqr5) / 2

    If n > 0 Then Fibonacci = Round((phi ^ n - 1 / (-phi) ^ n) / sqr5, 0)
End Function

 

[xenou]

It's going to take me a few days to digest that ... ! Nice one.

 

[shg]

Abraham de Moivre in the 18th century, sans Excel, computers, calculators, and even decent notation. The rounding is a nod to finite precision; the mathematical result needs none.

technically I'm not even supposed to know how to declare an array

You could just use arr0 and arr1.

 

[xenou]

Here is an alternate algorithm I found, without using the extra temp variables (I am allowing myself an array, though, still).

[COLOR="Navy"]Sub[/COLOR] FibNums2()
[COLOR="Navy"]Dim[/COLOR] a(2) [COLOR="Navy"]As[/COLOR] [COLOR="Navy"]Long[/COLOR]
[COLOR="Navy"]Dim[/COLOR] n [COLOR="Navy"]As[/COLOR] [COLOR="Navy"]Long[/COLOR]
[COLOR="Navy"]Dim[/COLOR] rsp [COLOR="Navy"]As[/COLOR] [COLOR="Navy"]Long[/COLOR]
[COLOR="Navy"]Dim[/COLOR] msg [COLOR="Navy"]As[/COLOR] [COLOR="Navy"]String[/COLOR]

    [COLOR="SeaGreen"]'//Seed First Number in the Series[/COLOR]
    a(0) = 0
    a(1) = 0
    a(2) = 1

    [COLOR="SeaGreen"]'//User inputs how many Fibonacci numbers to list[/COLOR]
    rsp = CLng(Application.InputBox("How many Fibonacci numbers do you want [enter a number zero or greater]:"))
    [COLOR="Navy"]If[/COLOR] rsp > 0 [COLOR="Navy"]Then[/COLOR]
        [COLOR="Navy"]For[/COLOR] n = 1 [COLOR="Navy"]To[/COLOR] CLng(rsp)
            a(n [COLOR="Navy"]Mod[/COLOR] 3) = a((n + 1) [COLOR="Navy"]Mod[/COLOR] 3) + a((n + 2) [COLOR="Navy"]Mod[/COLOR] 3)
            msg = msg & " " & a(n [COLOR="Navy"]Mod[/COLOR] 3)
        [COLOR="Navy"]Next[/COLOR] n
        MsgBox msg
    [COLOR="Navy"]End[/COLOR] [COLOR="Navy"]If[/COLOR]

[COLOR="Navy"]End[/COLOR] [COLOR="Navy"]Sub[/COLOR]

And here's the version with a fibonacci function:

[COLOR="Navy"]Sub[/COLOR] FibNums3()
[COLOR="Navy"]Const[/COLOR] SQRT5 [COLOR="Navy"]As[/COLOR] [COLOR="Navy"]Double[/COLOR] = 5 ^ 0.5
[COLOR="Navy"]Const[/COLOR] PHI [COLOR="Navy"]As[/COLOR] [COLOR="Navy"]Double[/COLOR] = (1 + SQRT5) / 2
[COLOR="Navy"]Dim[/COLOR] rsp [COLOR="Navy"]As[/COLOR] [COLOR="Navy"]String[/COLOR]
[COLOR="Navy"]Dim[/COLOR] msg [COLOR="Navy"]As[/COLOR] [COLOR="Navy"]String[/COLOR]
[COLOR="Navy"]Dim[/COLOR] n [COLOR="Navy"]As[/COLOR] [COLOR="Navy"]Long[/COLOR]

    [COLOR="SeaGreen"]'//User inputs how many Fibonacci numbers to list[/COLOR]
    rsp = CLng(Application.InputBox("How many Fibonacci numbers do you want [enter a number zero or greater]:"))
    [COLOR="Navy"]If[/COLOR] CLng(rsp) > 0 [COLOR="Navy"]Then[/COLOR]
        [COLOR="Navy"]For[/COLOR] n = 1 [COLOR="Navy"]To[/COLOR] CLng(rsp)
            msg = msg & " " & Round((PHI ^ n - 1 / (-PHI) ^ n) / SQRT5, 0)
        [COLOR="Navy"]Next[/COLOR] n
        MsgBox msg
    [COLOR="Navy"]End[/COLOR] [COLOR="Navy"]If[/COLOR]
    
[COLOR="Navy"]End[/COLOR] [COLOR="Navy"]Sub[/COLOR]

 

[ZVI]

Hi Xenou,

Merry Christmas!

It is interesting task from aspect of accuracy.

The series of FibNums is limited by 46 numbers because of the Long type.

After declaring of arr(2) and nextNum As Double the limit of FibNums is 73 correct numbers because of the 15 significant digits limit and math accuracy.
The same is for FibNums2.

Limit of FibNums3 is 70 correct numbers.

The below version is similar to FibNums but provides correct 139 numbers, for regret MsgBox can show only 93 of them.
No array is used (just variables).
The type of all variables is Variant.

Sub Fib4()
  Static n
  Dim i, f, f0, f1, f2
  n = Val(Application.InputBox("How many Fibonacci numbers do you want [from 1 up to 93]:", , n))
  If n > 0 Then
    f = "1"
    f0 = 0
    f1 = 1
    For i = 2 To n
      f2 = CDec(f1 + f0)
      f0 = CDec(f1)
      f1 = CDec(f2)
      f = f & " " & f2
    Next
    MsgBox f
  End If
End Sub

Regards,

Vlad

 

[bradhog]

I too have been using ZVI technique but now I also know a new one. Thank you.

 

[xenou]

Thanks Zvi!

Do I hear a Fib5? Going once, going twice ...

 

[shg]

Considering that all that's needed is addition, someone should post a version that returns numeric strings ...

 

[ZVI]

Fib5 puts the required (Big) Fibonacci number to the active cell,
Fib6 populates A-column by series of (Big) Fibonacci numbers.

Sub Fib5()
  ' Put the required Fibonacci number to the active cell
  Static n
  Dim i, f, f0, f1, f2
  ' Ask for the # in series
  n = Val(Application.InputBox("What # of Fibonacci number do you want in active cell?", , n))
  ' Main
  If n > 0 Then
    f = "1"
    f0 = "0"
    f1 = "1"
    For i = 2 To n
      f2 = FibAdd(f1, f0)
      f0 = f1
      f1 = f2
    Next
  End If
  ActiveCell = "'" & f2
End Sub
 
Sub Fib6()
  ' Put the series of Fibonacci numbers to the cells of A-column
  Static n
  Dim i, f, f0, f1, f2
  ' Clear A-column
  Intersect(Columns("A"), ActiveSheet.UsedRange).ClearContents
  ' Ask for the length of series
  n = Val(Application.InputBox("How many Fibonacci numbers do you want in A-column?", , n))
  ' Main
  If n > 0 Then
    f = "1"
    f0 = "0"
    f1 = "1"
    Cells(1, "A") = "'" & f
    For i = 2 To n
      f2 = FibAdd(f1, f0)
      Cells(i, "A") = "'" & f2
      f0 = f1
      f1 = f2
    Next
  End If
End Sub
 
Function FibAdd(ByVal a1, ByVal a2) As String
' ZVI:2014-01-01 http://www.mrexcel.com/forum/general-excel-discussion-other-questions/746480-fibonacci-numbers.html
' Returns the text sum of two big (string) integers: FibAdd = CStr(a1 + a2)
  Const SPACE As Byte = 32, ZERO As Byte = 48, NINE As Byte = 57
  Dim b1() As Byte, b2() As Byte
  Dim i As Long, j As Long
  a1 = Trim(a1)
  a2 = Trim(a2)
  If Len(a1) > Len(a2) Then
    b1() = "0" & a1
    b2() = a2
  Else
    b1() = "0" & a2
    b2() = a1
  End If
  i = UBound(b1) - 1
  j = UBound(b2) - 1
  Do
    b1(i) = b1(i) + b2(j) - ZERO
    If b1(i) > NINE Then
      b1(i) = b1(i) - 10
      b1(i - 2) = b1(i - 2) + 1
    End If
    i = i - 2
    j = j - 2
  Loop While j >= 0
  If b1(0) = ZERO Then b1(0) = SPACE
  FibAdd = Trim(b1)
End Function