Multiplying two positive numbers returns negative in C

Question

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

[Integer overflow](https://en.wikipedia.org/wiki/Integer_overflow) and [undefined behaviour](https://en.wikipedia.org/wiki/Undefined_behavior). — P.P, May 08 '20 at 12:45

chqrlie · Answer 1 · 2020-05-08T18:03:12.340

6

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;
}

edited May 08 '20 at 18:03

answered May 08 '20 at 12:51

chqrlie

131,814
10
121
189

Also note `long` and `long long` can be exactly the same type, and this is generally the case when compiling for 64b. – bruno May 08 '20 at 13:56
" make the assumption that int is large enough to represent 50000000" is interesting as code here also assumes things, and gets away with it with potential `long = int * int;`. Consider if code was `10000 * 50`. That `int` * `int` might overflow. On some unicorn machine with 24-bit `int`, `1000000 * 50` would overflow. As the left side `long` does not influence the right side, the math on the right should insure the calculation is done using at least the width of the left-side. Perhaps as `1000000L * 50`? Issue explored [here](https://stackoverflow.com/a/40637622/2410359). – chux - Reinstate Monica May 08 '20 at 17:44
@chux-ReinstateMonica: what a sharp eye! I guess this unicorn machine would not even have a friendly compiler warning the user about the overflow in this constant expression :( – chqrlie May 08 '20 at 18:02
1

Not so much a sharp eye as a black eye from bugs using narrow math on the right assigning to a wider left side result. Common enough porting code between 16,32,64 bit processors. – chux - Reinstate Monica May 08 '20 at 18:12

score 1 · Answer 2 · answered May 08 '20 at 13:06

1

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

answered May 08 '20 at 13:06

Nitin Tripathi

1,224
7
17

just a detail, *allocated memory of int* is wrongly said for me, *now* can stay in a register – bruno May 08 '20 at 13:10

Multiplying two positive numbers returns negative in C

2 Answers2