C++ numbers add to a negative

Question

So I was just practicing coding a dynamic solution to the Fibonacci sequence which would return the n'th Fibonacci number and I kept coming across a problem which I can't quite figure out. I am getting two positive numbers adding to a negative!

Code:

int fib(int n) {
    vector<int> v;
    v.push_back(1);
    v.push_back(1);
    for (int i = 2; i <= n; i++) {
        v.push_back( v.at(i-1) + v.at(i-2) );
        cout << v.at(i-1) << " + " << v.at(i-2) << " = " << (v.at(i-1) + v.at(i-2)) << endl;
    }
    return v.at(n);
}

try running fib(50), note cout is just for debugging

enter image description here

You have undefined behaviour due to signed integer overflow. — chris, Sep 08 '13 at 04:17
Try this: http://stackoverflow.com/questions/5026104/how-to-store-1000000-digit-integers-in-c?lq=1 — dcaswell, Sep 08 '13 at 04:25
They just don't teach how computers work anymore, do they? No requirement to understand integer arithmetic, signed vs. unsigned. Only high-level languages so it comes as a surprise when an int simply isn't big enough. — Carey Gregory, Sep 08 '13 at 04:29
I come from university like 2 years back, and we learned even in detail how float and doubles work, so they do teach that sort of stuff... guess someone wasn't paying attention though :D — SinisterMJ, Sep 08 '13 at 04:56
@CareyGregory, In my experience, no they don't. I picked up programming as a hobby in middle school, and when I got to high school I took both of the programming classes available, and this was never taught. I couldn't tell you if it was taught at my college or not though because I tested out of the programming courses. Certainly wasn't on any of the exams though. — Drew Chapin, Sep 08 '13 at 05:16

score 7 · Accepted Answer · edited May 23 '17 at 12:01

7

You need to change int to unsigned int or even better unsigned long long. Your result is overflowing the maximum value of int on your system. Because int is signed, when the most significant bit gets set, it becomes a negative number. See the Stack Overflow question titled maximum value of int, and this Swarthmore College page on binary arithmatic for more information. If you're using Visual Studio, take a look at the Data Type Ranges article on MSDN.

In addition to switching to unsigned long long, you should probably check for overflow errors such as this and throw an exception. A revised version of your code could look like this.

unsigned long long fib(int n) {
    vector<unsigned long long> v;
    v.push_back(1);
    v.push_back(1);
    for (int i = 2; i <= n; i++) {
        if( v.at(i-1) > (std::numeric_limits<unsigned long long>::max() - v.at(i-2)) )
            throw std::overflow_error("number too large to calculate");
        v.push_back( v.at(i-1) + v.at(i-2) );
        cout << v.at(i-1) << " + " << v.at(i-2) << " = " << (v.at(i-1) + v.at(i-2)) << endl;
    }
    return v.at(n);
}

You would also want to make sure the code calling your function can handle an exception by using a try... catch.... Here's an example

try {
    std::cout << "2000th number = " << fib(2000) << std::endl;
} catch( std::overflow_error& ex ) {
    std::cerr << ex.what() << std::endl; 
}

edited May 23 '17 at 12:01

Community

1
1

answered Sep 08 '13 at 04:22

Drew Chapin

7,779
5
58
84

1

"You need to change `int` to `unsigned int` or even better `unsigned long`." Depends on the compiler he's using. I believe that `long` in MSVC is just 4 bytes (not 8). To truly ensure the width of an integer, use the `stdint.h` (or `cstdint`) header file. – inspector-g Sep 08 '13 at 04:32
On many platforms int and long are the same size, signed or otherwise. – Carey Gregory Sep 08 '13 at 04:34
@inspector-g, and @Carey Gregory, You're right, I actually meant to type `unsigned long long`. I fixed the answer. I blame it on distraction from watching Brisco County Jr. – Drew Chapin Sep 08 '13 at 04:36
2

OK, but going to long long just postpones the problem. A really good answer would address how to avoid (or deal with) integer overflow regardless of the size of the types. Add that to your answer and I'll +1. – Carey Gregory Sep 08 '13 at 04:45
@CareyGregory, I added checking for overflow, and throwing an `overflow_error` exception. – Drew Chapin Sep 08 '13 at 05:05
Thanks for the help everyone. I actually DID learn about signed vs. unsigned integers, its been a while is all. By the way, why does the iterator `i` have to be long long? – E.Cross Sep 08 '13 at 20:54
@user35039, no it doesn't. Not sure why I changed it. – Drew Chapin Sep 08 '13 at 20:56

leesei · Answer 2 · 2013-09-08T05:40:17.893

2

Because of how C stores your int (signed int) in memory, the most significant bit indicates a negative number. So you'll get negative number if you overflow it with large numbers.

Reference:

edited Sep 08 '13 at 05:40

answered Sep 08 '13 at 04:32

leesei

6,020
2
29
51

Which bit is the "first" bit? And is that the C++ standard? – Carey Gregory Sep 08 '13 at 04:38
This is potentially wrong - see this question's top answer http://stackoverflow.com/questions/12125650/what-do-the-c-and-c-standards-say-about-bit-level-integer-representation-and-m, *[ Example: this International Standard permits 2’s complement, 1’s complement and signed magnitude representations for integral types. —end example ] [§3.9.1/7]* – jdphenix Sep 08 '13 at 04:52

C++ numbers add to a negative

2 Answers2

Linked