CODEWITHSUNDEEP
c
TSR
TSR

Reputation: 20589

Multiplying two positive numbers returns negative in C

I don't understand why the code below outputs a negative number

int main() {
    int cases = 1000000 * 50;
    int now = 1;
    for (int i = 0; i < cases; i++) {
        now++;
        now = now * now;
        now = now % cases;
        if (now < 0) {
            break;
        }
    }
    printf("%d", now);
    return 0;
}

output is: -37008604

Upvotes: 2

Views: 849

Answers (2)

chqrlie
chqrlie

Reputation: 144969

The posted code has undefined behavior when now becomes larger than sqrt(INT_MAX), which is 46340 on 32-bit systems, because signed arithmetic overflow has undefined behavior. The result of computing now * now causing an overflow could be a negative number, or an exception or anything else, and computing now % cases with a negative now produces a number between -cases+1 and 0, which is what you observe.

If you use type long long for the intermediary result, the program will have defined behavior and output 22152025:

Note however that you make the assumption that int is large enough to represent 50000000, which the C Standard does not guarantee. For complete portability, you should use type long for now, cases and i.

Here is a modified version:

#include <stdio.h>

int main() {
    long cases = 1000000L * 50;
    long now = 1;
    for (long i = 0; i < cases; i++) {
        now++;
        now = ((long long)now * now) % cases;
        if (now < 0) {
            break;
        }
    }
    printf("%ld\n", now);
    return 0;
}

Upvotes: 6

Nitin Tripathi
Nitin Tripathi

Reputation: 1254

now is going beyond MAX of int. Adding following code inside of for loop will provide much more information.

printf("%d->%d\n", i,now);

it indicates: for 32 bit system - after 4 iteration, your value of now is overflowing the allocated memory of int.

Output after adding debugs.

0->4
1->25
2->676
3->458329
4->-37008604

Upvotes: 1

Related Questions