Exponents in C (n^m)

Question

http://z-trening.com/tasks.php?show_task=5000000069&lang=uk

#include <stdio.h>

int main(void)
{
    long long o, s, m, i; 
    long long rez = 1;

    scanf("%lld %lld %lld", &o, &s, &m);
    o = o % m;
    for (i = 0; i < s; i++){
        rez = (rez * o) % m;
    }
    printf("%lld", rez);
    return 0;
}

It works for 10 out of 20 tasks. Is there any faster way to raise o^s ?

Answer 1

Yes, there is a faster method: modular exponentiation. http://en.wikipedia.org/wiki/Modular_exponentiation

Repeated multiplication (your algorithm) runs in exponential time, while modular exponentiation runs in polynomial time. It works like this:

Let's say, you want to compute A^B mod M. First, write B in binary:

B = bn,bn-1,...,b1,b0

This means, that

B = bn * 2^n + bn-1 * 2^(n-1) + ... + b1 * 2 + b0

Substituting this in the expression A^B:

A^B = A^(2^n)^bn * A^(2^(n-1))^bn-1 * ... * A^2^b1 * A^b0

A^(2^n) can be computed recursively:

A^(2^n) = (A^(2^(n-1)))^2

Now, the trick is, to use this identity to compute A^(2^i) for each i using repeated squaring modulo M. The usual identities of multiplication and exponentiation hold for modular arithmetics too, so this is perfectly legal. The full algorithm:

input: A,B,M
output: A^B mod M

result = 1
while(B != 0){
    if(B is odd){
        result = result * A mod M
    }
    B = B / 2
    A = A * A mod M
}
return result

Answer 2

An easy way to reduce the number of calculations uses the equalities:

a^(b+c) = a^b*a^c     (1)

and

(x*y)%z = ((x%z)*(y%z))%z   (2)

These two equalities can be used quickly compute (o^1)%m, (o^2)%m, (o^4)%m, (o^8)%m, ...:

o2n = (on * on)%m

The problem can now be solved with a loop that iterates once for every bit in s, which means that the complexity has been reduced from O(s) to O(log(s).

long long s, o;
int m;

// Input s,o,m (code omitted)

int res = 1, on = o%m;  // Assuming int is at least 32 bits
for (i = 0; i < 35; i++) {  // 2^35 is larger than the largest s allowed.
  if (s & 1 << i) {
    res = res * on;
  }
  on = (on*on)%m;
}
printf("%d\n", res);