6
\$\begingroup\$

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;
}
\$\endgroup\$
  • 2
    \$\begingroup\$ Depending on modulus and available integer sizes, "exponentiation by squaring" should be worth a try. \$\endgroup\$ – greybeard Feb 15 '17 at 14:30
  • 1
    \$\begingroup\$ en.wikipedia.org/wiki/Modular_exponentiation The right to left binary method? \$\endgroup\$ – hamster on wheels Feb 15 '17 at 18:47
  • \$\begingroup\$ I would suggest binary exponation for higher performance. My problem is, I don't know if there is a function in c++ what converts a number to it's binary representation as a string, like bin() does it in python. \$\endgroup\$ – Aemyl Feb 16 '17 at 12:24
7
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ For what it's worth, I used this modular exponentiation to implement RSA in a post on SO. That implementation is still a toy (doesn't support large enough numbers for security) but courtesy of templates, the code above can be used with a large integer type that overloads operators appropriately. \$\endgroup\$ – Jerry Coffin Feb 16 '17 at 1:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.