GATE CSE 2017 Set 2 | Question: 37

Question

Consider the C 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 terminated in a state satisfying the condition $x==(y*q + r)$?

• A. $(q==r) \ \&\& \ (r==0)$
• B. $(x>0) \ \&\&  \ (r==x) \ \&\& \ (y>0)$
• C. $(q==0) \ \&\& \ (r==x) \ \&\& \ (y >0)$
• D. $(q==0) \ \&\& \ (y>0)$

Comments

https://gateoverflow.in/8276/gate2015-1_33

---

Dividend should be always greater than 0 ??

then why not option b ??

---

${0}/{integer}   = 0 $  works fine.

Answer 1

Here, $x == ( y*q + r )$ says $q =$ quotient and $r =$  remainder.

To divide a number with repeated subtraction, quotient should be initialized to $0$ and should be incremented for each subtraction.

Initially $q=0 \Rightarrow r = x$.

$\therefore$ Initial conditions should be C] $(q == 0) \ \&\& \ (r == x) \ \&\& \ (y > 0)$.

Comments

why do we need to check y>0 despite of it is given that y is unsigned integer.

---

If we divide a number with 0(zero), will result in undefined state. that's why we need to check y > 0 condition. And one more point, unsigned integer range is 0 to 2^n-1. And in here if we don't check y > 0 condition while loop will always true when divider = 0 and goes infinite loop.

---

nice explanation @kantikumar

---

why quotient take 0 i dont understand plz clear??

---

take an example x=2, y=3 then x divides y mean quotient q=0,remainder r=2 it becomes x, (r==x) and y is a divisor ,so it should be >0 otherwise whole expression will tend to infinity.

---

now i got the point thanku

---

this is a repeated question

---

how it is knows that the initial condition as r=x?

---

https://gateoverflow.in/8276/gate2015-1-33

reverse question

---

nice explanaion....

---

“ To divide a number with repeated subtraction, quotient should be initialized to 00 and should be incremented for each subtraction.”

can anyone explain this !

---

@gurichouhan If the quotient is not $0$, it would start incrementing ($+1$) from any random number, which will produce wrong results.

Suppose $x = 4, y = 2$. 

So answer should be : $4/2 = 2$

Using the given prg, 

while (r >= y) {
    r=r-y;
    q=q+1;
}

If quotient was $0$ initially, only then we will get $x == ( y*q + r )$ i.e,

$4 == (2*2+0)$

---

quotient is q i think not r

---

@shikhar500 Yes, that’s what I’ve done. We need to find $x/y$ where the result will be the quotient $(q)$ and remainder is $r$. Remember : $(x-r)/y = q$ 

Answer 2

we can solve  by leting some values, as shown below:-

Answer 3

$ x==(y∗q+r)$

I don't think it is hard to make an intuitive guess here that

x = number to be divided.

y = divisor.

q = quotient.

r = remainder.

 

Option A says set quotient == remainder in the beginning. It doesn't serve any good to division.

---

Option B says x > 0. Why? We can legally divide 0 by anything. So, if x === 0, division should have no issues.

---

Option C says set quotient == 0, remainder == number to be divided, and divisor > 0.

So far so good.

Trace out the code. (Keep $451 == 10 * 45 + 1$ in mind)

• In each subtraction, we're reducing the size of remainder by divisor. That's technically what happens with each division.
   
• Every time we successfully subtract, quotient increments. Good.

This Option is correct.

---

Option D doesn't specify for remainder == number to be divided in the beginning of the program, but division by repeated subtraction wants that.

Answer 4

option c

Comments

x=(y*q+r) So, when q==0 and y>0 , then x=r...

---

It is given in the question that we've to satisfy the condition x==(y∗q+r)
It is not given x=(y*q+r)
In the code fragment, initial value of r and q is not set. So, we've to initialize those.
r = x and q = 0.

---

Thankyou... i understood..