Re: calculating fibonacci[was: encryption]



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 re-use them. The 'auto-memorisation' quirk of Haskell is a
double-edged 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.
.