How to avoid overflow in an expression? C++


I've been looking for an error in the code for a long time. Thanks to the VS debugger. The error is in this line:

this->b = ((hh * mul) % (this->p - 1));

this->b – variable of type int, 4 bytes. hh, mul, this->p – similar. The problem arises, for example, with numbers:

hh = -2156842;
mul = 3059;
this->p = 3061;

The error comes out in the very first expression. Multiplying a negative number hh and a positive mul results in a huge POSITIVE number. Is it an overflow? How to avoid it? How is memory allocated in expressions?


Yes, this is an overflow.

To avoid overflow, you should use one remarkable property of modulo comparisons: the numbers a * b and (a % m) * (b % m) are modulo m . However, it is not enough for us that they are comparable and we still need to keep the sign (I do not mean the choice between -x or +x , but the choice between x and x - m , where 0 < x < m ). But the % operator preserves it.

So, you can write the following:

auto mod = this->p - 1;
auto mul1 = hh % mod;
auto mul2 = mul % mod;
this->b = (mul1 * mul2) % mod;

However, it is worth remembering that even such a trick will not save if the this->p - 1 module is too large and the numbers hh , mul turn out to be "bad".

The memory before the variable is allocated exactly k bits. If, however, during execution, a certain number is obtained that does not fit into these k bits, then the "extra" bits will be cut off. For unsigned numbers, this means that, mathematically speaking, the result a * b will actually be (a * b) % (2^k) . For the unsigned, everything is a little more complicated there. It's all about representing negative numbers. You can read more about such a representation, for example, on Wikipedia . Both signed and unsigned numbers are looped. This means that if the numbers cover the range [L; R] , then R + 1 = L , L - 1 = R . For unsigned L = 0 , R = 2^k - 1 , for unsigned L = - 2^{k - 1} , R = 2^{k - 1} - 1 . That is, the result of a * b is actually (a * b - L) % (R - L) + L .

Scroll to Top