## 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`

.