Re: calculating fibonacci[was: encryption]

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.

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


- Gerry Quinn
.

Relevant Pages

  • Re: calculating fibonacci[was: encryption]
    ... Haskell uses "curried functions", so what a mathematician would write ... The tail function returns a list that has the first element removed. ... Finally zip takes two lists and returns that list of pairs made up ... Putting it all together, we know that fib starts 1, 1, ... ...
    (comp.programming)
  • Re: calculating fibonacci[was: encryption]
    ... unbounded lists like fib present no ... problem at all and the cost of calculating a particular element is ... Haskell: take 1000 fib) the cost of getting the 1001st will involve ...
    (comp.programming)
  • Re: calculating fibonacci[was: encryption]
    ... Haskell uses "curried functions", so what a mathematician would write ... Finally zip takes two lists and returns that list of pairs made up ... Putting it all together, we know that fib starts 1, 1, ... ... zip fib (tail fib) ...
    (comp.programming)
  • Re: calculating fibonacci[was: encryption]
    ... unbounded lists like fib present no ... Haskell: take 1000 fib) the cost of getting the 1001st will involve ... It is elegant and fast. ...
    (comp.programming)
  • Re: calculating fibonacci[was: encryption]
    ... unbounded lists like fib present no ... problem at all and the cost of calculating a particular element is ... Haskell: take 1000 fib) the cost of getting the 1001st will involve ...
    (comp.programming)