GATE CSE 2004 | Question: 42

Question

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);

• A. $\log \, m$
• B. $m^2$
• C. $m^{\frac{1}{2}}$
• D. $m^{\frac{1}{3}}$

Comments

In question it is mentioned e>0

This condition is very ambiguous as assuming e much greater than x will result in x itself ( loop condition fails).

I understand , in exam most appropiate option is to be chosen

But what if, another option given as 'x'

?

Answer 1

By putting $y = m/x$ into $x = ( x + y )/2$
$\quad x= ( x + m/x ) /2$

$\implies 2x^2= x^2 + m$
$\implies x = m^{1/2}$

We can also check by putting $2$ or $3$ different values also.

Correct Answer: $C$

Comments

i dont know if you can do this

'=' is assignment operator not equals

if you say x=x^2 , it means you are squaring something not 'x==1'..

---

@Rajesh Pradhan @Shaik Masthan sir is it possible to put the value of 2nd step directly in step 1 without executing step 1?...According to me it is not possible to execute 2nd step directly. 

and also how can we think like this in exam duration ?

---

@halfcodeblood It's not correct.

Further, you can refer for the proof in the following link : https://en.m.wikipedia.org/wiki/Methods_of_computing_square_roots#Heron's_method

 

Credits : sakht - link is mentioned in the answer. 

https://gateoverflow.in/1039/gate-cse-2004-question-42?show=156271#a156271

 

Coming to the question, how to answer in exam ?

In such situation, kindly take one integer which can give different answer for different option and run the algorithm blindly. (Take m=64 ).

Answer 2

First of all this question is about approximation of value. So we can do 1 step more or less. That will not affect the answer.

Answer given by @gate_asp is somehow appropriate, but it doesn't answer some questions which are mentioned in comments. 

So here is my ans. 

loop will terminate in (Log Log n) iterations. at that time if x is a perfect square number then it x = y = $m^{1/2}$

otherwise it will terminate with condition y > x.

Answer 3

take m=8 and trace the Algorithm and verify the options A.3  B.64  C.2$\sqrt{2}$=2.82  D.3

Imp Note:-> we cant take variable type as int (cz it is an algorithm as specified in question) if U do so we end up with incorrect result

Now Trace the algorithm

Initially m=8 , $\epsilon$=1 , x=8 , y=1

Iteration #	x	y	while(x - y >1)
1	8	1	True
2	4.5	1.78	True
3	3.14	2.55	True
4	2.85	2.8	False

So it match with Option C .

Comments

In 3rd iterarion How are you getting 3.14 ?
For me the loop stops at rd iteration and output x as 2.75  .  But your trace has got 4 iterations .Moreover Your option D is 3 . It should be 2 .

Tough the answer does not change much

---

€ =1
In 3rd iteration

3.14 - 2.55 = 0.584

0.584 > 1 condition false

And then x = 3.14

____________________________________

If  € = 0

0.584 > 0  true

Then x= 2.84

____________________________________

But according to question € > 0

Then x should be 3.14

And option A match with that

---

Will the time complexity of the above program be O(log n)? Because when m=8 total iterations are 3 which is nothing but log8. Correct me if I am wrong

Answer 4

This is an implementation of Babylonian method for square root - http://www.geeksforgeeks.org/square-root-of-a-perfect-square/

its time complexity is - log(log(n/e)) -https://stackoverflow.com/questions/12309432/time-complexity-for-babylonian-method