Fast Exponentiation Power in Log N in DSA Rust - Build from Scratch

Fast Exponentiation Power in Log N

📖 Scenario: Imagine you want to calculate the power of a number quickly, like finding how many candies you get if you double them several times. Instead of multiplying many times, you can use a faster way called fast exponentiation.

🎯 Goal: You will build a Rust program that calculates base raised to the power exponent using fast exponentiation, which works in O(log n) time instead of multiplying base repeatedly.

📋 What You'll Learn

Create variables for base and exponent with exact values

Create a variable result to store the answer starting at 1

Use a while loop to apply fast exponentiation logic

Print the final result after calculation

💡 Why This Matters

🌍 Real World

Fast exponentiation is used in cryptography, computer graphics, and scientific calculations where powers of numbers must be computed quickly.

💼 Career

Understanding fast exponentiation helps in optimizing algorithms and is a common interview question for software engineering roles.

1

Create base and exponent variables

Create a variable called base with value 3 and a variable called exponent with value 5.

DSA Rust

# Create variables base and exponent with values 3 and 5
# Your code here

Hint

Use let to create variables and assign the exact numbers.

2

Create result variable

Add a variable called result and set it to 1 to hold the power calculation result.

DSA Rust

fn main() {
    let base = 3;
    let exponent = 5;
    // Create result variable set to 1
    // Your code here
}

Hint

Use let mut because result will change during calculation.

3

Implement fast exponentiation loop

Add a mutable variable exp set to exponent. Use a while loop with condition exp > 0. Inside the loop, if exp % 2 == 1, multiply result by base. Then square base by multiplying it by itself. Finally, divide exp by 2 using integer division.

DSA Rust

fn main() {
    let base = 3;
    let exponent = 5;
    let mut result = 1;
    // Add fast exponentiation loop here
    // Your code here
}

Hint

Remember to make base mutable because it changes inside the loop.

4

Print the final result

Add a println! statement to print the value of result.

DSA Rust

fn main() {
    let mut base = 3;
    let mut exp = 5;
    let mut result = 1;
    while exp > 0 {
        if exp % 2 == 1 {
            result *= base;
        }
        base *= base;
        exp /= 2;
    }
    // Print the result
    // Your code here
}

Hint

Use println!("{}", result); to show the final answer.

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