GATE CSE 2004 | Question: 41

Question

Consider the following C program

main()
{ 
    int x, y, m, n;
    scanf("%d %d", &x, &y);
    /* Assume x>0 and y>0*/
    m = x; n = y;
    while(m != n)
        { 
            if (m > n)
                m = m-n;
            else
                n = n-m;
        }
    printf("%d", n);
}

The program computes

• A. $x+y$ using repeated subtraction

• B. $x \mod y$ using repeated subtraction

• C. the greatest common divisor of $x$ and $y$

• D. the least common multiple of $x$ and $y$

Comments

Same question repeated again : Algorithms: GATE CSE 1995 | Question: 2.3 (gateoverflow.in)

---

The program computes the greatest common divisor of x and y using the Euclidean algorithm. When m and n are both equal to the GCD of x and y, the while loop will terminate and the GCD will be printed. The other answer choices are incorrect.

Answer 1

It is an algorithm for $\gcd$ computation.

Here, while loop executes until $m=n$.
We can test by taking any two numbers as $m,n$.

Answer will be (C).

Ref: https://www.khanacademy.org/computing/computer-science/cryptography/modarithmetic/a/the-euclidean-algorithm

Comments

Reference

http://www.naturalnumbers.org/EuclidSubtract.html

---

EGCD is one the most favourite question on examiners.

hence in most of the good test series, you fill find question on fibonacci pair, which is the worst case input for the EGCD.

---

@ijnuhb to be more precise . consecutive fibonacci pairs.

Answer 2

c) euclidean algorithm

Answer 3

Algorithm for GCD(Greatest Common Divisor) computation 

 

Division-based Programmed:

function gcd(a, b)
    while b ≠ 0
        t := b
        b := a mod b
        a := t
    return a

 

In the subtraction-based version which was Euclid's original version, the remainder calculation (b := a mod b) is replaced by repeated subtraction.

 

function gcd(a, b)
    while a ≠ b 
        if a > b
            a := a − b
        else
            b := b − a
    return a

Comments

got it