Fibonacci series in C++ can't get more than 47

问题:

I designed this program that can print the Fibonacci Series (series[i] = series[i-1] + series[i-2]) but i can't get more than 47 numbers because the 48th they become negative and strange numbers (i think this happens when the list is out of range or the item is null):

#include <iostream>
#include <vector>

using namespace std;

int main ()
{
    int length;
    string again = "";
    do {
        cout << "Enter the length you want in your sequence: ";
        cin >> length;
        vector<int> series(length);
        for (int n=0; n<=1; n++) series[n] = n;
        for (int number=2; number<=length; number++) {
            series[number] = series[number-1] + series[number-2];
        }
        for (int i=0; i<length; i++) cout << series[i] << " ";
        cout << endl << "Do it again ? <y/n> ";
        cin >> again;
        cout << endl;
    } while (again == "y");
}

EDIT:

"Improved" code:

#include <iostream>
#include <vector>
#include <string>

std::vector<int> fibonacci (int length)
{
    std::vector<int> series(length);
    series[0] = 0;
    series[1] = 1;
    for (int num=2; num<length; num++) {
        series[num] = series[num-1] + series[num-2];
    }
    return series;
}

int main ()
{
    std::string again;
    do {
        std::cout << "Enter how many numbers you want in your series: ";
        int length;
        std::cin >> length;
        std::vector<int> series(length);
        series = fibonacci(length);
        for (int n=0; n<length; n++) std::cout << series[n] << " ";
        std::cout << "\nDo it again <y/n> ? ";
        std::cin >> again;
        std::cout << std::endl;
    } while (again == "y");
}

回答1:

When you get to the 47th value, the numbers go out of int range. The maximum int value is 2,147,483,647 and the 46th number is just below at 1,836,311,903. The 47th number exceeds the maximum with 2,971,215,073.

Also, as LeonardBlunderbuss mentioned, you are exceeding the range of the vector with the for loop that you have. Vectors start with 0, and so by having number<=length; the range+1 element will be called. The range only goes up to length-1.

回答2:

You are encountering integer overflow, meaning that you are trying to calculate a number that is outsize of the bounds of INT_MAX and INT_MIN. In the case of an unsigned number, it just overflows to zero and starts over, while in the case of a signed integer, it rolls over to INT_MIN. In both cases this is referred to as integer overflow or integer wraparound.

You could put a band-aid on the solution by using long long int (likely 64-bits on most modern systems) instead of int for your primitive data type, or you could use a better approach like a library that supports (almost) arbitrarily long data types, like libBigInteger.

References

1. Integer Overflow, Accessed 2014-03-04, <http://en.wikipedia.org/wiki/Integer_overflow>
2. C++ Big Integer Library, Accessed 2014-03-04, <https://mattmccutchen.net/bigint/>
3. The limits.h Header File, Accessed 2014-03-04, <http://tigcc.ticalc.org/doc/limits.html>

回答3:

This is my solution to calculating BIG fibonacci numbers

// Study for algorithm that counts n:th fibonacci number                        

#include <iostream>
#include <cstdlib>

#include "boost/multiprecision/cpp_int.hpp"

#define get_buffer(a) buffer[(a)%2]
#define BIG boost::multiprecision::cpp_int

int main(int argc, const char* argv[])
{
  // atoi returns 0 if not integer                                              
  if(argc != 2 || atoi(argv[1]) < 1){
    std::cout << "You must provide one argument. Integer > 0" << std::endl;
    return EXIT_SUCCESS;
  }

  // ring buffer to store previous two fibonacci number, index it with  [i%2]   
  // use defined function get_buffer(i), it will do the magic for you           
  BIG buffer[2]={ 1, 1 };

  // n:th Fibonacci                                                             
  unsigned int fn = atoi(argv[1]);

  // count loop is used if seeked fibonacci number is gt 2                      
  if(fn > 2){
    for(unsigned int i = 2; i < fn; ++i){                                       
      get_buffer(i) = get_buffer(i-1) + get_buffer(i-2);
      // get_buffer(i-1) + get_buffer(i-2) == buffer[0] + buffer[1]
      // if you want to print out every result, do it here
    }
  }

  // Result will be send to cout                                                
  std::cout << "Fibonacci[" << fn << "] is " << get_buffer(fn-1) << std::endl;
  return EXIT_SUCCESS;
}