Fast Exponentiation Power in Log N in DSA Rust

Mental Model

To find a number raised to a power quickly, we break the power into halves and multiply results, cutting steps in half each time.

Analogy: Imagine folding a big paper many times. Instead of folding one fold at a time, you fold it in halves repeatedly, making the process much faster.

base = 2, power = 8
2^8
  ↓
Split power: 8 -> 4 + 4
  ↓
Split again: 4 -> 2 + 2
  ↓
Multiply results step by step

Dry Run Walkthrough

Input: base = 2, power = 8

Goal: Calculate 2 to the power of 8 quickly using repeated squaring

Step 1: power is even, split 8 into 4 + 4, recursively compute 2^4

computing 2^8 -> compute 2^4 twice

Why: Splitting power reduces the number of multiplications

Step 2: power is even, split 4 into 2 + 2, recursively compute 2^2

computing 2^4 -> compute 2^2 twice

Why: Keep splitting power to smaller parts

Step 3: power is even, split 2 into 1 + 1, recursively compute 2^1

computing 2^2 -> compute 2^1 twice

Why: Reach the smallest power to multiply

Step 4: power is 1, return base 2

2^1 = 2

Why: Base case for recursion

Step 5: multiply 2^1 * 2^1 = 2 * 2 = 4, return 4 for 2^2

2^2 = 4

Why: Combine results of smaller powers

Step 6: multiply 2^2 * 2^2 = 4 * 4 = 16, return 16 for 2^4

2^4 = 16

Why: Combine results of smaller powers

Step 7: multiply 2^4 * 2^4 = 16 * 16 = 256, return 256 for 2^8

2^8 = 256

Why: Final multiplication to get result

Result:

2^8 = 256

Annotated Code

DSA Rust

fn fast_power(base: i32, power: i32) -> i32 {
    if power == 0 {
        return 1; // base case: anything^0 = 1
    }
    if power == 1 {
        return base; // base case: anything^1 = base
    }
    let half = fast_power(base, power / 2); // recursively compute half power
    if power % 2 == 0 {
        return half * half; // if even power, multiply half results
    } else {
        return half * half * base; // if odd power, multiply half results and base
    }
}

fn main() {
    let base = 2;
    let power = 8;
    let result = fast_power(base, power);
    println!("{}^{} = {}", base, power, result);
}

if power == 0 { return 1; }

return 1 when power is zero as base case

if power == 1 { return base; }

return base when power is one as base case

let half = fast_power(base, power / 2);

recursively compute power divided by two

if power % 2 == 0 { return half * half; }

if power even, multiply half results

else { return half * half * base; }

if power odd, multiply half results and base

Output

2^8 = 256

Complexity Analysis

Time: O(log n) because the power is divided by two each recursive call, reducing steps quickly

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

vs Alternative: Naive approach takes O(n) multiplying base power times, this method is much faster by halving steps

Edge Cases

power = 0

returns 1 immediately as anything to power zero is 1

DSA Rust

if power == 0 { return 1; }

power = 1

returns base immediately as base to power one is base

DSA Rust

if power == 1 { return base; }

power is odd

multiplies half results and base to handle odd power correctly

DSA Rust

else { return half * half * base; }

When to Use This Pattern

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

Common Mistakes

Mistake: Multiplying base power times in a loop causing slow O(n) time
Fix: Use recursive halving of power and multiply results to achieve O(log n) time

Mistake: Not handling odd powers correctly by missing the extra multiplication by base
Fix: Add multiplication by base when power is odd after squaring half results

Summary

Calculates base raised to power efficiently by splitting power in halves.

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

The key insight is to reduce the problem size by half each step and combine results.

Practice

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

easy

A. It reduces the time complexity from O(n) to O(log n)

B. It uses less memory than repeated multiplication

C. It works only for positive exponents

D. It avoids using multiplication altogether

Solution

1. Step 1: Understand repeated multiplication time

   Repeated multiplication multiplies the base n times, so it takes O(n) time.

2. Step 2: Understand fast exponentiation time

   Fast exponentiation uses squaring and halves the exponent each step, so it takes O(log n) time.

3. Final Answer:

   It reduces the time complexity from O(n) to O(log n) -> Option A

4. Quick Check:

   Fast exponentiation = O(log n) [OK]

Hint: Fast exponentiation halves exponent each step [OK]

Common Mistakes:

• Thinking it avoids multiplication
• Confusing time complexity with memory
• Believing it only works for positive exponents

2. Which of the following Rust function signatures correctly represents a fast exponentiation function for integers?

easy

A. fn fast_pow(base: i32, exp: i32) -> i32

B. fn fast_pow(base: i32, exp: i32) -> ()

C. fn fast_pow(base: i32) -> i32

D. fn fast_pow(exp: i32, base: i32) -> i32

Solution

1. Step 1: Check parameters needed

   Fast exponentiation needs base and exponent as inputs, both integers.

2. Step 2: Check return type

   It returns the computed power as an integer, so return type is i32.

3. Final Answer:

   fn fast_pow(base: i32, exp: i32) -> i32 -> Option A

4. Quick Check:

   Correct signature includes base, exp, returns i32 [OK]

Hint: Function needs base, exponent, returns result [OK]

Common Mistakes:

• Missing exponent parameter
• Wrong return type (void)
• Swapping parameter order incorrectly

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

fn fast_pow(mut base: i32, mut exp: i32) -> i32 {
    let mut result = 1;
    while exp > 0 {
        if exp % 2 == 1 {
            result *= base;
        }
        base *= base;
        exp /= 2;
    }
    result
}

fn main() {
    println!("{}", fast_pow(3, 5));
}

medium

A. 125

B. 243

C. 15

D. 81

Solution

1. Step 1: Understand fast_pow(3, 5)

   3^5 = 3*3*3*3*3 = 243.

2. Step 2: Trace the code logic

   Loop squares base and halves exp, multiplying result when exp is odd, correctly computing 243.

3. Final Answer:

   243 -> Option B

4. Quick Check:

   3^5 = 243 [OK]

Hint: Calculate 3^5 = 243 quickly [OK]

Common Mistakes:

• Calculating 5^3 instead of 3^5
• Confusing multiplication steps
• Forgetting to multiply result when exp is odd

4. Identify the bug in this Rust fast exponentiation function:

fn fast_pow(base: i32, mut exp: i32) -> i32 {
    let mut result = 1;
    let mut base = base;
    while exp > 0 {
        if exp % 2 == 0 {
            result *= base;
        }
        base *= base;
        exp /= 2;
    }
    result
}

medium

A. The result should start at 0, not 1

B. The base should not be mutable

C. The loop should run while exp >= 0

D. The condition should check if exp % 2 == 1, not 0

Solution

1. Step 1: Check condition for multiplying result

   Multiplying result should happen when exp is odd (exp % 2 == 1), not even.

2. Step 2: Confirm other parts

   Mutable base is correct, result starts at 1, loop condition is correct.

3. Final Answer:

   The condition should check if exp % 2 == 1, not 0 -> Option D

4. Quick Check:

   Multiply result only when exp is odd [OK]

Hint: Multiply result only if exponent is odd [OK]

Common Mistakes:

• Multiplying when exponent is even
• Starting result at 0
• Loop running one extra time

5. You want to compute (2^30) % 1000 efficiently using fast exponentiation in Rust. Which modification is necessary to the standard fast exponentiation algorithm to handle this correctly?

hard

A. Increase the base to 1000 before starting

B. Use floating point numbers instead of integers

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

D. Multiply result only when exponent is even

Solution

1. Step 1: Understand modulo exponentiation

   To compute (base^exp) % mod efficiently, apply modulo after each multiplication to avoid overflow.

2. Step 2: Modify fast exponentiation

   Insert modulo operation after multiplying result and squaring base to keep values within range.

3. Final Answer:

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

4. Quick Check:

   Modulo after each step prevents overflow [OK]

Hint: Apply modulo after every multiplication [OK]

Common Mistakes:

• Using floats causing precision errors
• Not applying modulo each step causing overflow
• Incorrectly multiplying on even exponent