How to find modulo of a sum of numbers?

Question

I am seeking for a way to find modulo of a sequence of numbers like: (a1 + a2 + a3 + a4 + ... + an) mod x

Is there any way/property of modulo function so that I can compute mod of this sequence from the individual mods of numbers in sequence.

Solution 1

As I can recall. you can:

(a1 mod x + a2 mod x + a3 mod x + ... + an mod x) mod x

Such equation will benefit one purpose. if the sum of the numbers exceeds the capacity of the variable used for summation. ex. 32 bit int.

This way it is most probably the sum of modulars will fit in the used var for summation. depending on x value and sequence length.

Sample Code

int sum = 0;
for (int i=0;i<n;i++)
   sum += a[i] % x;
int mod = sum % x;

Better Approach (not very sure)

int sum = 0;
for (int i=0;i<n;i++) {
   sum += a[i] % x;
   sum %= x;
}
int mod = sum;

Solution 2

Mod operator is distributive;

( x + y ) % z

... is equivalent to:

( x % z + y % z ) % z

Solution 3

As the purpose of doing this is usually to avoid overflows, the below might still overflow as we are summing all mod values.

Wrong approach if we want to avoid overflows :

(a1 mod x + a2 mod x + a3 mod x + ... + an mod x) mod x

We need to mod after each and every sum.

Assuming ai < x,

((((a1 + a2) mod x) + a3) mod x) + a4) mod x ....

should avoid the overflows.

Comments

[Oliver Charlesworth]

You know that (a + b) % x == ((a%x) + (b%x)) % x, right?

[Thariq Nugrohotomo]

I have the exact same question. Have you found your answer?