Re: FIbonacci

mwojcik@xxxxxxxxxxx (Michael Wojcik) writes:

> In article <z7adnct6kL7RAwHeRVn-ig@xxxxxxxxxxx>, Eric Sosman <esosman@xxxxxxxxxxxxxxxxxxx> writes:
> > Peteris Krumins wrote:
> > >
> > > #include <stdio.h>
> > >
> > > unsigned fib(unsigned n) {
> > > return n <= 2 ? 1 : fib(n - 1) + fib(n - 2);
> > > }
> > >
> > > int main(void) { printf("fib(17) is: %d\n", fib(17)); return 0; }
> >
> > Somebody always proposes this solution, but it's a
> > poor one. Try it with fib(47), say, and tell us how
> > long it takes. Hint: You won't need a high-precision
> > timer.
>
> Well, there's always this one (with error checking left as an
> exercise for the reader):
>
> /***
> prev2 and prev are the two immediately preceeding values in the
> series; prev2 is F(n-2) and prev is F(n).
> pos is the current position in the series.
> want is the position we're looking for.
> ***/
>
> unsigned fib_cps(unsigned prev2, unsigned prev, unsigned pos, unsigned want)
> {
> if (want <= 2) return 1;
> if (pos == want) return prev2 + prev;
> return fib_r(prev, prev2 + prev, pos + 1, want);
> }
>
> unsigned fib(n)
> {
> return fib_cps(1, 1, 3, n);
> }

(Of course you meant fib_cps rather than fib_r in the first function.)

Just for my own enjoyment:

unsigned
fib3( unsigned n, unsigned a, unsigned b ){
return n == 0 ? b : fib3( n-1, b, a+b );
}

unsigned
fib( unsigned n ){
return fib3( n, 1, 0 );
}

This definition yields fib(0) == 0, as the Fibonacci numbers are
usually defined.

.

Relevant Pages