Fibonacci...

Discussion in 'C++' started by felixnielsen@hotmail.com, Feb 17, 2006.

  1. Guest

    Im actually kinda embarassed to ask this question...

    @code start
    #include <iostream>
    int main() {
    unsigned long long a = 1;
    unsigned long long b = 1;
    for (int i = 0; i < 45; i++) {
    a += b;
    std::cout << a/b << std::endl;
    b += a;
    std::cout << b/a << std::endl;
    }
    std::cin.get();
    }
    @code end

    Why cant i get it to work?

    Regards
    Zacariaz
    , Feb 17, 2006
    #1
    1. Advertising

  2. Guest

    Guess this would be more correct:

    @code start
    #include <iostream>
    int main() {
    unsigned long long a = 1;
    unsigned long long b = 1;
    std::cout << b/a << std::endl;
    for (int i = 0; i < 91; i++) {
    if (a > b) {
    b += a;
    std::cout << b/a << std::endl;
    }
    else if (b >= a) {
    a += b;
    std::cout << a/b << std::endl;
    }
    }
    std::cin.get();
    }
    @code end
    , Feb 17, 2006
    #2
    1. Advertising

  3. wrote:
    > Im actually kinda embarassed to ask this question...
    >
    > @code start
    > #include <iostream>
    > int main() {
    > unsigned long long a = 1;
    > unsigned long long b = 1;
    > for (int i = 0; i < 45; i++) {
    > a += b;
    > std::cout << a/b << std::endl;
    > b += a;
    > std::cout << b/a << std::endl;
    > }
    > std::cin.get();
    > }
    > @code end
    >
    > Why cant i get it to work?



    Do you really want to know the answer? I mean, don't you actually
    already know the answer?..

    What do you expect from your program? What seems to be the problem?

    V
    --
    Please remove capital As from my address when replying by mail
    Victor Bazarov, Feb 17, 2006
    #3
  4. wrote:
    > Guess this would be more correct:


    "More correct"? You mean, it actually does what you need? Or
    does it just _seem_ to be better?

    > @code start
    > #include <iostream>
    > int main() {
    > unsigned long long a = 1;
    > unsigned long long b = 1;
    > std::cout << b/a << std::endl;
    > for (int i = 0; i < 91; i++) {
    > if (a > b) {
    > b += a;
    > std::cout << b/a << std::endl;
    > }
    > else if (b >= a) {
    > a += b;
    > std::cout << a/b << std::endl;
    > }
    > }
    > std::cin.get();
    > }
    > @code end


    V
    --
    Please remove capital As from my address when replying by mail
    Victor Bazarov, Feb 17, 2006
    #4
  5. Guest

    I whant to end up with the number 1.618, or something like it, but i
    have trued averything it seemes, it will only print integers, i should
    know why, but either i've forgotten how this work (aint working alot
    with float/double) or im just stupid.

    If you remove the /a and /b from the code u'll see that it does indeed
    work, but those are not the numbers i want.
    , Feb 17, 2006
    #5
  6. Daniel T. Guest

    In article <>,
    wrote:

    > Im actually kinda embarassed to ask this question...
    >
    > @code start
    > #include <iostream>
    > int main() {
    > unsigned long long a = 1;
    > unsigned long long b = 1;
    > for (int i = 0; i < 45; i++) {
    > a += b;
    > std::cout << a/b << std::endl;
    > b += a;
    > std::cout << b/a << std::endl;
    > }
    > std::cin.get();
    > }
    > @code end
    >
    > Why cant i get it to work?


    What output were you expecting? If you wanted it to output the Fibonacci
    sequence, I'd say you can't get it to work because you are using the
    wrong algorithm. :)

    Here is a recursive algorithm:

    int fibonacci( int i ) {
    if ( i == 0 ) return 0;
    if ( i == 1 ) return 1;
    else return fibonacci( i - 1 ) + fibonacci( i - 2 );
    }

    And non-recursive:

    int fibonacci( int i ) {
    int result[] = { 0, 1 };
    while ( i > 1 ) {
    int t = result[0];
    result[0] = result[1];
    result[1] = result[0] + t;
    --i;
    }
    return result;
    }

    int main() {
    for ( int i = 0; i < 45; ++i )
    cout << i << ": " << fibonacci( i ) << '\n';
    }

    --
    Magic depends on tradition and belief. It does not welcome observation,
    nor does it profit by experiment. On the other hand, science is based
    on experience; it is open to correction by observation and experiment.
    Daniel T., Feb 17, 2006
    #6
  7. wrote:
    > I whant to end up with the number 1.618, or something like it, but i
    > have trued averything it seemes, it will only print integers, i should
    > know why, but either i've forgotten how this work (aint working alot
    > with float/double) or im just stupid.
    >
    > If you remove the /a and /b from the code u'll see that it does indeed
    > work, but those are not the numbers i want.


    When you divide a integer by an integer, you get an integer. What you
    want is to convert one of them to double before dividing, like
    double(a)/b

    V
    --
    Please remove capital As from my address when replying by mail
    Victor Bazarov, Feb 17, 2006
    #7
  8. Guest

    Hey im thank full for your input, but it work, dont say otherwise.
    I have tryed casting, but then i casted both numbers, maybe this will
    work, if it does thanks
    , Feb 17, 2006
    #8
  9. * Daniel T.:
    > * :
    >
    >> Im actually kinda embarassed to ask this question...
    >>
    >> @code start
    >> #include <iostream>
    >> int main() {
    >> unsigned long long a = 1;
    >> unsigned long long b = 1;
    >> for (int i = 0; i < 45; i++) {
    >> a += b;
    >> std::cout << a/b << std::endl;
    >> b += a;
    >> std::cout << b/a << std::endl;
    >> }
    >> std::cin.get();
    >> }
    >> @code end
    >>
    >> Why cant i get it to work?

    >
    > What output were you expecting?


    It seems he wants a series converging (slowly) to the golden ratio, or
    something like that.

    The problem is that he performs an integer division instead of a
    floating point division.

    Here are some ways of forcing a floating point division in C++:

    double(a)/b instead of a/b
    1.0*a/b instead of a/b
    (a+0.0)/b instead of a/b

    double a instead of unsigned long long a;

    We should note, however, that the above is not a standard C++ program
    since there is no "long long" type in C++.

    C++ does have a "long double" type.

    --
    A: Because it messes up the order in which people normally read text.
    Q: Why is it such a bad thing?
    A: Top-posting.
    Q: What is the most annoying thing on usenet and in e-mail?
    Alf P. Steinbach, Feb 17, 2006
    #9
  10. Guest

    Daniel T. wrote:

    > Here is a recursive algorithm:
    >
    > int fibonacci( int i ) {
    > if ( i == 0 ) return 0;
    > if ( i == 1 ) return 1;
    > else return fibonacci( i - 1 ) + fibonacci( i - 2 );
    > }
    >
    > And non-recursive:
    >
    > int fibonacci( int i ) {
    > int result[] = { 0, 1 };
    > while ( i > 1 ) {
    > int t = result[0];
    > result[0] = result[1];
    > result[1] = result[0] + t;
    > --i;
    > }
    > return result;
    > }
    >
    > int main() {
    > for ( int i = 0; i < 45; ++i )
    > cout << i << ": " << fibonacci( i ) << '\n';
    > }


    FWIW I justput up an O(1) solution on comp.programming. Here it is:

    /*
    run time fibonacci
    */
    //Boost.Preprocessor library
    // available at http://wwww.boost.org
    #include <boost/preprocessor/repetition.hpp>
    #include <boost/preprocessor/control/if.hpp>
    #include <boost/preprocessor/comparison/equal.hpp>
    #include <boost/preprocessor/empty.hpp>
    #include <boost/preprocessor/comma.hpp>
    #include <boost/preprocessor/arithmetic/add.hpp>

    #include <iostream>
    #include <stdexcept>

    template<int N>
    struct fibonacci{
    static const int value
    = fibonacci<N-1>::value
    + fibonacci<N-2>::value;
    };

    template<>
    struct fibonacci<0>{
    static const int value = 0;
    };

    template<>
    struct fibonacci<1>{
    static const int value = 1;
    };

    #define FIB_SEQ1(N) \
    BOOST_PP_IF(N,BOOST_PP_COMMA,BOOST_PP_EMPTY)()\
    fibonacci< N >::value

    #define FIB_SEQUENCE(z,N,unused) FIB_SEQ1(N)

    #define MAX_FIB 46

    int rt_fibonacci(int n)
    {
    static int const values[] = {
    BOOST_PP_REPEAT( BOOST_PP_ADD(MAX_FIB,1) ,FIB_SEQUENCE,~)
    };
    if( (n < 0) || (n > MAX_FIB)) {
    throw(std::eek:ut_of_range(
    "fibonacci input out of range"
    )
    );
    }
    return values[n];
    }

    int main()
    {
    for(int i=0;i <=MAX_FIB;++i){
    std::cout << rt_fibonacci(i) << '\n';
    }
    }

    regards
    Andy Little
    , Feb 17, 2006
    #10
  11. Guest


    > Here are some ways of forcing a floating point division in C++:
    >
    > double(a)/b instead of a/b
    > 1.0*a/b instead of a/b
    > (a+0.0)/b instead of a/b
    >
    > double a instead of unsigned long long a;

    Is it not the divsor that controls the return type of operator/ ?
    As in a/double(b)?
    , Feb 20, 2006
    #11
  12. * :
    >
    >> Here are some ways of forcing a floating point division in C++:
    >>
    >> double(a)/b instead of a/b
    >> 1.0*a/b instead of a/b
    >> (a+0.0)/b instead of a/b
    >>
    >> double a instead of unsigned long long a;

    > Is it not the divsor that controls the return type of operator/ ?
    > As in a/double(b)?


    No, the conversion does not depend on the particular operator involved.

    With two arguments of different types, the type that has the largest set
    of values (imprecisely speaking) determines the type of the expression,
    and the other argument is converted "up" to that type.

    IIRC this falls under the "usual arithmetic conversions" in the standard.

    --
    A: Because it messes up the order in which people normally read text.
    Q: Why is it such a bad thing?
    A: Top-posting.
    Q: What is the most annoying thing on usenet and in e-mail?
    Alf P. Steinbach, Feb 20, 2006
    #12
  13. Triple-DES Guest

    On 3 Okt, 04:53, Mark Casternoff <> wrote:
    > On 2006-02-17 07:22:28 -0500, said:
    > > FWIW I justput up an O(1) solution on comp.programming. Here it is:

    >
    > > /*
    > >     run time fibonacci
    > > */
    > > //Boost.Preprocessor library
    > > // available athttp://wwww.boost.org
    > > #include <boost/preprocessor/repetition.hpp>
    > > #include <boost/preprocessor/control/if.hpp>
    > > #include <boost/preprocessor/comparison/equal.hpp>
    > > #include <boost/preprocessor/empty.hpp>
    > > #include <boost/preprocessor/comma.hpp>
    > > #include <boost/preprocessor/arithmetic/add.hpp>

    >
    > > #include <iostream>
    > > #include <stdexcept>

    >
    > > template<int N>
    > > struct fibonacci{
    > >     static const int value
    > >     = fibonacci<N-1>::value
    > >     + fibonacci<N-2>::value;
    > > };

    >
    > > template<>
    > > struct fibonacci<0>{
    > >     static const int value = 0;
    > > };

    >
    > > template<>
    > > struct fibonacci<1>{
    > >     static const int value = 1;
    > > };

    >
    > > #define FIB_SEQ1(N) \
    > > BOOST_PP_IF(N,BOOST_PP_COMMA,BOOST_PP_EMPTY)()\
    > > fibonacci< N >::value

    >
    > > #define FIB_SEQUENCE(z,N,unused) FIB_SEQ1(N)

    >
    > > #define MAX_FIB 46

    >
    > > int rt_fibonacci(int n)
    > > {
    > >     static int const values[]  = {
    > >        BOOST_PP_REPEAT( BOOST_PP_ADD(MAX_FIB,1) ,FIB_SEQUENCE,~)
    > >     };
    > >     if( (n < 0) || (n > MAX_FIB)) {
    > >         throw(std::eek:ut_of_range(
    > >                 "fibonacci input out of range"
    > >             )
    > >         );
    > >     }
    > >     return values[n];
    > > }

    >
    > > int main()
    > > {
    > >     for(int i=0;i <=MAX_FIB;++i){
    > >         std::cout << rt_fibonacci(i) << '\n';
    > >     }
    > > }

    >
    > > regards
    > > Andy Little

    >
    > Of course, you can directly compute any particular fibonacci number
    > directly by using the Binet formula.  No need to jump through all the
    > hoops of calculating x-1 and x-2 and certainly no need for recursion.  
    > Bonus:  It takes only 1 line of c++ code.


    Andy's solution would still outperform it (in runtime) as it is just a
    table lookup. Unless, of course, you implement the Binet formula using
    template metaprogramming. I'd really like to see that done in one
    line :)
    Triple-DES, Oct 3, 2008
    #13
  14. Puppet_Sock Guest

    On Oct 2 2008, 10:53 pm, Mark Casternoff <> wrote:
    > On 2006-02-17 07:22:28 -0500, said:
    >
    > > Daniel T. wrote:

    [snip]

    Wow. You must have a *really* slow internet connection.
    Socks
    Puppet_Sock, Oct 3, 2008
    #14
    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,006
  2. fighterman19
    Replies:
    11
    Views:
    800
    Karl Heinz Buchegger
    Sep 8, 2003
  3. Fibonacci numbers

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

    STL for Fibonacci Heap??

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

Share This Page