Richard Harter’s World
Site map
July 2009
Comp. Sci.
email

Computing Fibonacci numbers the hard way

I suppose we are all familiar with recursive definitions of Fibonacci numbers, e.g.

    F(0) = 0
    F(1) = 1
    F(n) = F(n-1) + F(n-2) for n>1
The recursive definition is used in programming exposition as an elegant example and as a grim warning. Thus (1):
    function fibonacci(n)
        if (n <= 0) return 0
        else if (n == 1) return 1
        return fibonacci(n-1)+fibonacci(n-2)
        end fibonacci
Unfortunately this code blows up; that is, the number of calls grows exponentially. The iterative version uses one call and n cycles through a simple loop. Thus (2):
    function fibonacci(n)
        if (n <= 0) return 0
        else if (n == 1) return 1
        a = 0; b = 1
        do i = 2,n
            c = a + b
            a = b
            b = c
            end do
        return b
        end fibonacci
(1) is ‘nicer’ than (2) – it is shorter and has no local variables. Many of the little morals often drawn from this comparison are off the mark; neither form is desirable if we actually want results.

Fibonacci numbers grow exponentially as phi^n. If we want exact results that fit in 32 or 64 bit integers then a lookup table suffices. If we want exact results for larger n, bignums and a more efficient algorithm is indicated. If the result does not have to be exact the asymptotic formula is indicated.

Although the simple recursion is not useful as an implementation it is useful for an entirely different reason – as a simple stress test for other software, e.g., compilers and run time systems.

One place it is particularly useful is in analyzing data flow languages and their implementations. For those not familiar with the data flow paradigm, data flow programs are composed of units variously called light processes, agents, actors, and even modules. In imperative programming functions return data and control to their caller. In dataflow programming agents pass data to their successors. Agents become active when they receive data and become quiescent when their input is exhausted. Here is a data flow version of the recursive fibonacci algorithm.

    process main
       read n
       spawn fibonacci
       self=>fibonacci=>self
       send n
       receive result
       print result
       end main
    process fibonacci
       receive n
       if (n < 2) send n
       else
          spawn adder, out=self.out
          spawn child1 = fibonacci
          spawn child2 = fibonacci
          child1 => adder
          child2 => adder
          send (child1) n-1
          send (child2) n-2
          end else
       die
       end fibonacci
    process adder
       receive first
       receive second
       send first+second
       die
       end adder
In this code a fibonacci process becomes active when it receives an input n. If it cannot determine F(n) directly it spawns two copies of itself and one copy of the adder process. It send n-1 to one child and n-2 to the other. The child processes send their results to the adder which in turn sends the sum to the return address for the original fibonacci process.

Each process kills itself when it is done. This is necessary because unlike function invocations processes do not die when they transmit results. Note that except for the main process and the root fibonacci process no process returns data to the process that “called” it.

This is an excessively inefficient way to compute fibonacci numbers; however it is a very effective way to stress a data flow engine. The number of processes generated grows exponentially. Likewise the number of data flow channels grows exponentially. In turn they die equally fast as the computation nears completion.


This page was last updated July 1, 2009.

Richard Harter’s World
Site map
July 2009
Comp. Sci.
email