Computing Fibonacci numbers the hard way
Richard Harter
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.
Richard Harter, c...@tiac.net
http://home.tiac.net/~cri, http://www.varinoma.com
If I do not see as far as others, it is because
I stand in the footprints of giants.
Paul N
> I suppose we are all familiar with recursive definitions of
> Fibonacci numbers, e.g.
<snip>
> 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.
<big snip>
I'm not entirely sure whether you're asking a question here or making
a point, let alone exactly what the question/point might be, so you
may not get many replies.
But there was one point which I wasn't sure you were mentioning. There
is an exact formula for Fibonacci numbers:
F(k) = (r ^ k - t ^ k) / (r - t)
where r = (1 + SQR(5)) / 2 and t = 1 - r.
Since the Fibonacci numbers are all integers, as long as any errors
are less than one they can be ignored.
Hope that helps.
Paul.
Richard Harter
wrote:
>On 24 June, 02:54, c...@tiac.net (Richard Harter) wrote:
>> I suppose we are all familiar with recursive definitions of
>> Fibonacci numbers, e.g.
>
><snip>
>
>> Fibonacci numbers grow exponentially as phi^n. =A0If we want exact
>> results that fit in 32 or 64 bit integers then a lookup table
>> suffices. =A0If we want exact results for larger n, bignums and a
>> more efficient algorithm is indicated. =A0If the result does not
>> have to be exact the asymptotic formula is indicated.
>
><big snip>
>
>I'm not entirely sure whether you're asking a question here or making
>a point, let alone exactly what the question/point might be, so you
>may not get many replies.
>
>But there was one point which I wasn't sure you were mentioning. There
>is an exact formula for Fibonacci numbers:
>
>F(k) =3D (r ^ k - t ^ k) / (r - t)
>
>where r =3D (1 + SQR(5)) / 2 and t =3D 1 - r.
>
>Since the Fibonacci numbers are all integers, as long as any errors
>are less than one they can be ignored.
There is indeed an exact formula; the catch is that it is more
expensive to use than the doubling formula if you want an exact
result. However it is just the thing if you want a limited
precision result.
The point, if there be such, is that an elegant but apparently
useless formulation has a real use.
cr88192
"Richard Harter" <c...@tiac.net> wrote in message
news:4a42e45b...@text.giganews.com...
yep...
it works good as a "first test" for a compiler or interpreter...
if a recursive fibonacci test works (and nothing breaks or blows up), this
is a good start, and off to more involved tests.
and if it breaks, then something is so fundamentally wrong with the compiler
or interpreter that there is no real point in going forwards until at least
this much works...
Aaron Gray
Aaron