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_Image

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 of finding large integer powers of a given number n : log(n)



Java

Java Program for finding fast exponentiation

Python

Python Program for finding fast exponentiation

C++ Program for finding 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
Copyright (c) 2019-2021, Algotree.org.
All rights reserved.