Modular exponentiation in C++

Question

I wrote the following code for a contest and worked fine for me. Could I make it a bit faster?

#include<iostream>
using namespace std;

int power(int,int,int);

int main(int argc,char** argv){
    int base,exponent,mod;
    cin>>base>>exponent>>mod;
    cout<<power(base,exponent,mod)<<endl;
    return 0;
}

int power(int base,int exponent,int mod){
    if(mod==1)return 0;
    int ans=1;
    for(int i=0;i<exponent;i++){
        ans=(ans*base)%mod;
    }
    return ans;
}

Answer 1

The usual way is a little more complex, but a lot faster when the exponent is large. It looks something like this:

template <class T>
T mul_mod(T a, T b, T m) { 
    if (m == 0) return a * b;

    T r = T();

    while (a > 0) {
        if (a & 1)
            if ((r += b) > m) r %= m;
        a >>= 1;
        if ((b <<= 1) > m) b %= m;
    }
    return r;
}

template <class T>
T pow_mod(T a, T n, T m) {
    T r = 1;

    while (n > 0) {
        if (n & 1)
            r = mul_mod(r, a, m);
        a = mul_mod(a, a, m);
        n >>= 1;
    }
    return r;
}

pow_mod right-shifts n (the exponent) each iteration through the loop, so the number of iterations is proportional to the number of bits in the number (where yours in the question is proportional to the exponent itself). In other words, yours is linear on the exponent's magnitude, and this is roughly logarithmic exponent's magnitude.

Actual code review

Since this is CodeReview, not (for example) Stack Overflow, let's also take a look at reviewing your code.

Variable Definitions

You've defined multiple variables in a single definition:

int base,exponent,mod;

Many people find it more readable to define one variable per definition:

int base;
int exponent;
int mod;

... or at least use a separate line for each variable:

int base,
    exponent,
    mod;

Naming

A function's name should reflect what it really does. Using power for modular exponentiation borders on misleading. I'd rather the name included modular or at least mod.

formatting

At least IMO, a little white space can help readability quite a bit. For one example, instead of:

int power(int base,int exponent,int mod)

...I'd rather see a space after each comma:

int power(int base, int exponent, int mod)

In addition, where there's flow control, the controlled statements should be indented, so this:

if(mod==1)return 0;

would come out like:

 if (mod==1)
     return 0;

return from main

When execution "flows" off the end of main, there's an implicit return 0;, so you can eliminate that line from your code (though some prefer to keep it).

Use of endl

I'd avoid using std::endl (ever). Most of the time you really just want to write out a new-line, in which case \n is entirely adequate. On the (relatively rare) occasion that you really also want to flush the stream as endl also does, you should do so explicitly.

using namespace std;

Pulling in the entirety of namespace std; like this is generally frowned upon. It's all right for other (more sensibly designed) namespaces, but std defines a huge amount of "stuff", most of which you really don't want directly visible.