Fast Exponentiation Power in Log N in DSA Python - Execution Trace

Concept Flow - Fast Exponentiation Power in Log N

Start with base and exponent

↓

Is exponent 0?

Yes→Return 1

No↓

Is exponent even?

Yes→Square half power

↓

Compute half power recursively

↓

Multiply base with square of half power

↓

Return result

The flow checks if exponent is zero, then if even or odd, recursively computes half power, squares it, and multiplies by base if odd.

Execution Sample

DSA Python

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

Computes base raised to exp using recursion and squaring to reduce steps.

Execution Table

Step	Operation	Exponent (exp)	Recursive Call	Return Value	Explanation
1	Call fast_power(2, 10)	10	fast_power(2, 5)		Start with base=2, exp=10
2	Call fast_power(2, 5)	5	fast_power(2, 2)		exp=5 is odd, recurse with exp//2=2
3	Call fast_power(2, 2)	2	fast_power(2, 1)		exp=2 is even, recurse with exp//2=1
4	Call fast_power(2, 1)	1	fast_power(2, 0)		exp=1 is odd, recurse with exp//2=0
5	Call fast_power(2, 0)	0		1	Base case: exp=0 returns 1
6	Return from fast_power(2, 0)	0		1	Return 1 to caller with exp=1
7	Calculate for exp=1 (odd)	1		2	Return base * half * half = 2 * 1 * 1 = 2
8	Return from fast_power(2, 1)	1		2	Return 2 to caller with exp=2
9	Calculate for exp=2 (even)	2		4	Return half * half = 2 * 2 = 4
10	Return from fast_power(2, 2)	2		4	Return 4 to caller with exp=5
11	Calculate for exp=5 (odd)	5		32	Return base * half * half = 2 * 4 * 4 = 32
12	Return from fast_power(2, 5)	5		32	Return 32 to caller with exp=10
13	Calculate for exp=10 (even)	10		1024	Return half * half = 32 * 32 = 1024
14	Return from fast_power(2, 10)	10		1024	Final result 1024 returned
15	End				Exponentiation complete

💡 Recursion ends when exponent reaches 0, returning 1, then results combine back up.

Variable Tracker

Variable	Start	After Step 5	After Step 7	After Step 9	After Step 11	After Step 13	Final
exp	10	0	1	2	5	10	10
half	N/A	N/A	1	2	4	32	32
return_value	N/A	1	2	4	32	1024	1024

Key Moments - 3 Insights

Why do we multiply by base only when exponent is odd?

Because when exponent is odd, the power can be split as base * (base^(exp//2))^2. The multiplication by base accounts for the extra factor. See steps 7 and 11 in execution_table.

Why does the recursion stop at exponent 0 returning 1?

By definition, any number to the power 0 is 1. This is the base case that stops recursion. See step 5 in execution_table.

How does dividing exponent by 2 reduce the number of steps?

Each recursive call halves the exponent, so the depth of recursion is about log2(exp), making the algorithm much faster than multiplying exp times. See the chain of recursive calls in steps 1 to 5.

Visual Quiz - 3 Questions

Look at the execution_table, what is the return value at step 9 for exponent 2?

A 32

B 2

C 4

D 1

💡 Hint

Check the 'Return Value' column at step 9 in execution_table.

At which step does the recursion reach the base case where exponent is 0?

A Step 7

B Step 5

C Step 1

D Step 13

💡 Hint

Look for the step where 'Exponent (exp)' is 0 and return value is 1.

If the exponent was changed from 10 to 9, how would the number of recursive calls change?

A It would stay about the same (logarithmic depth)

B It would decrease by 1

C It would increase by 1

D It would double

💡 Hint

Check the recursive call pattern in execution_table and variable_tracker; halving exponent controls depth.

Concept Snapshot

Fast Exponentiation (Power) in Log N:
- Use recursion to compute base^exp
- Base case: exp=0 returns 1
- Recursively compute half = base^(exp//2)
- If exp even: result = half * half
- If exp odd: result = base * half * half
- Runs in O(log exp) time, much faster than naive multiplication

Full Transcript

Fast exponentiation calculates the power of a base raised to an exponent quickly by using recursion and squaring. The process checks if the exponent is zero, returning 1 as the base case. If the exponent is even, it recursively computes the power of half the exponent and squares it. If odd, it multiplies the base by the square of the half power. This reduces the number of multiplications from linear to logarithmic in the exponent size. The execution table traces a call with base 2 and exponent 10, showing recursive calls halving the exponent until zero, then combining results back up to get 1024. Variables track the exponent, half power, and return values at each step. Key moments clarify why multiplication by base happens only for odd exponents, why recursion stops at zero, and how halving reduces steps. The visual quiz tests understanding of return values, base case step, and recursion depth changes. This method is efficient and widely used in algorithms requiring fast power calculations.

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