Menu
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;
}
303
In multiplication modulo the product of two element should be = OR < the Group order. In addition modulo the addition of elements should not exceed the Group order. This way the closure property is maintained. N.
Abstract. A sum sequence modulo n is a sequence S = (s1,s2,...,sd) of elements in Z/nZ such that every x ∈ Z/nZ can be represented as si + sj, i<j, in the same number λ of ways. For example, (0,1,2,4) is a sum sequence modulo 6 with λ = 1.
Most programming languages adopt the convention that the modulo operator (denoted by % rather than mod ) occupies the same place in the order of operations as multiplication and division. Hence, it comes AFTER the operations in parentheses, but BEFORE addition and subtraction.
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.
119
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
