# Fast Exponentiation

Below is an algorithm for finding large integer powers(n) of a number(x). i.e x^n or x to the power of n.
It is based on the technique known as “Exponentiation by Squaring”.

Time complexity of finding large integer powers of a given number n : log(n) C++14 Fast Exponentiation

#include<iostream>

using namespace std;
typedef unsigned long long ULL;

ULL RecExpo (ULL base, ULL power) {

ULL result;

if (power == 1)
return base;
if (power == 2)
return base * base;

if (power % 2 == 0) { // When power is even and greater than 2
result = RecExpo(base, power/2);
return result * result;
} else { // When power is odd
return base * RecExpo(base, power-1);
}
}

ULL FastExpo (ULL base, ULL power) {
ULL result = 1;
while (power) {
if (power%2) {
result *= base;
}
base *= base;
power /= 2;
}
return result;
}

ULL Bitwise_FastExpo (ULL base, ULL power) {
ULL result = 1;
while (power) {
if (power&1) {
result *= base;
}
base *= base;
power >>= 1;
}
return result;
}

int main() {
cout << "Base: 2, Power: 32 i.e (2^32) : " << RecExpo(2,32) << endl;
cout << "Base: 2, Power: 44 i.e (2^44) : " << FastExpo(2,44) << endl;
cout << "Base: 2, Power: 63 i.e (2^63) : " << Bitwise_FastExpo(2,63) << endl; // Limitation of 64 bit machine
return 0;
}

Base: 2, Power: 32 i.e (2^32) : 4294967296
Base: 2, Power: 44 i.e (2^44) : 17592186044416
Base: 2, Power: 63 i.e (2^63) : 9223372036854775808