FIbonacci

Discussion in 'C Programming' started by MARQUITOS51, Dec 11, 2005.

  1. MARQUITOS51

    MARQUITOS51 Guest

    Hey guys this is the fibonacci series. But Im having this huge problem.
    First of all I want to do the simplest code possible so then I can use
    user defined functions and arrays. But this one didnt came out well.
    Any suggestions!


    #include<stdio.h>
    #include<math.h>

    int main ()

    {
    int fib, n;

    for(n=0; n<=10; n++)
    {

    fib=(n-1)+(n-2);
    printf("%d \n", fib);

    }

    return 0;
    }
     
    MARQUITOS51, Dec 11, 2005
    #1
    1. Advertising

  2. Am Sun, 11 Dec 2005 07:06:00 -0800 schrieb MARQUITOS51:

    > Hey guys this is the fibonacci series. But Im having this huge problem.
    > First of all I want to do the simplest code possible so then I can use
    > user defined functions and arrays. But this one didnt came out well.
    > Any suggestions!
    >
    >
    > #include<stdio.h>
    > #include<math.h>
    >
    > int main ()
    >
    > {
    > int fib, n;
    >
    > for(n=0; n<=10; n++)
    > {
    >
    > fib=(n-1)+(n-2);
    > printf("%d \n", fib);
    >
    > }
    >
    > return 0;
    > }


    As far as I remember, this isn't the fibonacci algorithm.
    First it starts with 1 and 1, the third element of fibonacci series is the
    addition of the first and second. So fib(n)=fib(n-1)+fib(n-2).
    Not saving all elements you are able to only save the last elements in
    variables and shift them. But what you did on the indexing element doesn't
    make any sense.

    Bye,
    Stefan
     
    Stefan Wallentowitz, Dec 11, 2005
    #2
    1. Advertising

  3. MARQUITOS51

    MARQUITOS51 Guest

    Hey I did this a few moments ago and it workes. Can you check it and
    suggest how to optimize. Im also looking how to convert it to user
    defined function.

    #include<stdio.h>
    #include<math.h>

    int main ()

    { int f[50];
    int n=2;

    f[0]=0;
    f[1]=1;

    do
    {
    f[n]=f[n-1]+f[n-2];
    n++;
    }
    while(n<=49);

    for(n=0; n<=49; n++)
    {printf("%d \n", f[n]);}


    return 0;


    }
     
    MARQUITOS51, Dec 11, 2005
    #3
  4. MARQUITOS51 <> wrote:

    > Hey I did this a few moments ago and it workes. Can you check it and
    > suggest how to optimize. Im also looking how to convert it to user
    > defined function.


    Sure, it works, if you don't ever plan on wanting more than 50
    Fibonacci numbers. malloc() and friends can help you store an
    arbitrary number of Fibonacci numbers. If you're just trying to print
    them, you don't need more than three distinct variables. Think about
    it.

    > #include<stdio.h>
    > #include<math.h>


    Why are you including this header? You're not using anything from it.

    > int main ()

    int main( void ) /* better */

    --
    Christopher Benson-Manica | I *should* know what I'm talking about - if I
    ataru(at)cyberspace.org | don't, I need to know. Flames welcome.
     
    Christopher Benson-Manica, Dec 11, 2005
    #4
  5. MARQUITOS51 wrote:
    > Hey guys this is the fibonacci series. But Im having this huge problem.
    > First of all I want to do the simplest code possible so then I can use
    > user defined functions and arrays. But this one didnt came out well.
    > Any suggestions!
    >


    #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; }


    P.Krumins
     
    Peteris Krumins, Dec 11, 2005
    #5
  6. MARQUITOS51

    Alex Fraser Guest

    "Peteris Krumins" <> wrote in message
    news:...
    [snip]
    > #include <stdio.h>
    >
    > unsigned fib(unsigned n) {
    > return n <= 2 ? 1 : fib(n - 1) + fib(n - 2);


    Personally, I'd make that:

    return n < 2 ? n : fib(n - 2) + fib(n - 1);

    > }
    >
    > int main(void) { printf("fib(17) is: %d\n", fib(17)); return 0; }


    Alex
     
    Alex Fraser, Dec 11, 2005
    #6
  7. MARQUITOS51

    Eric Sosman Guest

    Peteris Krumins wrote:

    > MARQUITOS51 wrote:
    >
    >>Hey guys this is the fibonacci series. But Im having this huge problem.
    >>First of all I want to do the simplest code possible so then I can use
    >>user defined functions and arrays. But this one didnt came out well.
    >>Any suggestions!
    >>

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

    --
    Eric Sosman
    lid
     
    Eric Sosman, Dec 11, 2005
    #7
  8. 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.


    P.Krumins
     
    Peteris Krumins, Dec 11, 2005
    #8
  9. In article <>, Eric Sosman <> 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);
    }

    Even written this way, and compiled without optimization (I verified
    that the compiler left the tail-recursive call in rather than
    optimizing it to a branch), this computes fib(47) in negligible time.
    But of course it's just the forward-iterative version written as tail
    recursion.

    It'd be possible to rewrite Peteris' backward-recursing algorithm
    using continuation-passing style and tail recursion, but since C
    lacks dynamic closures we'd have to emulate them. And that would
    just involve recursively creating some sort of list of instructions
    to run the forward-iterative algorithm, so it's not very interesting.

    --
    Michael Wojcik

    Is it any wonder the world's gone insane, with information come to be
    the only real medium of exchange? -- Thomas Pynchon
     
    Michael Wojcik, Dec 13, 2005
    #9
  10. MARQUITOS51

    Guest

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


    Exercise to the reader: Describe a function to precisely count the
    number of "+" operations performed by this function for computing f(n).
    (Hint: its easier than you think.)

    --
    Paul Hsieh
    http://www.pobox.com/~qed/
    http://bstring.sf.net/
     
    , Dec 14, 2005
    #10
  11. MARQUITOS51

    Jordan Abel Guest

    On 2005-12-11, Peteris Krumins <> 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.
     
    Jordan Abel, Dec 14, 2005
    #11
  12. MARQUITOS51

    Tim Rentsch Guest

    (Michael Wojcik) writes:

    > In article <>, Eric Sosman <> 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.
     
    Tim Rentsch, Dec 14, 2005
    #12
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Brett Trost

    Fibonacci problem

    Brett Trost, Jan 22, 2004, in forum: Perl
    Replies:
    2
    Views:
    1,024
  2. fighterman19
    Replies:
    11
    Views:
    855
    Karl Heinz Buchegger
    Sep 8, 2003
  3. Fibonacci numbers

    , Oct 10, 2003, in forum: C++
    Replies:
    28
    Views:
    1,387
    yousafzai
    Jun 5, 2011
  4. Alex Vinokur
    Replies:
    0
    Views:
    470
    Alex Vinokur
    Oct 29, 2003
  5. Lance

    STL for Fibonacci Heap??

    Lance, Dec 1, 2003, in forum: C++
    Replies:
    5
    Views:
    1,356
    Dietmar Kuehl
    Dec 2, 2003
Loading...

Share This Page