Efficiently compute the modulo of the sum of two numbers

Question

I have three N-bit numbers, A, B, and C. I cannot easily calculate (A + B) % C but I can easily calculate A % C and B % C. If the modulo operation is unsigned and I know ahead of time that A + B does not wrap around N bits then I can instead calculate ((A % C) + (B % C)) % C. However, is it possible to do anything for the cases where the modulo operation is signed or the addition of A and B might lead to a wrap-around.

It looks like there might be some confusion as to why ((A % C) + (B % C)) % C cannot be relied upon to always work. Here is an unsigned example:

unsigned A = 0x1U;
unsigned B = 0xFFFFFFFFU;
unsigned C = 0x3U;
((A % C) + (B % C)) % C == 0x1U but (A + B) % C == 0x0U

Here is a signed example:

int A = 0x1;
int B = 0xE27F9803;
int C = 0x3U;
((A % C) + (B % C)) % C == 0x1U but (A + B) % C == -2

Answer 1

What you want is:

((a+b)%2^n)%c

Let

a+b = k 2^n + d

Where k = 0 or 1 and d < 2^n.

Plugging in you get:

 ((k 2^n + d) % 2^n) % c = (d % 2^n) % c = d % c

Taking the previous expression modulo c you get

 (a + b) % c = (k 2^n + d) % c => d % c = a % c + b % c - k 2^n % c

With n = 32, in C:

unsigned myMod(unsigned a, unsigned b, unsigned c)
{
     // k = 1 if the sum overflows
     unsigned k = ( a > UINT_MAX - b or b > UINT_MAX - a);

     return ( a % c + b % c -  k*(UINT_MAX%c + 1))%c;
}

myMod(0x1U,0xFFFFFFFFU,0x3U) == 0