binary exponent Algorithm

The binary exponentiation algorithm, also known as exponentiation by squaring, is an efficient method for computing large powers of a number, particularly in modular arithmetic. This algorithm takes advantage of the binary representation of the exponent to reduce the number of multiplications required to compute a power, significantly improving the speed of the operation compared to the naive method of repeated multiplication. The algorithm is widely used in various applications, such as cryptography, computer graphics, and scientific simulations, where fast and efficient exponentiation is crucial. The core idea behind the binary exponentiation algorithm is to represent the exponent as a sequence of binary digits and use this representation to iteratively compute the result. The algorithm starts by initializing the result to 1 and then iteratively goes through each bit in the binary representation of the exponent, from the least significant bit to the most significant bit. If the current bit is 1, the current result is multiplied by the current base raised to the power of the current bit position. After each iteration, the base is squared and the algorithm proceeds to the next bit. This way, only the necessary multiplications are performed, which greatly reduces the overall computation time. In the case of modular exponentiation, the intermediate results are reduced modulo a given number at each step, which helps to keep the numbers small and manageable.
/// C++ Program to find Binary Exponent Iteratively and Recursively.

#include<iostream>
/*
 * Calculate a^b in O(log(b)) by converting b to a binary number.
 * Binary exponentiation is also known as exponentiation by squaring.
 * NOTE : This is a far better approach compared to naive method which provide O(b) operations.
 * Example:
 * 10 in base 2 is 1010.
 * 2^10 = 2^(1010) = 2^8 * 2^2
 * 2^1 = 2
 * 2^2 = (2^1)^2 = 2^2 = 4
 * 2^4 = (2^2)^2 = 4^2 = 16
 * 2^8 = (2^4)^2 = 16^2 = 256
 * Hence to calculate 2^10 we only need to multiply 2^8 and 2^2 skipping 2^1 and 2^4.
*/

/// Recursive function to calculate exponent in O(log(n)) using binary exponent.
int binExpo(int a, int b) {
    if (b == 0) {
        return 1;
    }
    int res = binExpo(a, b/2);
    if (b%2) {
        return res*res*a;
    } else {
        return res*res;
    }
}

/// Iterative function to calculate exponent in O(log(n)) using binary exponent.
int binExpo_alt(int a, int b) {
    int res = 1;
    while (b > 0) {
        if (b%2) {
            res = res*a;
        }
        a = a*a;
        b /= 2;
    }
    return res;
}

int main() {
    int a, b;
    /// Give two numbers a, b
    std::cin >> a >> b;
    if (a == 0 && b == 0) {
        std::cout << "Math error" << std::endl;
    } else if (b < 0) {
        std::cout << "Exponent must be positive !!" << std::endl;
    } else {
        int resRecurse = binExpo(a, b);
        /// int resIterate = binExpo_alt(a, b);

        /// Result of a^b (where '^' denotes exponentiation)
        std::cout << resRecurse << std::endl;
        /// std::cout << resIterate << std::endl;
    }
}

LANGUAGE:

DARK MODE: