1

I noticed in my fibonacci sequence that I'm getting negative numbers after a certain point:

267914296 433494437 701408733 1134903170
1836311903 -1323752223 512559680 -811192543 -298632863

Does this have to do with the limited range of "int"? or is there something wrong with my code?

Here is the code:

using std::cout;

int main()
{

int n = 50, f1 = 0, f2 = 1, fn = 0, i = 0;

cout << "0 ";
for (i = 0; i < n; i++)
{
    fn = f1 + f2;
    f2 = f1;
    f1 = fn;

    cout << fn << " ";
}
Bill
  • 14,257
  • 4
  • 43
  • 55
M0113Y
  • 13
  • 6
  • 2
    'Does this have to do with the limited range of "int"?' Yes, highly likely. If it happens around 2G, yes, that's pretty much it. A simple test would be to use `long long int` and see how it fares. – R. Martinho Fernandes Jun 24 '13 at 16:18
  • At what point do the answers go negative? But I'll hazard a "yes, that's why". – Grimm The Opiner Jun 24 '13 at 16:19
  • At what certain point do you start getting wierd numbers? – Peter Rasmussen Jun 24 '13 at 16:20
  • @JonMolley ,please see BLUEPIXY's answer here. http://stackoverflow.com/questions/17037868/the-biggest-number-in-c This will solve your problem without having to use GMP. –  Jun 24 '13 at 18:00

3 Answers3

2

I'll bet it does have something to do with the range of int. you're probably overflowing

An integer normally has 32 bits, and one of those bits is the sign, so if you have a number like

01111111111111111111111111111111

which is a little bit over 2 billion, and you add 2 to it, then you get

10000000000000000000000000000001

which is negative(the first number is the sign, 0 is positive and 1 is negative)

If you want to store more numbers, you can use long ints.

Sam I am says Reinstate Monica
  • 30,851
  • 12
  • 72
  • 100
2

Yes, this has to do with the limited range of int. This is called rollover or overflow, and works just like the odometer in your car. Once the number passes its highest possible value, it rolls over to its lowest possible value (which for int is a negative number). Consider using an unsigned int or long unsigned int, though the second one is not neccessarily longer (it's platform-dependent). A long double can hold even bigger numbers. If you'd like to use an arbitrarily large number (as big as you want), you can find appropriate libraries in answers to this question.

Community
  • 1
  • 1
IanPudney
  • 5,941
  • 1
  • 24
  • 39
  • While *wraparound* (another name) is common behavior for many platforms when signed integers overflow, note that C++ actually treats signed integer overflow as *undefined behavior*; in other words, the program is broken the moment some integer overflows. – Sebastian Redl Jun 24 '13 at 16:37
0

Try using "long int" instead of "int".

Jairo Florián
  • 1