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)

Exponent_By_Squaring_Image


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

Copyright © 2019-2020, Algotree.org.
All rights reserved.