Sum and multiplication modulo

I have big numbers K, C[1], C[2], C[3] etc. and I have to calculate b:

b = C[1]*C[2]+C[3]*C[4]+... (mod K)

Now I calculate the full sum and then make something like

b = SUM % K.

But this is not work when SUM becomes bigger then unsigned long limit, so I have to use something like

b = (C[1]*C[2] %K + C[3]*C[4] %K ) %K

But this is time-consuming. I've tried to use unsigned long long exc开发者_Go百科ept unsigned long and this is time-consuming too. Is there any better way?

UPD:

  C = (unsigned long long int *) malloc(N*sizeof(unsigned long long int));
  unsigned long int i, j, l;
  C[0] = 1;
  for (i=1; i<=N; i++) {
    C[i] = 0;
    l = (unsigned long int) i/2;
    for (j=0; j<l; j++) {
      C[i] += C[j]*C[i-j-1];
      C[i] = C[i] % K;
    }
    C[i] = C[i]*2;
    C[i] = C[i] % K;
    if (i - l*2 == 1) {
      C[i] += C[l]*C[l];
    }
    C[i] = C[i] % K;
  }

---

modulo m arithmetic is a ring homomorphism.

say f(x) = x%P then

f(a+b) = f(a)+f(b) and also

f(a*b) = f(a)*f(b).

http://en.wikipedia.org/wiki/Modular_arithmetic

this means you can do a mod P after every step.

---

To calculate

b = ( C[1]*C[2]+C[3]*C[4]+... ) % P 

you can do instead:

b = ( ( (C[1] % P) * (C[2] % P) % P )
    + ( (C[3] % P) * (C[4] % P) % P )
    + ...
    ) % P

Since all operations will not have results bigger than (P-1)^2, I expect this to be faster if you keep all intermediate results in variables with types as small as possible.

---

If the number P is some special form, like a power of 2, then there are faster methods.

---

In this SO question: big-numbers-in-c, you'll find a reference to GNU Multiple Precision Arithmetic Library. If you are not allowed to use such a library I guess that best choice then is to implement (a subset of) such a library of your own.

You could store integers (bigger than 2^64) in arrays and define addition, mupltiplication, division and modulo functions for such numbers.

---

If you can factor K into pairwise relatively prime numbers K₁,...,K_n then you can do the computation for each K_i and combine the results into a result for K by using the Chinese remainder theorem. This is usually much faster, especially if the K_i fit into a machine word.