Question:
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?
Answer:
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 .