7,625 views
15 votes
15 votes

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

  1. $x+y$ using repeated subtraction

  2. $x \mod y$ using repeated subtraction

  3. the greatest common divisor of $x$ and $y$

  4. the least common multiple of $x$ and $y$

3 Answers

Best answer
18 votes
18 votes

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

edited by
0 votes
0 votes

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
Answer:

Related questions

33 votes
33 votes
6 answers
1
Kathleen asked Sep 18, 2014
14,113 views
What does the following algorithm approximate? (Assume $m 1, \epsilon >0$).x = m; y = 1; While (x-y ϵ) { x = (x+y)/2; y = m/x; } print(x);$\log \, m$$m^2$$m^{\frac{1}{...
47 votes
47 votes
7 answers
2
Kathleen asked Sep 18, 2014
17,290 views
The recurrence equation$ T(1) = 1$$T(n) = 2T(n-1) + n, n \geq 2$evaluates to$2^{n+1} - n - 2$$2^n - n$$2^{n+1} - 2n - 2$$2^n + n $
31 votes
31 votes
6 answers
3
Kathleen asked Sep 18, 2014
19,268 views
The time complexity of the following C function is (assume $n 0$)int recursive (int n) { if(n == 1) return (1); else return (recursive (n-1) + recursive (n-1)); }$O(n)$$...