Modular arithmetic - competitive programming

Question

I saw a lot of competitive programmers writing code with ((a + b) % d + d) % d in C++. Why don't they just use (a + b) % d? What is that + d inside parentheses good for? Does it have something to do with negative numbers?

Thanks

Karilla

"Does it have something to do with negative numbers?" Have you tried using negative numbers with both methods and comparing the answers you get? – Broken

Oh, now I see. I was inattentive when I was trying to come up with answer on my own, sorry. Thanks a lot :) – Karilla

Are you sure it wasn't ((a + b) % d + d) % d? – Heist

No, it was like I wrote last time I've seen this, but It was probably because of that particular problem input constraints. Your version is more general, isn't it? Thanks, I edited question. – Karilla

Answer 1

Yes you are correct. Until C++11 the behaviour of the remainder operator % for negative arguments was left to the implementation, subject to some constraints. And adding d to the left argument can help that so long as the other terms in that argument sum to greater or equal to -d, which, in general is not the case. (-a / d multiples of d for the case of negative a would have been a better additive constant in your particular case.)

Adolfoadolph

Answer 2

Yes, it has something to do with negative numbers. It prevents the result from being a negative number under certain conditions. In this case, when the b variable is negative, the result of b % d is also negative. This result can never be greater than d, so adding d to this result forces the result to be positive.

Below code is Java code, but it has the same principle:

int a = 13;
int b = -23;
int d = 31;

int result1 = (a + b % d + d) % d;
int result2 = (a + b % d) % d;

System.out.println(result1);
System.out.println(result2);

It outputs the following:

21
-10

Genseric

Answer 3

To avoid integer overflow and to always keep number positive we use modular arithmetic. Compettitve programmers tend to use (a+b)%b instead of a%b when a is a negative number.

a%b = (a+b)%b
(a+b)%b = a%b + b%b = a%b + 0 = a%b

Like a=-2 & b=5 then a%b = 3

Unthankful