# 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.

The idea is as follows,

• If the power is even, then the base would be multiplied with itself ( power / 2 ) times.
Example : 3 2 = ( 3 * 3 ) ( 2 / 2 ) = ( 3 * 3 ) 1 = 9
• If the power is odd ( and greater than 1 ) then the base would be used in the multiplication with the result once
and then it would be multipled with itself ( power - 1 ) times.
Example : 3 3 = 3 . ( 3 ) 2 = 3 . ( 3 * 3 ) ( 2 / 2 ) = 3 . ( 3 * 3 ) 1 = 27

Algorithm : Fast Exponentiation ( base, power )

0.   Initialize result = 1
1.    While ( power > 0 ) do
2.       If power is odd then,
result = result * power
3.       base = base * base
4.       power = power / 2
5.    return result

Consider the example of finding 2 5

Step Base Power Operation Result
0 2 5 Initialize result to 1 result = 1
1 2 5 (odd) result = result * base
result = 1 * 2 = 2
base = base * base = 4
power = power / 2 = 2
result = 2
2 4 2 (even) base = base * base = 16
power = power / 2 = 1
result = 2
3 16 1 (odd) result = result * base
result = 2 * 16 = 32
base = base * base = 256
power = power / 2 = 0
result = 32

Now the power is less than 1, hence the algorithm terminates.

Time complexity : log ( n )

Fast exponentiation implementation

``````def RecExpo ( base, power ) :
result = 0
if ( power == 1 ) :
return base
elif ( 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 the power is odd
return base * RecExpo ( base , power - 1 )

def FastExpo ( base , power ) :
result = 1
while ( power > 0 ) :
if ( power % 2 == 1 ) :
result = result * base

base *= base
power //= 2

return result

def Bitwise_FastExpo ( base , power ) :
result = 1
while ( power > 0 ) :
if ( power & 1 == 1 ) :
result *= base
base *= base
power >>= 1

return result

def main() :
print ( "Base: 2, Power: 32 i.e (2^32) : " + str ( RecExpo ( 2 , 32 ) ) )
print ( "Base: 2, Power: 44 i.e (2^44) : " + str ( FastExpo ( 2 , 44 ) ) )
print ( "Base: 2, Power: 63 i.e (2^63) : " + str ( Bitwise_FastExpo ( 2 , 63 ) ) )

if __name__ == "__main__":
main()

``````

Output

``````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
``````
``````#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

``````
``````import java.util.*;

class Exponent {

public long RecExpo ( long base, long power) {

long 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 );
}
}

public long FastExpo ( long base, long power) {
long result = 1;
while ( power > 0 ) {
if ( power % 2 == 1 ) {
result *= base;
}
base *= base;
power /= 2;
}
return result;
}

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

public static void main (String[] args) {
Exponent e = new Exponent();
System.out.println("Base: 2, Power: 32 i.e (2^32) : " + e.RecExpo ( 2 , 32 ) );
System.out.println("Base: 2, Power: 44 i.e (2^44) : " + e.FastExpo ( 2 , 44 ) );
System.out.println("Base: 2, Power: 54 i.e (2^54) : " + e.Bitwise_FastExpo ( 2 , 54 ) );
}
}
``````

Output

``````Base: 2, Power: 32 i.e (2^32) : 4294967296
Base: 2, Power: 44 i.e (2^44) : 17592186044416
Base: 2, Power: 54 i.e (2^54) : 18014398509481984
``````