# 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 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.

.

**Follow-Ups**:**Re: calculating fibonacci[was: encryption]***From:*Gerry Quinn

**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

- 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):