Fibonacci weirdness

[dyingatmidnight]

Hello, I've been in the process of teaching myself C++, going through different tutorials and like. Anyway I was working on a fibonacci sequence program - I looked through the practice problems here and decided to do them all from beginner on upward. I thought I had it working only to find later when I went to play around with it some that I did not. Everything works up until the 47th value which comes out negative. I stepped through the loop and the numbers for 45 and 46 are correct and yet they are producing a negative...

Here's my code: I'm sure there's a better way to do this, I know I did it differently in school when we did Java but my mind is blanking.

#include <iostream>
using namespace std;
void fibonacci(int loop);

int main(){
	cout << "Please enter the number of fibonacci numbers you would like displayed: ";
	int loop;
	cin >> loop;
	fibonacci(loop);
	system("PAUSE");
}

void fibonacci(int loop){
	int one = 0;
	int two = 1;

	for(int i = 0; i < loop; i++){
		if(i == 0)
		{
			cout << i << ": " << i << "\n";
		}
		if(i == 1)
		{
			cout << i << ": " << i << "\n";
		}
		if(i > 1)
		{
		int nextNum = one + two;
		cout << i << ": " << nextNum << " " << "\n";
		one = two;
		two = nextNum;
		}
	}
}

everything is great apparently until it tries to add 1134903170 + 1836311903 and comes up with -132375223

[Narue]

What's the range of int? I bet not enough to handle that value, so on your system it wraps around and you find yourself with a negative value.

[Tomi1988]

int can be used from –2,147,483,648 to 2,147,483,647.
Use instead of int double!

void fibonacci(int loop){
  double one = 0;
  double two = 1;
  for(double i = 0; i < loop; i++)
  {
    if(i == 0)
    {
    cout << i << ": " << i << "n";
    }

    if(i == 1)
    {
    cout << i << ": " << i << "n";
    }

    if(i > 1)
    {
    double nextNum = one + two;
    cout << i << ": " << nextNum << " " << "n";
    one = two;
    two = nextNum;
    }
  }
}

[Narue]

int can be used from –2,147,483,648 to 2,147,483,647.

The range of int is not fixed in C++. This depends on the implementation, though it's never less than 16 bits. It's not wise to assume a specific range.

Use instead of int double!

And what happens when he reaches the limit of double? :icon_rolleyes:

[Tomi1988]

And what happens when he reaches the limit of double?

I don't know. What is the solution?

[Narue]

It depends on the needs of the program. Most of the time when writing a Fibonacci program, it's for an early programming course. In that case simply recognizing the limitation is enough. If it needs to be more robust and handle larger values, some library to remove the limitation (GMP, for example) would be necessary. Switching to double would extend the range of possible values, but the inherent limitations are still there; I'd call it more of a temporary Band-Aid than a fix.

One nice thing about this exercise is it opens the way for another exercise where one implements an arbitrary length arithmetic type.

[ravenous]

I don't know. What is the solution?

The solution is to write your own arbitrary precision integer version, which isn't as complicated as it sounds.

[ravenous]

Also, since you're learning, there are some performance considerations that you might want to think about in your function. For example, you have:

for(int i = 0; i < loop; i++){
    if(i == 0)
    {
        cout << i << ": " << i << "\n";
    }
    if(i == 1)
    {
        cout << i << ": " << i << "\n";
    }
    if(i > 1)
    {
        int nextNum = one + two;
        cout << i << ": " << nextNum << " " << "\n";
        one = two;
        two = nextNum;
    }
}

But, you know that when i is 0 or 1, you're going to have to do something different. Rather than check every time you go through the loop, why not start the loop at i = 2 :

cout << "0: " << one << "\n";
cout << "1: " << two << "\n";
for( int i = 2; i < loop; ++i ){
    int nextNum = one + two;
    cout << i << ": " << nextNum << " " << "\n";
    one = two;
    two = nextNum;
}

Now you don't pay for the checks at every loop iteration :o)

[Jimmy_7]

Hello. I am just wondering if you have figured this problem out, yet? I know that this question has been asked 5 years ago, and in that time, there was enough time to figure it out. However; I am going to assume that you haven't figured it out yet. You can Always change all of your 'int's' to 'long long int' this should allow you to loop it up to 84 times before it goes wierd on you again. I am going to leave this post here, in case some future programmer may need to know why his or her Fibonacci program is working so weirdly after so many iterations.