Sum and multiplication modulo

Question

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 except 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;
  }

So, if `P` is about `2^100`, what datatype do you use for storing it? — ypercubeᵀᴹ, May 15 '11 at 14:22
The SUM is about 2^100. But if I count % P after each multiplication, it's about 2^16. — Ximik, May 15 '11 at 14:28
So, you mean that `P` is less than `2^16` ? Then you could use 32-bit integers for all your arithmetic functions. — ypercubeᵀᴹ, May 15 '11 at 14:31
The problem is the SUM is too big. So I have to count % P after each multiplication and this makes program very slow. — Ximik, May 15 '11 at 14:34
You have to do `% P` after each multiplication and after every addiition, correct. But I doubt this is slow. Please post the whole code you have by editing your question (add it in the end), so others can see and comment. Perhaps there are other issues that it is slow. — ypercubeᵀᴹ, May 15 '11 at 14:35

score 8 · Answer 1 · answered May 15 '11 at 12:26

8

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.

answered May 15 '11 at 12:26

sleeplessnerd

21,853
1
25
29

No, i can't, because of limits in data types. – Ximik May 15 '11 at 13:48

score 6 · Answer 2 · edited May 23 '17 at 10:34

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.

Yes, there are a lot of examples with mod 2^N, but I can't found any for another P. This is the problem. — Ximik, May 15 '11 at 14:09
Seems like this library can't help. Because it would be ever more slow then current solution. — Ximik, May 15 '11 at 15:25

score 1 · Accepted Answer · answered May 15 '11 at 20:21

1

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.

answered May 15 '11 at 20:21

starblue

55,348
14
97
151

I don't see how it solves the OP's problem. K doesn't exceed 2^16. What could we possibly gain by factoring K into K1,...,Kn? – ciamej Feb 18 '14 at 22:29
That's true, I probably missed the comment where he states that limit. For `2^100` it would be useful, but not for `2^16`. – starblue Feb 22 '14 at 09:29

Sum and multiplication modulo

3 Answers3

Linked