Fast Exponentiation Algorithm

Fast Exponentiation Algorithm

The Fast Exponentiation Algorithm is an efficient method for calculating large powers. When we need to compute a to the power of n (a^n), the most straightforward approach is to perform n-1 multiplications, resulting in a time complexity of O(n). However, when the exponent n is very large (for example, in cryptography or big number calculations, n can be a number with hundreds of digits), this linear-time method becomes impractical. The Fast Exponentiation Algorithm reduces the time complexity to O(log n) by decomposing the exponent n into its binary representation.

Core Idea

The core idea of the Fast Exponentiation Algorithm is "divide and conquer" and "doubling." It leverages a fundamental property of exponentiation: a^(m+n) = a^m * a^n. More importantly, it transforms the computation into a series of squaring operations by representing the exponent n in binary form. For example, a^13 can be expressed as a^(1101)₂, i.e., a^(8+4+1) = a^8 * a^4 * a^1.

Detailed Step-by-Step Explanation

Let's understand the Fast Exponentiation Algorithm step by step by calculating 3 to the power of 13 (3^13). The binary representation of 13 is 1101.

Step 1: Initialize Variables
We need to initialize three key variables:

  • base: Initially set to our base number a. During the computation, base will be continuously squared, representing a^(2^k), where k is the bit position of the current binary digit.
  • exponent: This is n, which we will treat as a binary number. During iteration, we will repeatedly right-shift it (divide by 2) to examine each of its bits.
  • result: Initially set to 1. Ultimately, it will contain our final answer.

For 3^13:

  • base = 3
  • exponent = 13 (binary 1101)
  • result = 1

Step 2: Process Each Bit of the Exponent in a Loop
As long as the exponent is greater than 0, we continue the loop. In each iteration, we do two things:

  1. Check the current Least Significant Bit (LSB): We check if the current LSB of the exponent exponent is 1. This can be done by checking (exponent % 2) == 1 or using the bitwise operation (exponent & 1) == 1.

    • If the LSB is 1: This means the current binary digit contributes to the final result. Therefore, we multiply the current base into the result.
    • If the LSB is 0: We skip and do not perform the multiplication.

  2. Update the base and right-shift the exponent:

    • Update the base (base): Square the base (base = base * base). This essentially prepares for processing the next higher-order binary digit. Since the weight of the next digit is twice the current one, the corresponding power should be the square of the current value (e.g., changing from a^2 to a^4).
    • Right-shift the exponent (exponent): Shift exponent one bit to the right (equivalent to integer division by 2), i.e., exponent = exponent // 2 or using the bitwise operation exponent = exponent >> 1. This removes the already processed LSB, allowing us to start processing the next bit.

Step 3: Step-by-Step Calculation of 3^13

Let's trace the loop step by step:

  • Iteration 1:

    • Current exponent = 13 (binary 1101). The LSB is 1.
    • Operation 1 (Check LSB): Because the LSB is 1, multiply the current base (3) into result. result = 1 * 3 = 3.
    • Operation 2 (Update):
      • Square base: base = 3 * 3 = 9 (now base represents 3^2).
      • Right-shift exponent: exponent = 13 // 2 = 6 (binary 110).

  • Iteration 2:

    • Current exponent = 6 (binary 110). The LSB is 0.
    • Operation 1 (Check LSB): Because the LSB is 0, result remains unchanged at 3.
    • Operation 2 (Update):
      • Square base: base = 9 * 9 = 81 (now base represents 3^4).
      • Right-shift exponent: exponent = 6 // 2 = 3 (binary 11).

  • Iteration 3:

    • Current exponent = 3 (binary 11). The LSB is 1.
    • Operation 1 (Check LSB): Because the LSB is 1, multiply the current base (81) into result. result = 3 * 81 = 243.
    • Operation 2 (Update):
      • Square base: base = 81 * 81 = 6561 (now base represents 3^8).
      • Right-shift exponent: exponent = 3 // 2 = 1 (binary 1).

  • Iteration 4:

    • Current exponent = 1 (binary 1). The LSB is 1.
    • Operation 1 (Check LSB): Because the LSB is 1, multiply the current base (6561) into result. result = 243 * 6561 = 1594323.
    • Operation 2 (Update):
      • Square base: base = 6561 * 6561 (we no longer need this value).
      • Right-shift exponent: exponent = 1 // 2 = 0.

  • Loop Ends: At this point, exponent is 0, and the loop terminates. The final result = 1594323.

We can verify: 3^13 indeed equals 1594323.

Algorithm Implementation (Python)

def fast_power(base, exponent):
    result = 1
    while exponent > 0:
        # If the current LSB is 1, multiply the current base into the result
        if exponent & 1:
            result *= base
        # Square the base (doubling)
        base *= base
        # Right-shift the exponent by one bit (process the next bit)
        exponent = exponent >> 1
    return result

# Example: Calculate 3^13
print(fast_power(3, 13)) # Output: 1594323

Summary

The essence of the Fast Exponentiation Algorithm lies in optimizing the number of multiplications from linear (O(n)) to logarithmic (O(log n)) through a binary approach. The key steps are:

  1. Initialize result=1, base=a, exponent=n.
  2. Loop until exponent becomes 0:
    • If the current LSB of exponent is 1, multiply result by the current base.
    • Square base.
    • Right-shift exponent by one bit.
  3. Return result.

This method is not only efficient but can also be easily extended to modular exponentiation (e.g., calculating (a^n) % mod), which is very common in competitions and interviews. Simply perform a modulo operation after each multiplication to prevent numerical overflow.