The Fibonacci sequence

  • Difficulty: 006/100
  • Author: jeremy theler
  • Keywords: VECTOR, SIZE, PRINT_VECTOR, FORMAT, IF, ELSE, ENDIF, :=, static_steps, vecsize, sqrt,

A thorough discussion of the beauty and applications of the Fibonacci sequence is of course out of both this Real Book and its author league. For sure the reader is already familiar with this set of natural numbers. The three examples that follow show how to use wasora to compute the Fibonacci numbers, first by constructing a vector of a certain size and setting each element to be equal to the sum of the two previous elements, then iteratively computing

\[ f_{n} = f_{n-1} + f_{n-2} \]

and then by using the dazzling closed-form formula

\[ f_{n} = \frac{\phi^n + (1-\phi)^n}{\sqrt{5}} \]

where \(\phi= (1+\sqrt{5})/2\) is the golden ratio. As cumbersome as it may seem, this formula is easily obtained by solving the explicit difference equation, for example with the aid of the \(Z\)-transform:

\[ f_{n} = z f_{n} + z^2 f_{n} \]

\[ z^2 + z - 1 = 0 \]

\[ z = \frac{1 \pm \sqrt{5}}{2} \]

The general solution is therefore

\[ f_n = k_1 \left( \frac{1+\sqrt{5}}{2} \right)^n + k_2 \left(\frac{1-\sqrt{5}}{2} \right)^n \]

where \(k_1\) and \(k_2\) should be determined as to fulfill the initial conditions \(f_1 = 1\) and \(f_2=1\). The solution is

\[ \begin{align*} k_1 &= +\frac{1}{\sqrt{5}}\\ k_2&= -\frac{1}{\sqrt{5}} \end{align*} \]

and the closed-form formula follows.

fibo_vector.was

The first \(N\) elements of the Fibonacci sequence can be computed within a vector \(f\) of a size \(N\) as the following simple wasora input shows. The first two elements \(f_i\) for \(i=1\) and \(i=2\) are set to one and then the next \(N-2\) elements are computed as \(f_i = f_{i-1} + f_{i-2}\).

# the fibonacci sequence as a vector
VECTOR f SIZE 25

f(i)<1:2> = 1
f(i)<3:vecsize(f)> = f(i-2) + f(i-1)

PRINT_VECTOR f FORMAT %g
$ wasora fibo_vector.was
1
1
2
3
5
8
13
21
34
55
89
144
233
377
610
987
1597
2584
4181
6765
10946
17711
28657
46368
75025
$ 

fibo_iterative.was

As in its original form the Fibonacci sequence is presented as a recurrence relation, it seems an appropriate example be used to introduce wasora’s iterative computation capabilities. Three variables \(f_n\), \(f_{n-1}\) and \(f_{n-2}\) are use to compute the recurrence. For the special case for \(n=1\) and \(n=2\) they are initialized to one. Then, each step consists of computing the new value for \(f_n\) and shifting \(f_{n-1}\) to \(f_{n-2}\) first and \(f_n\) to \(f_{n-1}\) afterward. The first twenty five numbers are printed to the screen. As the computations are performed using double-precision floating point arithmetic, the maximum element that can be computed with this example is \(n = 1476\), case that the user is encouraged to try. For \(n = 1477\) a not-a-number error is issued.

# the fibonacci sequence as an iterative problem

#static_iterations = 1476
static_steps = 25

IF step_static=1|step_static=2
 f_n = 1
 f_nminus1 = 1
 f_nminus2 = 1
ELSE
 f_n = f_nminus1 + f_nminus2
 f_nminus2 = f_nminus1
 f_nminus1 = f_n
ENDIF

PRINT %g step_static f_n 
$ wasora fibo_iterative.was
1   1
2   1
3   2
4   3
5   5
6   8
7   13
8   21
9   34
10  55
11  89
12  144
13  233
14  377
15  610
16  987
17  1597
18  2584
19  4181
20  6765
21  10946
22  17711
23  28657
24  46368
25  75025
$ 

fibo_formula.was

The following input solves the very same problem but instead of iterative solving the recurrence relation, it uses the closed-form formula derived above. A function \(f(n)\) is defined and then printed for \(n=1,\dots,25\). Note that the floating point precision is enough to obtain integral values for every \(n\).

# the fibonacci sequence using the closed-form formula as a function
phi = (1+sqrt(5))/2 
f(n) := (phi^n - (1-phi)^n)/sqrt(5)
PRINT_FUNCTION f MIN 1 MAX 25 STEP 1 FORMAT %g
$ wasora fibo_formula.was
1   1
2   1
3   2
4   3
5   5
6   8
7   13
8   21
9   34
10  55
11  89
12  144
13  233
14  377
15  610
16  987
17  1597
18  2584
19  4181
20  6765
21  10946
22  17711
23  28657
24  46368
25  75025
$