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

Concept Flow - Fast Exponentiation Power in Log N

Start with base and exponent

↓

Check if exponent == 0?

Yes→Return 1

No↓

Is exponent even?

Yes→Square base, halve exponent

↓

Multiply result by base

↓

Multiply result by base

↓

Repeat until exponent == 0

↓

Return result

This flow shows how we repeatedly square the base and halve the exponent, multiplying the result when the exponent is odd, until the exponent reaches zero.

Execution Sample

DSA Go

func fastPower(base, exp int) int {
    result := 1
    for exp > 0 {
        if exp % 2 == 1 {
            result *= base
        }
        base *= base
        exp /= 2
    }
    return result
}

Calculates base raised to exp using fast exponentiation in logarithmic time.

Execution Table

Step	Operation	base	exp	result	Explanation
1	Start	2	10	1	Initialize result=1, base=2, exp=10
2	Check exp%2==1?	2	10	1	10 is even, skip multiply
3	Square base	4	10	1	base = 2*2=4
4	Halve exp	4	5	1	exp = 10/2=5
5	Check exp%2==1?	4	5	1	5 is odd, multiply result by base
6	Multiply result	4	5	4	result = 1*4=4
7	Square base	16	5	4	base = 4*4=16
8	Halve exp	16	2	4	exp = 5/2=2
9	Check exp%2==1?	16	2	4	2 is even, skip multiply
10	Square base	256	2	4	base = 16*16=256
11	Halve exp	256	1	4	exp = 2/2=1
12	Check exp%2==1?	256	1	4	1 is odd, multiply result by base
13	Multiply result	256	1	1024	result = 4*256=1024
14	Square base	65536	1	1024	base = 256*256=65536
15	Halve exp	65536	0	1024	exp = 1/2=0
16	End	65536	0	1024	exp=0, return result=1024

💡 exp reaches 0, loop ends, final result is 1024

Variable Tracker

Variable	Start	After Step 4	After Step 8	After Step 11	After Step 15	Final
base	2	4	16	256	65536	65536
exp	10	5	2	1	0	0
result	1	1	4	4	1024	1024

Key Moments - 3 Insights

Why do we multiply the result only when the exponent is odd?

Because when exponent is odd, we need to include the current base once in the result. This is shown in steps 5 and 12 where exp%2==1 triggers multiplication (rows 5 and 12 in execution_table).

Why do we square the base and halve the exponent each loop?

Squaring the base and halving the exponent reduces the problem size quickly, making the algorithm run in log N time. This is visible in steps 3, 7, 10, and 14 where base is squared and exp is halved (rows 3,7,10,14).

What happens when exponent becomes zero?

When exponent reaches zero (step 16), the loop ends and the current result is returned as the final answer (row 16).

Visual Quiz - 3 Questions

Look at the execution_table at step 6, what is the value of result?

A 1

B 4

C 16

D 256

💡 Hint

Check the 'result' column at step 6 in execution_table

At which step does the exponent first become odd?

A Step 5

B Step 2

C Step 4

D Step 9

💡 Hint

Look at the 'exp' and 'Operation' columns in execution_table rows 2 to 6

If the initial exponent was 9 instead of 10, how would the first multiplication step change?

A It would not happen at all

B It would happen after squaring base once

C It would happen immediately at step 2

D It would happen only at the end

💡 Hint

Odd exponent triggers multiplication immediately, check step 2 where exp=10 (even) skips multiply

Concept Snapshot

Fast Exponentiation (Power in Log N):
- Initialize result=1
- While exponent > 0:
  - If exponent odd, multiply result by base
  - Square base
  - Halve exponent (integer division)
- Return result
This reduces multiplications from N to log N.

Full Transcript

Fast exponentiation calculates base raised to an exponent quickly by using repeated squaring and halving the exponent. We start with result 1. If the exponent is odd, we multiply the result by the current base. Then we square the base and halve the exponent. We repeat this until the exponent becomes zero. This method reduces the number of multiplications from the exponent's value to its logarithm, making it very efficient. The example with base 2 and exponent 10 shows how the base and exponent change each step, and when the result is multiplied. The final result is 1024.

Practice

1. What is the main advantage of using fast exponentiation (power in log n) over the simple repeated multiplication method?

easy

A. It reduces the number of multiplications from n to log n

B. It uses less memory by storing all intermediate powers

