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

Exponent_By_Squaring


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



Copyright (c) 2019-2021, Algotree.org.
All rights reserved.