Notes on Evaluation of the Recursive Fibonacci Function

The purpose of this note is to examine and compare two implementations of an algorithm for computing the n th term of a Fibonacci sequence.

The Experiment

The Fibonacci sequence sequence is defined as the sequence:

0 1 1 2 3 5 8 13 21 34 55 ...

Suppose we had a function, named fibonacci, which, when given an input n, would compute the n th term in this sequence. Then,

fibonacci 0 ==> 0
fibonacci 1 ==> 1
fibonacci 2 ==> 1
...

As we search for the pattern which defines this function, we note that for n > 1,

fibonacci n ==> (fibonacci n - 1) + fibonacci n - 2

This leads to the following implementation of this algorithm for computing the n th term of the Fibonacci sequence.

fibonacci =. monad define 
if. y. < 2
  do. y.
  else. (fibonacci y. - 1) + fibonacci y. - 2
end.
)

Experiment Software

Use the vi editor to create a file named fib.js and enter and save the above fibonacci function.

Next start the J system by entering the unix commands:

%cd cs2322j
%j

Notice that the system prompts you for input with three spaces when you are running J while the unix prompt ends in the "%" character. To exit from J enter the Ctrl-D character.

Note that when we show a J expression in this laboratory experiment it will be preceeded by three spaces. Similarly, when we show a unix command it will be preceeded by the "%" character.

You may use vi editor from J as well as from unix. To do this enter the J expression

   vi 'filename'

The editing session should proceed as it does when using vi or nedit from the unix environment. When you are finished editing, quit the editor after first saving your file. You will find that you are back in J where you were before the editing session. To load any newly created J functions, expressions, etc., enter the J expression:

   load 'filename'

Now load the fibonacci function you just entered into J by entering the J sentence

   load 'fib.js'

Test the fibonacci function to verify its correct operation. Be sure not to use values of n larger than about 20.

Use the J verb time to time how long it takes to evaluate some of these fibonacci values.

Notice that as n gets larger it takes much longer than expected to compute the result. We need to examine exactly what is happening in this implementation of the Fibonacci algorithm.

Analysis of the Fibonacci Function

To compute the value of

fibonacci n

our function evaluates

(fibonacci n - 1) + fibonacci n - 2

We need to look at an example to better understand what is happening. Consider the task of evaluating fibonacci 5 . We abbreviate fibonacci 5 as (f 5) in the following diagram.

One problem with our function is that in computing (f 5),

f 4 is computed 1 time
f 3 is computed 2 times
f 2 is computed 3 times
f 1 is computed 5 times
f 0 is computed 3 times
...

The fib-work Function

It seems reasonable to attempt to quantify this behavior. Define an estimate of the work done in evaluating fibonacci n to be the number of times fibonacci j is evaluated for each possible j <= n. We will call this function fib-work n. We have

fib_work 0 ==> 1
fib_work 1 ==> 1
fib_work 2 ==> 3
fib_work 3 ==> 5
fib_work 4 ==> 9
fib_work 5 ==> 15
...

A little observation indicates that

fib_work n ==> 1 + (fib_work n - 1) + fib_work n - 2

which is a kind of Fibonacci series. However, we have the same kind of difficulty evaluating fib_work n as we have evaluating fibonacci n.

We need another approach to implement the algorithm for calculating the n th term of the Fibonacci sequence. In particular, we need to make sure that we do not unnecessarily re-evaluate a term in the sequence which has already been evaluted. Consider the following implementation of the n th term of the Fibonacci sequence.

fib_iter =: monad define 
('a' ; 'b' ; 'count') =. y.
if. count = 0
  do. b
  else. fib_iter (a + b) , a , count - 1
end.
)

fibonacci1 =: monad def 'fib_iter 1 0 , y.'

Use an editor to enter and verify these two functions and notice that they are able to calculate fibonacci1 n for large values of n. We call this implementation an iterative implementation because when fib_iter evaluates fib_iter, there is no pending execution to be done when each such evaluation completes. This is a tail recursive function since the continuation of each recursive use of fib_iter in fib_iter is the identity function. Also notice that if count = 0, the answer b has already been computed.

Estimating The execution Time of (fibonacci 100)

To complete this laboratory problem, use the iterative technique of fibonacci1 and fib_iter to provide an iterative implementation of fib_work. Call this function fib_work1. Next time how long it takes to evaluate fibonacci 20. Divide fib_work1 20 by the time it takes to evaluate fibonacci 20 to compute the average number of evaluations of fibonacci i per second your workstation can perform. You should, perhaps, repeat the computation of the average number of calls of fibonacci by using other n values which are a little larger than 20. However, remember that you will not be able to use n values much larger than about 25. Use this frequency to estimate how long it would take to evaluate fibonacci 100 on your workstation. What assumptions are being made in your estimate of how long it takes to evaluate fibonacci 100 ?

Write a brief report which contains listings of each of the programs as well as your estimate of how long it would take to evaluate fibonacci 100.