Newton's method to find squareroot

[rockerjhr]

ok so I was doing a a function that would find the square root of a number to a certain precision using newtons method and this is what I came up with

/* 
 * File:   main.cpp
 * 
 *
 * Created on July 6, 2012, 6:58 PM
 */
#include <iostream>
#include <cstdlib>

using namespace std;

/*
 * 
 */

double sqrt(double n)
{


    if(n == 0 || n == 1) return n ; 


    double pres = 0.0001 ;
    double x_0 = n/4 ; 
    double x_1 = x_0-   (((x_0*x_0)-n)/(2*x_0)) ; 

    while(( x_1 - x_0 > pres )){

        x_0 = x_1 ;
    x_1 = x_0-   (((x_0*x_0)-n)/(2*x_0)) ; 



    }


    return x_1 ; 

}


int main(int argc, char** argv) {


    for(int i = 1 ; i < 15 ; i++){
        double z = i*i ; 
        cout<<"sqrt["<<i*i<<"] = "<<sqrt(z) << endl ; 

    }



    return 0;
}

and it would give me the wrong answers so after doing some research I found out that by changing the while loop condition to:

while(( x_1 - x_0 > pres || x_1 - x_0 < -0.0001 ))

it fixed it and gave me the correct answers

so my question is why do I need the

|| x_1 - x_0 < -0.0001

in the while loop ?

[sepp2k]

You need it because you don't know whether x_1 is greater or less than x_0. If x_1 is less than x_0, then x_1 - x_0 will be negative and thus less than pres even if x_1 and x_0 are far apart.

[mike_2000_17]

As sepp2k says, the problem is that the difference x_1 - x_0 could be negative, but yet large in magnitude. So, the right condition is to use the absolute value of the difference, as so:

while( fabs(x_1 - x_0) > pres )

or, equivalently, this or-expression:

while( (x_1 - x_0 > pres) || (x_1 - x_0 < -pres) )