Algotree > Algorithms > Numeric > Fast Exponentiation

Fast Exponentiation

Exponent_By_Squaring Below is an algorithm for finding large integer powers(n) of a number(x). i.e x ⁿ 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² = ( 3 * 3 ) ^{( 2 / 2 )} = ( 3 * 3 ) ¹ = 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 . ( 3 * 3 ) ^{( 2 / 2 )} = 3 . ( 3 * 3 ) ¹ = 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 ⁵

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