C. It works only for even powers

D. It avoids multiplication completely

Solution

1. Step 1: Understand simple exponentiation

   Simple method multiplies the base by itself n times, so it takes n multiplications.

2. Step 2: Understand fast exponentiation

   Fast exponentiation uses repeated squaring, reducing multiplications to about log n times.

3. Final Answer:

   It reduces the number of multiplications from n to log n -> Option A

4. Quick Check:

   Fast exponentiation = fewer multiplications [OK]

Hint: Fast exponentiation cuts steps from n to log n [OK]

Common Mistakes:

• Thinking it only works for even powers
• Confusing memory use with speed
• Believing it avoids multiplication

2. Which of the following Go function signatures correctly represents a fast exponentiation function that calculates base^exp (integer power)?

easy

A. func fastPower(base float64, exp int) float64

B. func fastPower(base int, exp float64) int

C. func fastPower(base int, exp int) int

D. func fastPower(base int, exp int) float64

Solution

1. Step 1: Identify parameter types for integer power

   Base and exponent should be integers for integer power calculation.

2. Step 2: Check return type

   Return type should be int to match integer power result.

3. Final Answer:

   func fastPower(base int, exp int) int -> Option C

4. Quick Check:

   Integer base and exponent with int return [OK]

Hint: Use int for base, exponent, and return for integer powers [OK]

Common Mistakes:

• Using float64 for exponent when integer is needed
• Returning float64 instead of int
• Mixing base and exponent types

3. What is the output of the following Go code snippet?

func fastPower(base int, exp int) int {
    if exp == 0 {
        return 1
    }
    half := fastPower(base, exp/2)
    if exp%2 == 0 {
        return half * half
    } else {
        return half * half * base
    }
}

fmt.Println(fastPower(2, 5))

medium

A. 10

B. 32

C. 25

D. 16

Solution

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

   fastPower(2,5) calls fastPower(2,2), which calls fastPower(2,1), which calls fastPower(2,0)=1.

2. Step 2: Calculate results bottom-up

   fastPower(2,1) = 1*1*2=2; fastPower(2,2) = 2*2=4; fastPower(2,5) = 4*4*2=32.

3. Final Answer:

   32 -> Option B

4. Quick Check:

   2^5 = 32 [OK]

Hint: Remember 2^5 = 32; fastPower uses recursion [OK]

Common Mistakes:

• Confusing multiplication order
• Forgetting to multiply by base for odd exponent
• Miscomputing base cases

4. The following Go code for fast exponentiation has a bug. What is the bug?

func fastPower(base int, exp int) int {
    if exp == 0 {
        return 0
    }
    half := fastPower(base, exp/2)
    if exp%2 == 0 {
        return half * half
    } else {
        return half * half * base
    }
}

medium

A. Function does not handle negative exponents

B. Missing multiplication by base for even exponents

C. Incorrect integer division for exp/2

D. Base case returns 0 instead of 1

Solution

1. Step 1: Check base case for exponent 0

   Exponent 0 means power is 1, but code returns 0, which is incorrect.

2. Step 2: Verify other parts

   Multiplication and division logic is correct; negative exponent handling is not required here.

3. Final Answer:

   Base case returns 0 instead of 1 -> Option D

4. Quick Check:

   Power of 0 exponent = 1 [OK]

Hint: Base case for exp=0 must return 1 [OK]

Common Mistakes:

• Returning 0 for exp=0 base case
• Ignoring negative exponent cases
• Misplacing multiplication logic

5. You want to compute (3^13) mod 7 efficiently using fast exponentiation in Go. Which modification is needed in the fastPower function to correctly compute this without overflow?

hard

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

B. Use float64 type for base and exponent to handle large numbers

C. Multiply only once at the end after all recursion completes

D. Increase the base to base*mod to avoid overflow

Solution

1. Step 1: Understand modular exponentiation

   To avoid overflow and keep numbers small, apply modulo after each multiplication.

2. Step 2: Modify fastPower to include modulo

   Insert modulo operation after multiplying halves and base to keep intermediate results within mod.

3. Final Answer:

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

4. Quick Check:

   Modulo after multiplication prevents overflow [OK]

Hint: Apply modulo after every multiplication step [OK]

Common Mistakes:

• Delaying modulo until end causes overflow
• Using float64 instead of int causes precision loss
• Multiplying base by mod increases value incorrectly