Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C Programming > FIbonacci

Reply
Thread Tools

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.
 
Reply With Quote
 
 
 
 
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
> 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.

 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Fibonacci numbers dleecurt@cc.usu.edu C++ 28 06-05-2011 04:30 AM
Fibonacci problem Brett Trost Perl 2 01-22-2004 02:04 PM
STL for Fibonacci Heap?? Lance C++ 5 12-02-2003 09:17 AM
Computing Fibonacci numbers as a performance testsuite Alex Vinokur C++ 0 10-29-2003 12:07 PM
How to do fibonacci by linked list ( not by recursive) fighterman19 C++ 11 09-08-2003 02:30 PM



Advertisments