2
$\begingroup$

My friend/colleague who just completed her Bachelors degree in Computer Science is now preparing for a Graduate Aptitute Test. Today she asked me about a question related to Complexity Analyis (Big-O Notation specifically) which I easily solved, and then came another question at which I got stuck. Question Statement was:

What does the following algorithm approximate?

x = m;
y = 1;
while (x - y > e)
{
   x = (x + y)/2;
   y = m/x;
}
print(x);

(Assume m > 1, e > 0).

Options:

(A) log m
(B) $m^2$
(C) m^1/2
(D) m^1/3

Initially I assumed upon looking at the code that the answer would be (C), she also came up with that answer as well (she didn't actually solve it), to my surprise it was actually correct as I cross-checked the answer here. When I looked for the explanation, it said:

The given code is implementation of Babylonian method for square root

Easy, right? But since there wasn't anything like Number Theory in our syllabus (although there were Engineering Mathematics, Discrete Mathematics and Numerical Methods for Engineers) I did not know anything about this method, meaning that I had to solve it by myself (which I thought would be pretty easy since these type of questions have to be solved in one minute, if you want to attempt all the questions). So I took a paper and a pen (second time) before telling her that I'll get it solved in the morning and started solving it, trying to keep it simple but eventually made it complex (images attached).

First page

Second page

The only thing that I could deduce was that the complexity of the code was O(logM) and X halves (approximately) in each iteration and Y doubles (approximately) in each iteration. That wasn't the required answer, so I assumed that I was missing something, so I looked up the Babylonian Square Root Algorithm and found out that the complexity was O(logN) and the code provided above was a little messed up since

while (x - y > e)

which was actually meant to be

while (x - y)

The e was just added to make it more complex, also it would make the problem to solve by trial and error if someone assumed e to be a large value (although it was an easy job if someone assumed e=1 and m=100).

I figured that maybe if I write a code to generate some statistics, then I might be able to figure something out, so I wrote this:

#include<iostream>
int main(int argc, char** argv)
{
    float x,y=1,m,e;
    std::cin>>m>>e;
    x=m;
    while(x-y>e)
    {
        x=(x+y)/2;
        y=(m/x);
        std::cout<<x<<"\t"<<y<<"\t"<<x-y<<std::endl;
    }
    return 0;
}

Initially, I found out that e was actually a culprit, as providing larger values would affect the answer by not letting it completely finish.

The problem still remained, how to know that the answer would be $m^2$ ? I don't know, I am a loser when it comes to mathematics (and that is why I need help)

Below is some sample data from two inputs, 100000 5 and 100 5

enter image description here

I could see that both X and Y would converge to the square root of M, and E was the evil variable. Now, in brief, assuming the following that:

  • Candidate doesn't know about Babylonian Square-root method
  • Question has to be attempted ideally within 1 minute
  • A well prepared candidate can analyze the complexity easily
  • Trial and Error method is only a matter of luck with low probability of success
  • The answer doesn't need to be accurate, but approximate

How this problem can be solved?

$\endgroup$
5
  • $\begingroup$ I just posted this question, and its morning time here. P.S. : It needs to be edited by an expert in my opinion, as my formatting is not up to the mark. $\endgroup$
    – RishbhSharma
    Jun 1, 2017 at 23:43
  • 3
    $\begingroup$ That's a lot of typing for a friend/colleague. $\endgroup$
    – Paul
    Jun 1, 2017 at 23:55
  • 1
    $\begingroup$ I just got involved a bit too much into the question and couldn't sleep thanks to overthinking and chronic insomnia. Edit : I wish I could give your comment a bunch of upvotes. $\endgroup$
    – RishbhSharma
    Jun 2, 2017 at 0:00
  • $\begingroup$ I think it's meant to be an easy question, just recognition of the algorithm (often mentioned in introductory programming classes, or if not falls under the "Numerical Methods for Engineers" heading). It's a special case of Newton's method for finding roots of a function of one variable, and also often discussed in that context in introductory calculus courses as an example. $\endgroup$
    – Daniel Schepler
    Jun 2, 2017 at 0:00
  • $\begingroup$ I strongly believe in your statement. It actually is a special case of Newton's method for finding roots of a function of one variable. But I can't figure it out in a simple way. $\endgroup$
    – RishbhSharma
    Jun 2, 2017 at 0:02

2 Answers 2

Reset to default
3
$\begingroup$

Maybe e is like $\epsilon$ in math and is supposed to suggest a small positive number. Then the fact that the loop terminates when $x-y \lt e$ should suggest they are almost equal. Note that this assumes $x \gt y,$ otherwise it also terminates the first time $x \lt y$. Anyway, this suggests plugging $x=y$ into the equations and it is easy to derive $x=\sqrt m$

I don't suggest this is at all rigorous and I think it is a terrible question, but this will get you to the answer. I think I would just run it by hand for some small $x$ like $8$, notice that it seems to be converging to the square root, and quit. I can tell $\log 8, 8^{1/2},8^{1/3},8^2$ apart easily.

$\endgroup$
8
  • $\begingroup$ the fact that the loop terminates when x−y<e should suggest they are almost equal. Right, there is a negligible difference between x and y for small values of e. notice that it seems to be converging to the square root, and quit. Yes, right, that's what it is expected to do. this suggests plugging x=y into the equations and it is easy to derive x=sqrt(m). Makes sense, but I am a dummy at maths, could you please tell me how to do that in easy steps? $\endgroup$
    – RishbhSharma
    Jun 1, 2017 at 23:53
  • $\begingroup$ About "Note that this assumes ...", the question says $x = m > 1 = y$ initially. $\endgroup$
    – peterwhy
    Jun 1, 2017 at 23:54
  • $\begingroup$ @RishbhSharma: Note that if $x=y$ then $x=(x+y)/2$ and that $y=m/x=m/y$ implies $y^2=m$ $\endgroup$
    – Ross Millikan
    Jun 2, 2017 at 0:07
  • $\begingroup$ @peterwhy: Yes, we start with $x \gt y$ but I don't think it is obvious that $x$ stays greater than $y$ as we iterate. It is true, but if $x$ could get less than $y$ we could terminate with them rather far apart. $\endgroup$
    – Ross Millikan
    Jun 2, 2017 at 0:08
  • $\begingroup$ @RossMillikan : Took me a while, but I finally got it. Now I can go to sleep. Don't be offended but I still believe there is a plain simple way of solving it by knowing only the details listed in the question here $\endgroup$
    – RishbhSharma
    Jun 2, 2017 at 0:16
0
$\begingroup$

Imagine you've got a rectangle of area $m$. You try to find such side length so that it's a square. So you proceed - start with rectangle $1\times m$. Then take their average as one side. The second side should be such that the area remains equal to $m$. That's the idea.

But, one could discard other options rather quickly. $m^2$ is absurd, $\log m$ should involve repeated division, maybe $m^{1/3}$? But after trying the algorithm for some small number, one gets that it can't be cubic root.

$\endgroup$
1
  • $\begingroup$ MathJax hint: to get multicharacter exponents, put them in braces, so m^{1/3} becomes $m^{1/3}$ when placed in dollar signs. Also putting a backslash before common functions gets the proper font and spacing, so \log m gets $\log m$ $\endgroup$
    – Ross Millikan
    Jun 2, 2017 at 1:49

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .