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














































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:

Comments