Fibonacci...

F

felixnielsen

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
 
F

felixnielsen

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
 
V

Victor Bazarov

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
 
V

Victor Bazarov

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
 
F

felixnielsen

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

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? 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';
}
 
V

Victor Bazarov

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
 
F

felixnielsen

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
 
A

Alf P. Steinbach

* Daniel T.:
* (e-mail address removed):


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

andy

Daniel said:
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
 
J

jesper

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)?
 
A

Alf P. Steinbach

* (e-mail address removed):
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.
 
T

Triple-DES

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 :)
 

Ask a Question

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

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,744
Messages
2,569,484
Members
44,905
Latest member
Kristy_Poole

Latest Threads

Top