CODEWITHSUNDEEP
c++optimization
CPPCoder
CPPCoder

Reputation: 165

CPP: Type casting to prevent overflows

The statement I'm writing where values may overflow is as below:

fact = ((fact * (llu) (i - 1)) / (llu) (i - M)) % MOD;
llu Ans = (llu) C[k - 1] * fact;

Here llu means unsigned long long

i is a signed integer and varies between values ranging from 210 to 220

MOD is 109 + 9

Variables fact and Ans are of type unsigned long long.

M is a signed integer and can be atmost as high as 210

C[k - 1] is the (k - 1)th index term of an int array C and is of order of 109

All values are always positive.

Question: Now, regarding the type casting I've done in the above code (from int to unsigned long long); Is it fine enough to handle overflows or am I doing more/less/incorrect type casting?

Further, is it right to perform division by (i - M) in the 1st line of my code or should it preferably be written as:

fact = fact * (llu) (i - 1);
fact = (fact / (llu) (i - M)) % MOD;

Upvotes: 0

Views: 653

Answers (1)

andreaplanet
andreaplanet

Reputation: 771

You didnt define the limits of fact, since it's part of the first expression. If fact can initially be 2^60 for example then you have an overflow.

When you multiply integer bit values you need to sum the amount of bits. For example if you multiple two 32 bit values you will need/get 32+32 = 64bits. 

fact=((fact*(llu)(i-1))/(llu)(i-M))%MOD;

In our example we have i up to 20 bits, it means that to avoid an overflow in the first expression fact must be at most Bitsof(unsigned long long)-20. If unsigned long long is 64 bit then fact can be up to 44 bits, e.g 2^44.

llu Ans=(llu)C[k-1]*fact;

In the second expression we have a similar situation, fact must be at most 64-30 bits (10^9 takes about 29 bits), after evaluating the first expression, which is verified by the %MOD expression. Fact will be less than 10^10 after first expression which is almost 32 bits.

Short answer: if fact is initially less than 2^44 then it will not overflow.

In such cases I prefer to use explicit integer sizes, for example type u_int64_t, I know it's unsigned 64 bit.

Upvotes: 1

Related Questions