Re: calculating fibonacci[was: encryption]
 From: Ben Bacarisse <ben.usenet@xxxxxxxxx>
 Date: Mon, 15 Dec 2008 17:17:56 +0000
Gerry Quinn <gerryq@xxxxxxxxx> writes:
In article <87iqpmj1l4.fsf@xxxxxxxxx>, ben.usenet@xxxxxxxxx says...
Haskell uses what is called lazy evaluation, so nothing is calculated
until it is needed. As a result, unbounded lists like fib present no
problem at all and the cost of calculating a particular element is
linear. The neat thing about doing it this way, is that the results
are automatically "memoised". If you calculate fib !! 1000, (!! is
the list index operator) asking for fib !! 100 just involves the cost
of looking in the list. If you ask for the first 1000 numbers (in
Haskell: take 1000 fib) the cost of getting the 1001st will involve
just one "click" of the definition of fib. It is elegant and fast.
In Basic a Fibonnaci function would be something like:
process Fib ( int n )
small = 1
large = 1
for i = 3 to n
calc = small + large
small = large
large = calc
next
return large
end process
And similarly for any procedural language. Because of the nature of the
function, using iteration seems far more elegant and clear than a
recursive solution.
It is obviously a matter of taste.
Obviously you could store results so far in an array if you wanted to be
able to reuse them. The 'automemorisation' quirk of Haskell is a
doubleedged sword...
Just to be clear, it is not a quirk of Haskell, it is a consequence of
(globally) defining a list of fibs. As I posted elsewhere, you don't
need to store them (though I have no evidence that the Haskell
compiler does in fact optimise the list away).
BTW, I translated my example from another language and I should have
simplified it my using the standard Haskell function that can zip a
pair of lists with a combining function:
fibs = 1 : 1 : zipWith (+) fibs (tail fibs)
I posted because it is an example of defining "the Fibonacci numbers"
not specifically as a way of calculating the fib(n) function. If you
actually want the sequence, it is handy to be able to define it.

Ben.
.
 FollowUps:
 Re: calculating fibonacci[was: encryption]
 From: Gerry Quinn
 Re: calculating fibonacci[was: encryption]
 References:
 encryption
 From: Bill Cunningham
 Re:calculating fibonacci[was: encryption]
 From: Bill Cunningham
 Re: Re:calculating fibonacci[was: encryption]
 From: Bill Cunningham
 Re: Re:calculating fibonacci[was: encryption]
 From: Richard Heathfield
 Re: Re:calculating fibonacci[was: encryption]
 From: Bill Cunningham
 Re: calculating fibonacci[was: encryption]
 From: Patricia Shanahan
 Re: calculating fibonacci[was: encryption]
 From: Ben Bacarisse
 Re: calculating fibonacci[was: encryption]
 From: Bartc
 Re: calculating fibonacci[was: encryption]
 From: Ben Bacarisse
 Re: calculating fibonacci[was: encryption]
 From: Gerry Quinn
 encryption
 Prev by Date: Re: Mergesort Vs Quicksort
 Next by Date: Re: Mergesort Vs Quicksort
 Previous by thread: Re: calculating fibonacci[was: encryption]
 Next by thread: Re: calculating fibonacci[was: encryption]
 Index(es):
Relevant Pages
