c++ Integer overflow in spite of using unsigned int and modulo operations

Question

        int orders=1000000000;
        int mod=pow(10,9)+7;
        unsigned int total=4294967295; 
        total=(orders*(orders+1))%mod;
        total/=2;
        return total;

expected Answer= 21

BUT getting

runtime error: signed integer overflow: 1000000000 * 1000000001 cannot be represented in type 'int'

I also tried

        int orders=1000000000;
        int mod=pow(10,9)+7;
        long long total=0LL; 
        total=(long long)(orders*(orders+1))%mod;
        total/=2;
        return total;

Same error

//Compiled with clang 11 using the latest C++ 17 standard.

May I know why this is happening? I thought maybe long long is getting truncated to int hence the 0LL, But still that didn't solve the issue.

When tried on other compiler, getting output

for 1st code:

-243309312

for second peice of code:

1904174336

Don't use `pow` in a program investigating integer behaviour; as we first have to rule out floating point issues before looking at your problem. Why not just type the integer constant to replace `pow(10,9)` ? — Richard Critten, Jul 23 '21 at 09:41
`orders` is an `int`. `(orders*(orders+1))%mod` is all `int`s — 463035818_is_not_an_ai, Jul 23 '21 at 09:44
There is no unsigned integer in `(orders*(orders+1))%mod;` so the calculation is done signed. The result type on the LHS of the assignment operator does not participate in the type conversions of the expression on the RHS until the expression has ben evaluated and the result is about to be assigned. Note that `(a * b) mod m == ((a mod m) * (b mod m)) mod m` — Richard Critten, Jul 23 '21 at 09:45
You try to multiply two signed 32bit ints, each one being a 10⁹. — bipll, Jul 23 '21 at 09:45
You will need to learn modulo arithmetic to solve it without overflows. — Yksisarvinen, Jul 23 '21 at 09:47
It is nicer when code is enclosed in function or in class so the input outputs are obvious. It is better when [mcve] is provided using some online compiler. And it is perfect when you can provide live test. https://godbolt.org/z/xh8eYY33M — Marek R, Jul 23 '21 at 09:47
using `pow(10,9)` to get 10⁹ is terrible. See [Why pow(10,5) = 9,999](https://stackoverflow.com/q/9704195/995714), [Why does pow(5,2) become 24?](https://stackoverflow.com/q/22264236/995714), [Why does gcc compiler output pow(10,2) as 99 not 100?](https://stackoverflow.com/q/25474351/995714)... If you're really lazy then use `1e9 + 7` instead — phuclv, Jul 23 '21 at 09:56
`1000000000` requires 30 bits to be able to represent it. `1000000000*100000001` requires about 60 bits, so that calculation will definitely overflow a 32-bit `unsigned int`. Incidentally, although `unsigned int` is often 32-bits in practice on modern systems, the standard doesn't require more than 16 bits (and, yes, there are real systems with a 16-bit `int` and `unsigned int` types). — Peter, Jul 23 '21 at 11:53

User · Answer 1 · 2021-07-23T10:05:22.700

integer range considering size to be 4 bytes

-2,147,483,648 to 2,147,483,647

Unsigned int max  4,294,967,295

Now the statement

total=(orders*(orders+1))%mod;

will try to put orders*(orders+1) into type int which is signed and has max value of "2,147,483,647" as orders is type of int.

so the multiplication results

1000000001000000000

and it's not in range of int .hence you have overflow issue here .

For better visibility run this

int orders=1000000000;
        int mod=pow(10,9)+7;
        unsigned int total=4294967295; 
        total=(orders*(orders+1))%mod;
        total/=2;
        cout<< "result= "<<total<<"\n"; 
        int val = (orders*(orders+1));
        std::cout<<"val = "<<val;
        unsigned int t=(-486618624)%mod;
        std::cout<<"\nresult 2 = "<<t/2;

score 1 · Accepted Answer · answered Jul 23 '21 at 10:06

Basically problem is you have integer overflow just after multiplication.

To overcome this problem you have to approach topic using one of two solutions.

use integer type which can hold a result of such magnitude, for example: unsigned long long int
use algorithm which is able to do that calculation without integer overflow (for that I can't find good and simple document in English)

Using second approach:

constexpr unsigned mutiplyModulo(unsigned a, unsigned b, unsigned n)
{
    unsigned m = 1, w = 1;

    while (m) {
        if (b & m)
            w = (w + a) % n;
        a = (a << 1) % n;
        m <<= 1;
    }
    return w;
}

constexpr unsigned int intpow(unsigned int x, unsigned int n)
{
    unsigned int r = 1;
    while (n) {
        if (n & 1)
            r *= x;
        x *= x;
        n /= 2;
    }
    return r;
}

unsigned int foo(unsigned int orders)
{
    constexpr auto mod = intpow(10u, 9u) + 7u;
    unsigned int total = mutiplyModulo(orders, orders + 1, mod);
    total /= 2;
    return total;
}

https://godbolt.org/z/ePW7WxcTe

c++ Integer overflow in spite of using unsigned int and modulo operations

2 Answers2