Member Avatar for Member #866461

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 ?

Edited by Member #866461
  • 3 Contributors
  • 2 Replies
  • 1K Views
  • 26 Minutes Discussion Span
  • Latest Post Latest Post by mike_2000_17

Dani AI

Generated

Short explanation tying the posts together and a more robust suggestion.

As discovered, the sign of (x1 - x0) can flip from iteration to iteration, so a simple > pres test only detects when x1 is larger than x0 by more than the tolerance. and are correct that the magnitude of the change must be compared instead. For production-grade code it is better to use a relative test and a safety cap on iterations so the stopping criterion works for very large and very small inputs and cannot loop forever.

A practical checklist and a compact implementation pattern:

  • Do not name the function sqrt (it hides std::sqrt).
  • Return NaN for negative inputs or document complex handling.
  • Start with a nonzero initial guess (for n < 1 use 1.0).
  • Use a relative change test such as abs((next - cur) / next) < tol, guarding against next == 0.
  • Set a maximum iteration count and verify result is finite before returning.

Example (compact, robust pattern):

#include <cmath>
#include <limits>

double newton_sqrt(double n, double tol = 1e-12, int max_iter = 100) {
    if (n < 0.0) return std::numeric_limits<double>::quiet_NaN();
    if (n == 0.0 || n == 1.0) return n;
    double x = (n >= 1.0) ? n : 1.0;
    for (int i = 0; i < max_iter; ++i) {
        double next = 0.5 * (x + n / x);
        if (std::abs((next - x) / next) <= tol) return next;
        x = next;
    }
    return x;
}

Notes: std::sqrt from <cmath> is usually faster and more accurate; Newton is useful for learning or custom numeric control.

Recommended Answers

All 2 Replies

Member Avatar for 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.

Member Avatar for 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) )
Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.