Re: calculating fibonacci[was: encryption]

In article <87myew99mc.fsf@xxxxxxxxx>, ben.usenet@xxxxxxxxx says...
Gerry Quinn <gerryq@xxxxxxxxx> writes:

In article <874p159x2z.fsf@xxxxxxxxx>, ben.usenet@xxxxxxxxx says...
Gerry Quinn <gerryq@xxxxxxxxx> writes:
process Fib ( int n )
small = 1
large = 1
for i = 3 to n
calc = small + large
small = large
large = calc
return large
end process
... I suppose you could do what
my program does and keep the current list pared down to the two most
recent numbers, anyway.

Yes. Richard Harter has posted the functional equivalent of
iterating while holding two previous values.

The Basic function serves equally well as a definition. Knowing how to
calculate the n-th number in a series is a definition of the series.

It serves as a definition, yes, but it may not be as useful for
building the series if that is what you really want. If you call it
repeatedly to make the series you get (roughly) a quadratic
algorithm. If you want a linear function that makes a list (or array
if that is what Basic has) you need to re-write it rather call the

You call it once to get the n-th Fibonacci number, making it adequate as
a mathematical definition of the series. If you want to store
intermediate data for optimisation purposes, you modify it.

That applies to any language. The Haskell funcion could presumably
likewise be optimised for memory storage or whatever algorithmic
optimisations are required. From a purely mathematical point of view,
there's no difference.

- Gerry wquinn