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>1The 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 fibonacciUnfortunately 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 adderIn 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. |