Fast Exponentiation Power in Log N in DSA Go

Mental Model

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

Analogy: Imagine climbing stairs two steps at a time instead of one. You reach the top faster by skipping steps smartly.

power(base, exponent)
  ↓
  base^exponent
  ↓
  base^(exponent/2) * base^(exponent/2) (if exponent even)
  or
  base * base^(exponent-1) (if exponent odd)

Dry Run Walkthrough

Input: Calculate 3^13 using fast exponentiation

Goal: Compute 3 raised to the power 13 quickly using repeated squaring

Step 1: Check if exponent 13 is odd; multiply result by base 3 and reduce exponent to 12

result = 3, exponent = 12

Why: Odd exponent means we take one base out and work with even exponent

Step 2: Square base: 3^2 = 9, halve exponent: 12 / 2 = 6

base = 9, exponent = 6, result = 3

Why: We reduce the problem size by squaring base and halving exponent

Step 3: Exponent 6 is even, square base: 9^2 = 81, halve exponent: 6 / 2 = 3

base = 81, exponent = 3, result = 3

Why: Continue halving exponent and squaring base for efficiency

Step 4: Exponent 3 is odd; multiply result by base 81, reduce exponent to 2

result = 3 * 81 = 243, exponent = 2, base = 81

Why: Handle odd exponent by multiplying current result by base

Step 5: Square base: 81^2 = 6561, halve exponent: 2 / 2 = 1

base = 6561, exponent = 1, result = 243

Why: Keep reducing exponent by squaring base

Step 6: Exponent 1 is odd; multiply result by base 6561, reduce exponent to 0

result = 243 * 6561 = 1594323, exponent = 0

Why: Final odd exponent step multiplies result by base

Result:

Final result = 1594323

Annotated Code

DSA Go

package main

import "fmt"

func fastPower(base int, exponent int) int {
    result := 1
    currBase := base
    currExp := exponent

    for currExp > 0 {
        if currExp%2 == 1 {
            result *= currBase
        }
        currBase *= currBase
        currExp /= 2
    }

    return result
}

func main() {
    base := 3
    exponent := 13
    fmt.Printf("%d^%d = %d\n", base, exponent, fastPower(base, exponent))
}

for currExp > 0 {

repeat until exponent is zero

if currExp%2 == 1 {

if exponent is odd, multiply result by current base

result *= currBase

update result with base for odd exponent

currBase *= currBase

square the base to reduce exponent faster

currExp /= 2

halve the exponent to shrink problem size

Output

3^13 = 1594323

Complexity Analysis

Time: O(log n) because the exponent is halved each step, reducing the number of multiplications

Space: O(1) because only a few variables are used regardless of input size

vs Alternative: Naive approach takes O(n) multiplications by multiplying base exponent times, which is slower for large exponents

Edge Cases

exponent is 0

returns 1 because any number to power 0 is 1

DSA Go

for currExp > 0 {

exponent is 1

returns base itself as result

DSA Go

if currExp%2 == 1 {

base is 0 and exponent > 0

returns 0 because 0 to any positive power is 0

DSA Go

result *= currBase

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 result by base before checking if exponent is odd
Fix: Only multiply result by base when exponent is odd inside the loop

Mistake: Not halving the exponent after squaring the base
Fix: Divide exponent by 2 each iteration to shrink problem size

Summary

Computes base raised to exponent quickly by repeated squaring.

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

The key is to halve the exponent each step and square the base to reduce multiplications.

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