patterncppMinor
Modular exponentiation in C++
Viewed 0 times
exponentiationmodularstackoverflow
Problem
I wrote the following code for a contest and worked fine for me. Could I make it a bit faster?
#include
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;
}Solution
The usual way is a little more complex, but a lot faster when the exponent is large. It looks something like this:
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:
Many people find it more readable to define one variable per definition:
... or at least use a separate line for each variable:
Naming
A function's name should reflect what it really does. Using
formatting
At least IMO, a little white space can help readability quite a bit. For one example, instead of:
...I'd rather see a space after each comma:
In addition, where there's flow control, the controlled statements should be indented, so this:
would come out like:
return from
When execution "flows" off the end of
Use of
I'd avoid using
Pulling in the entirety of
template
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 m) b %= m;
}
return r;
}
template
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
mainWhen 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
endlI'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.Code Snippets
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;
}int base,exponent,mod;int base;
int exponent;
int mod;int base,
exponent,
mod;int power(int base,int exponent,int mod)Context
StackExchange Code Review Q#155432, answer score: 7
Revisions (0)
No revisions yet.