Fast Exponentiation Power in Log N in DSA Rust - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the main idea behind Fast Exponentiation (Power) algorithm?

It reduces the number of multiplications by repeatedly squaring the base and using the binary form of the exponent, achieving power calculation in logarithmic time.

beginner

Why is Fast Exponentiation faster than the naive method?

Because it uses the exponent's binary representation to square the base and multiply selectively, reducing operations from n multiplications to about log₂(n) multiplications.

intermediate

In Fast Exponentiation, what do you do when the current exponent bit is 1?

Multiply the current result by the current base value before squaring the base for the next bit.

beginner

Show the Rust function signature for a fast exponentiation function that calculates base^exponent.

fn fast_power(base: u64, exponent: u64) -> u64

intermediate

What is the time complexity of Fast Exponentiation and why?

O(log n) because the exponent is divided by 2 at each step, reducing the problem size exponentially.

What is the time complexity of the naive power calculation method?

A O(1)

B O(log n)

C O(n^2)

D O(n)

The naive method multiplies the base n times, so it takes O(n) time.

In Fast Exponentiation, what operation is performed when the current exponent bit is 0?

A Multiply result by base

B Add base to result

C Square the base only

D Divide base by 2

When the bit is 0, we only square the base and do not multiply the result.

Which of these is a correct Rust return type for a fast exponentiation function with u64 inputs?

A u64

B u32

C i64

D f64

Since inputs are u64 and result can be large, u64 is appropriate.

What does the 'exponent & 1' operation check in Fast Exponentiation?

A If exponent is odd

B If exponent is even

C If exponent is zero

D If exponent is negative

'exponent & 1' checks the least significant bit to see if exponent is odd.

Which of these best describes the Fast Exponentiation algorithm?

A Repeated multiplication

B Divide and conquer using squaring

C Linear iteration

D Recursive addition

Fast Exponentiation uses divide and conquer by squaring the base.

Explain how Fast Exponentiation reduces the number of multiplications compared to the naive method.

Think about how the exponent's bits guide the multiplication steps.

Write a simple Rust function for Fast Exponentiation and describe each step in comments.

Use bitwise operations and a while loop.

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