Modul sum and multiplication

Question

I have large 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 total amount and then do something like

 b = SUM % K. 

But this does not work when the SUM gets larger than the unsigned long limit, so I should use something like

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

But it is time consuming. I tried to use unsigned long long besides unsigned long, and this also takes a lot of time. Is there a 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[ij-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; } 

Answer 1

If you can point K to pairwise relatively prime numbers K ₁ , ..., K _n , then you can perform a calculation for each K _i and combine the results into a result for K using the Chinese remainder theorem . This is usually much faster, especially if K _{i is} inserted into the machine word.

Answer 2

modulo m arithmetic is a ring homomorphism.

say that 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 that you can do mod P after each step.

Answer 3

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 greater than (P-1)^2 , I expect this to be faster if you save all intermediate results in variables with types as little as possible.

---

If the number P is a special kind, such as degree 2, then there are faster methods.

---

In this SO question: big-numbers-in-c, you will find a link to the GNU Multipoint Arithmetic Library . If you are not allowed to use such a library, I suggest that the best choice is to implement (a subset) of such a library.

You can store integers (greater than 2 ^ 64) in arrays and define such functions of addition, multiplication, division and modulation for such numbers.