Array of Fibonacci numbers: Elements do not make sense when array size > 28

Question

I have a short C++ program that populates an array of Fibonacci numbers, then calculates the sum of the terms, and displays the sum to the screen.

#include <iostream>

using namespace std;

const int SIZE = 10;

int main() {
    int sum = 0; // running sum
    int fib[SIZE]; // array of Fibonacci numbers

    // initialize 1st and 2nd elements = 1, the rest to 0
    for (int i = 2; i < SIZE; i++) { 
        fib[0] = 1; 
        fib[1] = 1; 
        fib[i] = 0; 
    }

    // populate the array:
    // next term in Fibonacci sequence: fib[current] - 1 + fib[current] - 2
    for (int i = 0; i < SIZE; i++) { 
        fib[i + 1] = fib[i] + fib[i - 1]; 
        sum = sum + fib[i + 1]; 
    }

    // display the contents and the sum
    for (int i = 0; i < SIZE; i++) { 
        cout << i + 1 << ": " << fib[i] << endl; 
    }
    cout << "\nSum of the Fibonacci numbers: " << sum << endl;

    //system("pause");
    return 0;
}

When I start with SIZE = 10, the program adds the sum just fine...

OUTPUT:

1: 1
2: 1
3: 2
4: 3
5: 5
6: 8
7: 13
8: 21
9: 34
10: 55

Sum of the Fibonacci numbers: 231

--------------------------------
Process exited after 0.02942 seconds with return value 0
Press any key to continue . . .

In fact, any value of SIZE between 2 and 28 works well. I get the correct, positive value for the sum.

However, when I try to define SIZE = 29 or greater, this happens:

OUTPUT:

1: 1
2: 32764
3: 32765
4: 65529
5: 98294
6: 163823
7: 262117
8: 425940
9: 688057
10: 1113997
.
.
.
25: 1519229809
26: -1836801828
27: -317572019
28: 2140593449
29: 1823021430

Sum of the Fibonacci numbers: 1160283831

--------------------------------
Process exited after 0.05147 seconds with return value 0
Press any key to continue . . .

I don't understand why the second element changed from 1 to 32764, and why I have negative values in the array when I define SIZE = 29 or greater. Actually, I'll start getting random values and each value is unusually different after every compilation and run.

Does this relate to compilation? Maybe change data types from int to long? Did I simply run out of place holders to represent the digits? Comments are appreciated.

P.S. I've yet to rewrite this recursively. But I'm not too worried about it.

Edit: I truly appreciate the comments. I learn new things every time.

Answer 1

You have:

for (int i = 0; i < SIZE; i++)
{
   fib[i + 1] = fib[i] + fib[i - 1];
   sum = sum + fib[i + 1];
}

For i == 0, you are acessing fib[i-1], i.e. fib[-1].
for i == SIZE-1, you are accessing fib[SIZE].
They are causes for undefined behavior.

You need to use:

sum = 2; // Takes care of fib[0] and fib[1]
for (int i = 1; i < SIZE-1; i++)
{
   fib[i + 1] = fib[i] + fib[i - 1];
   sum += fib[i + 1];
}

PS

It's important to note that sum overflows for values of SIZE greater than 44 and fib[SIZE-1] overflows for values of SIZE greater than 46 if sizeof(int) is 4. Use of long or long long will be necessary when SIZE exceeds those limits.

Answer 2

Please format your code so you can better read the for loops.

Why do you set fib[0] and fib[1] to 1. SIZE times?

So fib[0] is definitely 1 afterwards :)

for (int i = 0; i < SIZE; i++) { 
    fib[i + 1] = fib[i] + fib[i - 1]; 
    sum = sum + fib[i + 1]; 
}

But regardless of the overhead in the second loopfib[0] is still 1 but fib[1] becomes fib[0] + fib[-1]

fib[-1] is a really bad index to rely on and leads to random behavior.

Here is how it works: http://cpp.sh/54dg

#include <iostream>
#include <string>

using namespace std;

const int SIZE = 30;
int main() {
    int sum = 0; // running sum
    int fib[SIZE]; // array of Fibonacci numbers

    // initialize 1st and 2nd elements = 1, the rest to 0
    for (int i = 2; i < SIZE; i++) { 
        fib[0] = 1; 
        fib[1] = 1; 
        fib[i] = 0; 
    }

    // populate the array:
    // next term in Fibonacci sequence: fib[current] - 1 + fib[current] - 2
    for (int i = 1; i < SIZE-1; i++) { 
        fib[i + 1] = fib[i] + fib[i - 1]; 
        sum = sum + fib[i + 1]; 
    }

    // display the contents and the sum
    for (int i = 0; i < SIZE; i++) { 
        cout << i + 1 << ": " << fib[i] << endl; 
    }
    cout << "\nSum of the Fibonacci numbers: " << sum << endl;

    //system("pause");
    return 0;
}

Answer 3

Your loop for (int i = 0; i < SIZE; i++) { fib[i + 1] = fib[i] + fib[i - 1]; sum = sum + fib[i + 1]; } is writing outside the fib array. Specifically it is writing in the position fib[i + 1]=SIZE when i=fib[i + 1]-1. The same happens in the sum sum = sum + fib[i + 1];

Similar error happens accessing fib[i - 1] for i==0