### C++ Program to find the power of a number in Logarithmic time

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

Simple Method:
Basic and very straight forward solution can be implemented by multiplying a n number of times.
i.e: an =[a*a*a*a....*a*a] a occurs n times

Efficient Method:
We can make use of the fact that every number N can be represented using at most (1 + log2(N)) bits.
If n is odd then  an = a * a(n/2) * a(n/2)
else  ana(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 (a2)^(n/2) ==  an`
`    Now our result stores an and we return it`

Note: Please be aware of overflow as power function grows very fast.

C++ Program:

#include<iostream>
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;
}

Output: