Given two integers a & n (a > 0 and n >= 0), Our task is to compute a

Basic and very straight forward solution can be implemented by multiplying a n number of times.

i.e: a

We can make use of the fact that every number N can be represented using at most (1 + log_{2}(N)) bits.

If n is odd then a^{n} = a * a^{(n/2)} * a^{(n/2)}

else a^{n} = a^{(n/2)} * a^{(n/2)}

Let's initialize our result to 1

Now while our n is greater than zero repeat:

if our n is odd then

multiply a in result and decrease n by 1

Note: At this point we must have even n

Now we should divide n by 2 and multiply a to itself

Note: As we know that (a^{2})^(n/2) == a^{n}

Now our result stores a^{n}and we return it

using namespace std;

template<typename T>

T power(T a, T n) {

T res = 1;

while (n > 0) {

if (n & 1) {

res *= a;

/* we can skip decrement of n by 1

because in next step we will divide n

by 2 and it will produce the same result

*/

}

n >>= 1;

// Here division by 2 is done by bitwise right shift

a *= a;

}

return res;

}

int main() {

int a = 6, n = 4;

cout << a << '^' << n << " = " << power(a, n) << '\n';

long long p = 12, q = 15;

cout << p << '^' << q << " = " << power(p, q) << '\n';

return 0;

}

## Comments