edited by
1,745 views
12 votes
12 votes

Consider the following program operating on four variables $u, v, x, y$, and two constants $X$ and $Y$.

x, y, u, v:= X, Y, Y, X;    
While (x ≠ y)  
do
    if (x > y) then x, v := x - y, v + u;
    else if (y > x) then y, u:= y - x, u + v;  
od;
print ((x + y) / 2);  print ((u + v) / 2);  

Given $X > 0 \land Y > 0$, pick the true statement out of the following:

  1. The program prints $\text{gcd}(X, Y)$ and the first prime larger than both $X$ and $Y$.
  2. The program prints $\text{gcd}(X, Y)$ followed by $\text{lcm}(X, Y)$.
  3. The program prints $\text{gcd}(X, Y)$ followed by $\frac1 2 \times \text{lcm}(X, Y)$.
  4. The program prints $\frac1 2 \times \text{gcd}(X, Y)$ followed by $\frac1 2 \times \text{lcm}(X, Y)$.
  5. The program does none of the above.
edited by

2 Answers

13 votes
13 votes

Greatest Common Divisor of two number can be calculated using Euclid's Algorithm[1]

$$\begin{align}gcd(X,0) &= X \\ gcd(X,Y) &= gcd(Y,X \%Y)\end{align}$$

For $X,Y > 0$ this algorithm can be simplified as follows

$$gcd(X,Y) = \left\{\begin{matrix} X & X=Y& \\gcd(X-Y,Y)&X>Y & \\ gcd(X,Y-X)&X<Y & \end{matrix}\right.$$

Out of observation we learn that the given program is performing the same operation on two variable $x$ and $y$ initialized to $X$ and $Y$ respectively. Loop terminated with $x=y$, therefore $(x+y)/2$ i.e., average of two will return $x$ (or $y$), which is essentially $gcd(X,Y)$.

Next, let us propose a loop invariant[2] for this program[3]

$$2 X Y = (x \times v) + (y \times u)$$

The correctness of this program depends on this invariant, which must be true prior to the first iteration of the loop, during the execution of loop and with the termination of the loop it must express some useful property that program exhibits. Let's briefly show these three things.

  1. Initialization: The fact that this loop invariant holds prior to the first iteration of the loop can be seen by plugging in initial values of $x,y,u$ and $v$.
  2. Maintenance: Let us assume this loop invariant holds before $i^{th}$ iteration and we need to show that it holds after $i^{th}$ iteration as well. During $i^{th}$ iteration for $x>y$, $x = (x-y)$ and $u = (u+v)$. Substitue these new values in loop invariant we get $$\begin{align}2XY & = (x-y) \times v + y(u+v) \\ & = (x \times v) + (y \times u)\end{align}$$ And same will also be true for $x<y$.
  3. Termination: Loop terminates with $x=y$ and as shown earlier that $x=y=gcd(X,Y)$. Therefore, $$\begin{align}2XY & = (x \times v) + (x \times u) = x(u+v) \\ 2XY & = gcd(X,Y)(u+v) \end{align} $$ 

Rearranging above equation gives us[4]

$$\frac{XY}{gcd(X,Y)} = LCM(X,Y) = \frac{u+v}{2}$$

HTH


REFERENCES

  1. GCD using Euclid's Algorithm
  2. Introduction to Algorithms, CLRS, 3rd edition, 2.1, Pg.18
  3. Edsger Dijkstra lecture at University of Newcastle 1992
  4. Reduction by the greatest common divisor

P.S In competitive examinations like GATE/TIFR the better strategy for such unfamiliar program is to try executing the program on different values, observe the result and compare with given options. However, in my opinion, understanding the underlining crux of such problems (when we are outside examination hall) is more important than just getting answers.

9 votes
9 votes
It prints with $gcd(x,y)$ and $lcm(x,y)$.

Consider $x,y,u,v=17,3,3,17$.

$X=14$, $v=20$

$X=11$, $v=23$

$X=8$, $v=26$

$X=5$, $v=29$

$X=2$, $v=32$

$Y=1$, $u=35$

$X=1$, $v=67$

This is the value obtained.

Lastly, printing $(x+y)/2$ and $(v+u)/2$ gives $1$ and $51$.

Correct option: B
edited by
Answer:

Related questions