Question-3

Consider the Python program fragment below, which is meant to divide x by y using repeated subtractions. The variables x, y, q, and r are all unsigned int.

while r >= y:
    r = r - y
    q = q + 1

Which of the following conditions on the variables x, y, q, and r before the execution of the fragment will ensure that the loop terminates in a state satisfying the condition x == (y * q + r)?

• q == r and r == 0
• x > 0 and r == x and y > 0
• q == 0 and r == x and y > 0
• q == 0 and y > 0

Answer

• q == r and r == 0
• x > 0 and r == x and y > 0
• q == 0 and r == x and y > 0
• q == 0 and y > 0

Solution

To ensure that the loop terminates with the condition x == (y * q + r), the following conditions must hold:

• x must be greater than 0.
• r must be equal to x.
• y must be greater than 0.

These conditions are met in x > 0 and r == x and y > 0