L5. Power Exponentiation | Maths Playlist

1. Overview and Problem Statement

When studying algorithms in computer science, calculating powers ($x^n$) efficiently is a foundational operation. Given two numbers, a base $X$ and an exponent $N$, our goal is to compute $X^N$ and return the result.

Initially, let us assume both $X$ and $N$ are positive integers. Later, we will expand our algorithm to handle edge cases such as negative exponents and floating-rector ($double$) base values.

Inputs:  X = 2, N = 5
Process: 2 * 2 * 2 * 2 * 2
Output:  32

2. Why Do We Need This? (The Naive Approach)

The most intuitive, brute-force way to calculate $X^N$ is to use a loop that multiplies $X$ by itself $N$ times.

# Naive Linear Power Calculation
answer = 1
for i in range(1, n + 1):
    answer = answer * X

Limitations of the Naive Approach

• Time Complexity: $\mathcal{O}(N)$ because the loop runs exactly $N$ times.
• Performance Bottleneck: If $N$ is a very large integer (e.g., $10^9$), an $\mathcal{O}(N)$ approach will result in a Time Limit Exceeded (TLE) error in competitive programming and inefficient execution in production systems. We need a logarithmic approach.

3. Core Mental Model: Binary Exponentiation (Exponentiation by Squaring)

Instead of multiplying $X$ one by one, we can drastically reduce the number of multiplications by leveraging properties of exponents. We halve the exponent at each step by squaring the base.

Real-Life Analogy

Imagine you need to take 21 steps forward. Walking one step at a time takes 21 individual movements ($\mathcal{O}(N)$). However, if you can instantly jump forward in massive exponential bounds—doubling your stride length whenever your remaining distance is even, and taking a single step only when your distance is odd—you reach the destination in just a handful of jumps ($\mathcal{O}(\log N)$).

4. Step-by-Step Evolution: Manual Trace with $X = 2, N = 21$

Let us trace how Binary Exponentiation calculates $2^{21}$ step-by-step.

1. Initial State: answer = 1, X = 2, N = 21
2. $N$ is Odd (21):
   • Extract one $2$ from the exponent and multiply it into our answer: answer = 1 * 2 = 2
   • Reduce $N$ by 1: N becomes 20.
3. $N$ is Even (20):
   • Rewrite $2^{20}$ as $(2^2)^{10} = 4^{10}$.
   • Square the base: X = 4
   • Halve the exponent: N = 10
4. $N$ is Even (10):
   • Rewrite $4^{10}$ as $(4^2)^5 = 16^5$.
   • Square the base: X = 16
   • Halve the exponent: N = 5
5. $N$ is Odd (5):
   • Extract one $16$ and multiply it into our answer: answer = 2 * 16 = 32
   • Reduce $N$ by 1: N becomes 4.
6. $N$ is Even (4):
   • Rewrite $16^4$ as $(16^2)^2 = 256^2$.
   • Square the base: X = 256
   • Halve the exponent: N = 2
7. $N$ is Even (2):
   • Rewrite $256^2$ as $(256^2)^1 = 65536^1$.
   • Square the base: X = 65536
   • Halve the exponent: N = 1
8. $N$ is Odd (1):
   • Extract one $65536$ and multiply it into the running answer: answer = 32 * 65536 = 2,097,152
   • Reduce $N$ by 1: N becomes 0.
9. Termination: $N = 0$, loop ends. Return final computed answer.

5. Another Example Walkthrough: $X = 3, N = 9$

Let us run through another quick example to cement the pattern.

• Initial: answer = 1, X = 3, N = 9
• $N = 9$ (Odd): Extract $3 \rightarrow$ answer = 3, N = 8
• $N = 8$ (Even): Square base ($3^2 = 9$), halve exponent ($8 / 2 = 4$) $\rightarrow$ X = 9, N = 4
• $N = 4$ (Even): Square base ($9^2 = 81$), halve exponent ($4 / 2 = 2$) $\rightarrow$ X = 81, N = 2
• $N = 2$ (Even): Square base ($81^2 = 6561$), halve exponent ($2 / 2 = 1$) $\rightarrow$ X = 6561, N = 1
• $N = 1$ (Odd): Extract $6561 \rightarrow$ answer = 3 * 6561 = 19683, N = 0
• Termination: $N = 0$, return 19683.

6. Algorithm Design & Pseudo Code

The core rules governing our loop are:

• If $N$ is odd: Multiply answer by X, then decrement $N$ by 1 to make it even.
• If $N$ is even: Square the base (X = X * X) and divide $N$ by 2 (N = N / 2).

def power(x, n):
    answer = 1
    # Store original n for negative exponent handling
    m = n 
    if m < 0:
        m = -m  # Make positive for loop iteration
        
    while m > 0:
        if m % 2 == 1:  # Odd power
            answer = answer * x
            m = m - 1
        else:           # Even power
            x = x * x
            m = m // 2
            
    if n < 0:
        return 1.0 / answer
    return answer

7. Handling Edge Cases: Negative Exponents and Doubles

Real-world problems contain messy inputs. We must account for negative exponents and floating-point base values.

A. Negative Exponents

If $N$ is negative (e.g., $5^{-2}$), it is mathematically equivalent to $\frac{1}{5^2} = \frac{1}{25}$.

• Strategy: Keep track of whether the initial exponent was negative. Compute the absolute value of $N$ for the main calculation loop, and at the end, if the original exponent was negative, return 1 / answer.

B. Floating-Point Bases ($Double$)

If $X$ is a floating-point number (e.g., $2.5$), ensure that your answer variable and base variable are declared as floating-point types (or double in C++/Java/JavaScript) to prevent integer truncation during division (1.0 / answer).

8. Complexity Analysis

Summary and Key Takeaways

• Exponential Growth / Reduction: Binary exponentiation transforms linear exponent calculation into a logarithmic process ($\mathcal{O}(\log N)$).
• The Squaring Trick: When the exponent is even, square the base and halve the exponent: $X^N = (X^2)^{N/2}$.
• Handling Odd Exponents: When the exponent is odd, peel off a single factor of $X$ into the running answer to make the exponent even.
• Space Efficiency: The algorithm runs in constant auxiliary space ($\mathcal{O}(1)$) by mutating variables in place without recursive stack overhead.
• Negative Exponents: Handle negative powers by running the positive exponent algorithm and taking the reciprocal (1 / answer) at the end.
• Data Types: Use floating-point (double) variables for bases and results to safely handle fractional inputs.