Fast Exponentiation Power in Log N in DSA Python

Mental Model

To find a number raised to a power quickly by breaking the problem into smaller parts and reusing results.

Analogy: Like folding a paper in half repeatedly to reach a big thickness quickly instead of stacking sheets one by one.

power(n, e)
  ├─ if e is 0 -> return 1
  ├─ else split e into half
  ├─ compute power(n, e//2)
  └─ combine results by squaring or multiplying by n if e is odd

Dry Run Walkthrough

Input: Calculate 3^5 using fast exponentiation

Goal: Compute 3 raised to the power 5 efficiently using repeated squaring

Step 1: Calculate power(3, 5), split exponent 5 into half 2

power(3,5) calls power(3,2)

Why: We break down the problem to smaller powers to reuse calculations

Step 2: Calculate power(3, 2), split exponent 2 into half 1

power(3,2) calls power(3,1)

Why: Keep splitting exponent until base case

Step 3: Calculate power(3, 1), split exponent 1 into half 0

power(3,1) calls power(3,0)

Why: Base case is when exponent is zero

Step 4: power(3, 0) returns 1 (base case)

return 1

Why: Any number to power 0 is 1

Step 5: power(3, 1) computes half_power=1, exponent odd so multiply by base: 1 * 1 * 3 = 3

return 3

Why: For odd exponent, multiply half power squared by base

Step 6: power(3, 2) computes half_power=3, exponent even so square: 3 * 3 = 9

return 9

Why: For even exponent, square the half power

Step 7: power(3, 5) computes half_power=9, exponent odd so multiply by base: 9 * 9 * 3 = 243

return 243

Why: Combine results for odd exponent

Result:

3^5 = 243

Annotated Code

DSA Python

class FastExponentiation:
    def power(self, base: int, exponent: int) -> int:
        if exponent == 0:
            return 1  # base case: any number^0 = 1
        half_power = self.power(base, exponent // 2)  # recursive call for half exponent
        if exponent % 2 == 0:
            return half_power * half_power  # even exponent: square the half power
        else:
            return half_power * half_power * base  # odd exponent: multiply by base once more

# Driver code
fe = FastExponentiation()
result = fe.power(3, 5)
print(result)

if exponent == 0:

check base case to stop recursion

half_power = self.power(base, exponent // 2)

recursive call to compute power for half the exponent

if exponent % 2 == 0:

check if exponent is even to decide how to combine results

return half_power * half_power

square half power for even exponent

return half_power * half_power * base

multiply by base once more for odd exponent

Output

243

Complexity Analysis

Time: O(log n) because the exponent is divided by 2 each recursive call, reducing the problem size quickly

Space: O(log n) due to recursion call stack depth proportional to log of exponent

vs Alternative: Naive approach takes O(n) time by multiplying base n times, which is slower than this logarithmic method

Edge Cases

exponent is 0

returns 1 immediately as per definition

DSA Python

if exponent == 0:

exponent is 1

returns base itself after one recursive call

DSA Python

if exponent == 0:

large exponent

efficiently computes power without timeout due to logarithmic steps

DSA Python

half_power = self.power(base, exponent // 2)

When to Use This Pattern

When you need to compute large powers quickly, look for fast exponentiation using repeated squaring to reduce time from linear to logarithmic.

Common Mistakes

Mistake: Multiplying base by itself exponent times directly causing slow performance
Fix: Use recursive halving of exponent and combine results by squaring to achieve logarithmic time

Mistake: Not handling odd exponents correctly by missing the extra multiplication by base
Fix: Check if exponent is odd and multiply the squared half power by base once more

Summary

Computes base raised to exponent quickly using repeated squaring.

Use when you need fast power calculation especially for large exponents.

Split exponent in half recursively and combine results by squaring to save time.

Practice

1. What is the main advantage of using Fast Exponentiation to calculate a^b compared to the simple repeated multiplication?

easy

A. It works only for positive integers

B. It uses less memory than repeated multiplication

C. It reduces the time complexity from O(b) to O(log b)

D. It avoids using multiplication altogether

Solution

1. Step 1: Understand repeated multiplication complexity

   Calculating a^b by multiplying a by itself b times takes O(b) steps.

2. Step 2: Analyze fast exponentiation approach

   Fast exponentiation uses the idea of squaring and halving the exponent, reducing steps to O(log b).

3. Final Answer:

   It reduces the time complexity from O(b) to O(log b) -> Option C

4. Quick Check:

   Fast exponentiation = O(log b) [OK]

Hint: Remember: halve exponent each step for log speed [OK]

Common Mistakes:

• Thinking it avoids multiplication
• Confusing memory use with speed
• Assuming it only works for positive exponents

2. Which of the following is the correct base case for a recursive fast exponentiation function power(a, b) that calculates a^b?

easy

A. if b == 0: return 1

B. if a == 0: return 0

C. if b == 1: return 0

D. if a == 1: return b

Solution

1. Step 1: Recall mathematical rule for exponent zero

   Any number to the power 0 equals 1, so power(a, 0) should return 1.

2. Step 2: Check options for correct base case

   if b == 0: return 1 matches this rule: if b == 0: return 1.

3. Final Answer:

   if b == 0: return 1 -> Option A

4. Quick Check:

   Base case b=0 returns 1 [OK]

Hint: Base case: exponent zero returns 1 [OK]

Common Mistakes:

• Returning 0 when exponent is 1
• Confusing base and exponent in conditions
• Returning b instead of 1 for base case

3. What is the output of the following Python code?

def fast_power(a, b):
    if b == 0:
        return 1
    half = fast_power(a, b // 2)
    if b % 2 == 0:
        return half * half
    else:
        return half * half * a

print(fast_power(2, 5))

medium

A. 32

B. 10

C. 25

D. 16

Solution

1. Step 1: Trace recursive calls for fast_power(2, 5)

   fast_power(2,5) calls fast_power(2,2), which calls fast_power(2,1), then fast_power(2,0) returns 1.

2. Step 2: Calculate values bottom-up

   fast_power(2,1) = 1*1*2 = 2
   fast_power(2,2) = 2*2 = 4
   fast_power(2,5) = 4*4*2 = 32

3. Final Answer:

   32 -> Option A

4. Quick Check:

   2^5 = 32 [OK]

Hint: Remember: odd exponent multiplies extra base [OK]

Common Mistakes:

• Confusing multiplication order
• Forgetting to multiply by base when exponent is odd
• Incorrect base case handling

4. The following code attempts to implement fast exponentiation but has a bug. What is the bug?

def fast_power(a, b):
    if b == 0:
        return 1
    half = fast_power(a, b // 2)
    if b % 2 == 1:
        return half * half
    else:
        return half * half * a

print(fast_power(3, 3))

medium

A. Function does not handle negative exponents

B. Base case should return 0 instead of 1

C. Multiplication order is incorrect

D. The condition for odd exponent is reversed

Solution

1. Step 1: Analyze the condition for odd exponent

   The code checks if b % 2 == 1 but returns half * half which is for even exponent.

2. Step 2: Identify correct logic for odd exponent

   For odd exponent, it should return half * half * a. The conditions are swapped.

3. Final Answer:

   The condition for odd exponent is reversed -> Option D

4. Quick Check:

   Odd exponent must multiply extra base [OK]

Hint: Odd exponent means multiply extra base factor [OK]

Common Mistakes:

• Swapping odd/even conditions
• Wrong base case return value
• Ignoring negative exponent cases

5. You want to compute 3^1000 mod 1000000007 efficiently using fast exponentiation. Which of the following modifications is necessary to the standard fast exponentiation algorithm to handle this?

hard

A. Convert exponent to binary string before calculation

B. Add modulo operation after each multiplication to keep numbers small

C. Increase recursion depth limit to handle large exponent

D. Use floating point arithmetic to handle large numbers

Solution

1. Step 1: Understand the problem with large powers

   Calculating 3^1000 directly results in a huge number that can cause overflow or slow computation.

2. Step 2: Apply modulo at each multiplication step

   To keep numbers manageable and get correct modulo result, apply modulo after every multiplication.

3. Final Answer:

   Add modulo operation after each multiplication to keep numbers small -> Option B

4. Quick Check:

   Modulo after multiplication keeps numbers small [OK]

Hint: Apply modulo after every multiplication step [OK]

Common Mistakes:

• Using floating point causing precision errors
• Not applying modulo inside recursion
• Trying to convert exponent to string unnecessarily