FANDOM


Modular Exponentiation can be user to speed up large exponents a^b from naive O(b) to O(log b) by calculating: (a*a)^(b/2) whenever b is even and (a).(a^(b-1)) whenever b is odd.

Algorithm Edit

Here is the C++ Code:

#include <bits/stdc++.h>
using namespace std;

long long power(int x, int y) {     // calculates power with complexity O(log y)     int res=1;     while(y>0)     {         if(y&1) // if last bit is 1 then y is odd 

          res=res*x;

        y=y>>1; // divide by 2         x=x*x;     }     return res;

}

int modpower(int x,int y,int p) {    // this function calculates power of a number with complexity O(log(y))     int res=1;     x=x%p;     while(y>0)     {         if(y&1)             res=(res*x)%p;         y=y>>1;         x=(x*x)%p;     }     return res;

}

int main() {

   cout << power(3,4)<<endl;

    cout << modpower(2,5,13);

   return 0;

}

Ad blocker interference detected!


Wikia is a free-to-use site that makes money from advertising. We have a modified experience for viewers using ad blockers

Wikia is not accessible if you’ve made further modifications. Remove the custom ad blocker rule(s) and the page will load as expected.