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
– Richard Critten, Commented Jul 23, 2021 at 9:41
orders is an int. (orders*(orders+1))%mod is all ints — 463035818_is_not_an_ai
– 463035818_is_not_an_ai, Commented Jul 23, 2021 at 9: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
– Richard Critten, Commented Jul 23, 2021 at 9:45
You try to multiply two signed 32bit ints, each one being a 10⁹. — bipll
– bipll, Commented Jul 23, 2021 at 9:45
You will need to learn modulo arithmetic to solve it without overflows. — Yksisarvinen
– Yksisarvinen, Commented Jul 23, 2021 at 9:47

Marek R · Accepted Answer · 2021-07-23 10:06:35Z

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

User · Accepted Answer · 2021-07-23 10:05:22Z

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;

Collectives™ on Stack Overflow

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

2 Answers 2

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related