AntInLoop

Fast Exponentiation (Binary Exponentiation) Code Implementations

Complete Fast Exponentiation (Binary Exponentiation) code implementations in C++, Python, Java, and JavaScript with time and space complexity analysis on AntInLoop.

Read Fast Exponentiation (Binary Exponentiation) Guide ยท Launch Interactive Visualizer

C++ Implementation

// Fast Exponentiation in C++

class FastExponentiation {
public:
    // Iterative
    static long long fastPowIterative(long long base, long long exponent) {
        long long result = 1;
        while (exponent > 0) {
            if (exponent % 2 == 1) {
                result *= base;
            }
            base *= base;
            exponent /= 2;
        }
        return result;
    }

    // Recursive
    static long long fastPowRecursive(long long base, long long exponent) {
        if (exponent == 0) return 1;
        if (exponent % 2 == 0) {
            long long half = fastPowRecursive(base, exponent / 2);
            return half * half;
        } else {
            return base * fastPowRecursive(base, exponent - 1);
        }
    }
};

JAVA Implementation

// Fast Exponentiation in Java

public class FastExponentiation {

    // Iterative
    public static long fastPowIterative(long base, long exponent) {
        long result = 1;
        while (exponent > 0) {
            if ((exponent & 1) == 1) {
                result *= base;
            }
            base *= base;
            exponent >>= 1;
        }
        return result;
    }

    // Recursive
    public static long fastPowRecursive(long base, long exponent) {
        if (exponent == 0) return 1;
        if (exponent % 2 == 0) {
            long half = fastPowRecursive(base, exponent / 2);
            return half * half;
        } else {
            return base * fastPowRecursive(base, exponent - 1);
        }
    }
}

JAVASCRIPT Implementation

// Fast Exponentiation (Exponentiation by Squaring) in JavaScript

// Iterative
function fastPowIterative(base, exponent) {
  let result = 1;
  while (exponent > 0) {
    if (exponent % 2 === 1) result *= base;
    base *= base;
    exponent = Math.floor(exponent / 2);
  }
  return result;
}

// Recursive
function fastPowRecursive(base, exponent) {
  if (exponent === 0) return 1;
  if (exponent % 2 === 0) {
    const half = fastPowRecursive(base, exponent / 2);
    return half * half;
  } else {
    return base * fastPowRecursive(base, exponent - 1);
  }
}

PYTHON Implementation

# Fast Exponentiation (Exponentiation by Squaring) in Python

# Iterative
def fast_pow_iterative(base, exponent):
    result = 1
    while exponent > 0:
        if exponent % 2 == 1:
            result *= base
        base *= base
        exponent //= 2
    return result

# Recursive
def fast_pow_recursive(base, exponent):
    if exponent == 0:
        return 1
    elif exponent % 2 == 0:
        half = fast_pow_recursive(base, exponent // 2)
        return half * half
    else:
        return base * fast_pow_recursive(base, exponent - 1)