Strength reduction in Compiler Design - Practice Problems & Coding Challenges

Challenge - 5 Problems

🧠 Conceptual

intermediate

Understanding the purpose of strength reduction

What is the main goal of applying strength reduction in compiler optimization?

A To replace expensive operations with cheaper ones to improve performance

B To increase the number of instructions for better parallelism

C To convert high-level code into assembly language

D To remove all loops from the program

💡 Hint

Think about how replacing certain operations can make code run faster.

Strength reduction replaces costly operations like multiplication or division with simpler operations like addition or bit shifts, which are faster to execute.

📋 Factual

intermediate

Identifying strength reduction in code

Which of the following code transformations is an example of strength reduction?

Compiler Design

for (int i = 0; i < n; i++) {
    a[i] = b * i;
}

A Replace b * i with b / i

B Replace b * i with a single multiplication outside the loop

C Replace b * i with an incremented variable initialized to 0 and increased by b each iteration

D Replace b * i with repeated addition: sum = 0; for (int j = 0; j < i; j++) sum += b;

💡 Hint

Consider how multiplication by i can be turned into addition inside the loop.

Strength reduction replaces multiplication inside the loop with an incremented variable that adds b each iteration, which is cheaper than multiplying every time.

🔍 Analysis

advanced

Analyzing strength reduction effect on loop performance

Consider the loop below. What is the main performance benefit after applying strength reduction?

Compiler Design

int x = 0;
for (int i = 0; i < n; i++) {
    y[i] = 5 * i + 3;
}

A Uses division instead of multiplication to reduce computation time

B Eliminates the loop entirely by unrolling it

C Replaces addition with multiplication to speed up calculations

D Reduces the number of multiplications by replacing 5 * i with an incremented variable starting at 0 and adding 5 each iteration

💡 Hint

Focus on how multiplication inside the loop can be optimized.

By replacing multiplication with addition, the loop performs fewer costly operations, improving performance.

❓ Comparison

advanced

Comparing strength reduction with other optimizations

Which statement correctly distinguishes strength reduction from loop unrolling?

A Strength reduction duplicates loop body; loop unrolling replaces multiplication with addition

B Strength reduction replaces expensive operations with cheaper ones; loop unrolling duplicates loop body to reduce loop overhead

C Both techniques remove loops entirely from the code

D Strength reduction increases the number of instructions; loop unrolling decreases them

💡 Hint

Think about what each optimization changes in the code.

Strength reduction focuses on replacing costly operations with cheaper ones, while loop unrolling reduces the overhead of looping by repeating the loop body multiple times.

❓ Reasoning

expert

Determining the correctness of strength reduction application

Given the code snippet below, which option correctly applies strength reduction without changing the program's behavior?

Compiler Design

int result = 0;
for (int i = 1; i <= n; i++) {
    result += 4 * i;
}

A

int temp = 0;
for (int i = 1; i <= n; i++) {
    temp += 4;
    result += temp;
}

B

int temp = 0;
for (int i = 1; i <= n; i++) {
    result += 4;
}

C

int temp = 0;
for (int i = 1; i <= n; i++) {
    temp += 4;
    result = temp * i;
}

D

int temp = 0;
for (int i = 1; i <= n; i++) {
    temp = 4 * i;
    result += temp;
}

💡 Hint

Consider how to replace multiplication with addition while preserving the sum.

Option A replaces multiplication by incrementing a temporary variable by 4 each iteration and adding it to result, preserving the original sum.