Computing Fibonacci numbers the hard wayI 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. |