On 12/12/07, Bill Wood <[EMAIL PROTECTED]> wrote:
> On Wed, 2007-12-12 at 11:19 +0000, Andrew Coppin wrote:
> . . .
> > ...and normal programmers care about the Fibonacci numbers because...?
> >
> > Seriously, there are many, many programmers who don't even know what
> > Fibonacci numbers *are*. And even I can't think of a useful purpose for
> > them. (Unless you count Fibonacci codes?)
>
> Knuth[1] pp. 417-419 discusses Fibonacci trees and Fibonacci search.
> According to Knuth (and who am I to argue with him) Fibonacci search has
> better average case running time than binary search, although worst case
> can be slightly slower.
>
> Cormen et. al.[2] devotes chapter 20 to Fibonacci heaps, which they say
> are of primarily theoretical interest.
Since someone else mentioned these, I feel justified in saying:
fibonacci heaps *are* practical, under certain usage conditions. They
are, however, hard to get right. =]
More importantly for this discussion, however: Fibonacci heaps have
nothing to do with calculating the fibonacci numbers, and you don't
even need to know what the fibonacci sequence is to use fibonacci
heaps. (You discover what it is, if you didn't know, when you do a
complexity analysis of fibonacci heaps, but, that's only useful for
proving how efficient the heaps can be.) Therefore, I don't think one
can successfully argue that fibonacci numbers are important because a
heap has "Fibonacci" the name in its name.
Just a nit, but I thought it worth mentioning. =]
--
Denis
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
