Re: Induction problem ? (Atleast I think it is that :)

Vinay wrote: 
Hi,

I recently came across the following code:

const double epsilon = 1.0e-15;
double compute(double m) {
      double x = m;
      double y = 1.0;
      while(x - y > epsilon ) {
            x = (x+y)/2;
            y = m/x;
       }
       return x;
}

This function returns the square-root for given value(m). I tried
solving this algebraically but expression got too complex. Can anybody
point me how one can PROVE this to be true. I don't remember seeing any
expansions for square-root similar to say that of log(x), or sin(x) -
in case there is one please do mention it.

Vinay

PS: I tried looking up at recurring function solutions for square-root
( of the type y/(1+y/1+y(1/...))) but drew a blank.

This algorithm is elementary and widely known as the Newton formula. For proof, see for example:

http://mathews.ecs.fullerton.edu/n2003/newtonsmethod/Newton'sMethodProof/Links/Newton'sMethodProof_lnk_3.html

BTW, the method can be applied, after making appropriate substitutions, to computing sin and log as well.

HTH
.

Quantcast