Fast Exponentiation Power in Log N in DSA Rust - 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 Rust

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

Computes base raised to exp using fast exponentiation by squaring in O(log n) time.

Execution Table

Step	Operation	Exponent (exp)	Base (b)	Result	Action	Visual State
1	Initialize	5	2	1	Start with result=1, b=2, exp=5	result=1, b=2, exp=5
2	Check exp odd?	5	2	1	5 is odd, multiply result by b	result=1*2=2, b=2, exp=5
3	Square base	5	2	2	b = b * b = 4	result=2, b=4, exp=5
4	Halve exp	5	4	2	exp = 5 // 2 = 2	result=2, b=4, exp=2
5	Check exp odd?	2	4	2	2 is even, skip multiply	result=2, b=4, exp=2
6	Square base	2	4	2	b = 4 * 4 = 16	result=2, b=16, exp=2
7	Halve exp	2	16	2	exp = 2 // 2 = 1	result=2, b=16, exp=1
8	Check exp odd?	1	16	2	1 is odd, multiply result by b	result=2*16=32, b=16, exp=1
9	Square base	1	16	32	b = 16 * 16 = 256	result=32, b=256, exp=1
10	Halve exp	1	256	32	exp = 1 // 2 = 0	result=32, b=256, exp=0
11	Exit loop	0	256	32	exp == 0, stop and return result	result=32

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

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	After Step 7	After Step 8	After Step 9	After Step 10	Final
exp	5	5	5	2	2	2	1	1	1	0	0
b	2	2	4	4	4	16	16	16	256	256	256
result	1	2	2	2	2	2	2	32	32	32	32

Key Moments - 3 Insights

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

Because when the exponent is odd, the current base contributes to the final power. This is shown in execution_table step 2 and 8 where result is multiplied by b only if exp % 2 == 1.

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

Squaring the base corresponds to moving to the next power of two, and halving the exponent reduces the problem size. This is visible in steps 3, 6, 9 for squaring b and steps 4, 7, 10 for halving exp.

What happens when exponent becomes zero?

The loop stops because any number to the power 0 is 1, and the accumulated result is returned. This is shown in step 11 where exp=0 and the loop exits.

Visual Quiz - 3 Questions

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

A 16

B 2

C 32

D 64

💡 Hint

Check the 'Result' column at step 8 in the execution_table.

At which step does the exponent first become even?

A Step 5

B Step 4

C Step 2

D Step 7

💡 Hint

Look at the 'Exponent (exp)' column in execution_table rows to find when exp changes from odd to even.

If the initial exponent was 6 instead of 5, how would the result change at step 2?

A Result would be multiplied by base

B Result would remain 1

C Exponent would be halved immediately

D Base would not be squared

💡 Hint

Check the condition for multiplying result by base in execution_table step 2 and consider if exp=6 is odd or even.

Concept Snapshot

Fast Exponentiation (Power) in Log N:
- Use repeated squaring to reduce multiplications
- If exponent is odd, multiply result by base
- Square base and halve exponent each step
- Stop when exponent reaches zero
- Runs in O(log n) time, much faster than naive method

Full Transcript

Fast exponentiation calculates base raised to an exponent quickly by using repeated squaring. We start with result=1 and base as given. While exponent is greater than zero, if exponent is odd, multiply result by base. Then square the base and halve the exponent. Repeat until exponent is zero. The final result is returned. This method reduces the number of multiplications from linear to logarithmic in the exponent size.

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