Velocity Reviews > FIbonacci

# FIbonacci

Jordan Abel
Guest
Posts: n/a

 12-14-2005
On 2005-12-11, Peteris Krumins <(E-Mail Removed)> wrote:
> Eric Sosman wrote:
>> Peteris Krumins wrote:
>>
>>
>> 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.
>>

>
> Yes, the solution has exponential complexity.

But only needs the last two results [or even the last one even and the
last one odd n] cached to reduce it to the same as the iterative
version.

Tim Rentsch
Guest
Posts: n/a

 12-14-2005
http://www.velocityreviews.com/forums/(E-Mail Removed) (Michael Wojcik) writes:

> In article <(E-Mail Removed)>, Eric Sosman <(E-Mail Removed)> 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
>
> /***
> 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.