Square root approximation with Newton's method

Question

I designed a program that calculates the square root of a number using Newton's method of approximation that consists of taking a guess (g) and improving it (improved_guess = (x/g + g)/2) until you can't improve it anymore:

#include <iostream>
#include <iomanip>
using namespace std;

template <class Y>
Y sqrt (Y x)
{
    double g (1), ng;
    while (true) {
        ng = (x/g + g)/2;
        if (g != ng) g = ng;
        else if (g == ng) break;
    }
    return g;
}

void menu()
{
    double x, g;
    string a = "";
    do {
        cout << "Enter a number to get the sqrt of: ";
        cin >> x;
        g = sqrt(x);
        cout << "The result is: " << setprecision(100) << g << endl;
        cout << "Result^2 = " << setprecision(100) << g*g << endl;
        cout << "\nDo it again ? <y/n> ";
        cin >> a;
        cout << endl;
    } while (a == "y");
}

int main()
{
    menu();
    return 0;
}

Can you see any way to improve this ? Like in the "do it again" part, I just couldn't use y/n...

Answer 1

Good comments have been posted already but no one explicitly pointed out that the if (g == ng) doesnt bring anything in the function and :

while (true) {
    double ng = (x/g + g)/2;
    if (g != ng) g = ng;
    else if (g == ng) break;
}
return g;

can be written :

while (true) {
    double ng = (x/g + g)/2;
    if (g != ng)
        g = ng;
    else
        break;
}
return g;

or even better :

double g (1);
while (true) {
    double ng = (x/g + g)/2;
    if (g == ng)
        break;
    g = ng;
}
return g;

which can just as easily be written :

while (true) {
    double ng = (x/g + g)/2;
    if (g == ng)
        return g;
    g = ng;
}

Answer 2

Looks fairly good over all, but a few things jumped out at me. Please note that the stylistic ones are opinion based.

---

Make sure you don't get into a habit of using namespace std;. It's acceptable in some places, but it can form a bad habit very easily. Your code is a perfect example of this since your sqrt will conflict with std::sqrt if you include cmath or math.h. A lot more discussion on the matter can be found here.

---

If you're not going to put your function in a namespace, I would avoid calling it sqrt. In fact, unless you have a compelling reason, it's best to avoid names from the standard library in general.

---

I would leave a blank space after your header lines. The typical format is:

#include "local1.h"
#include "local2.h"

#include <blah1>
#include <blah2>

// stuff here

Also, I would consider alphabetizing the headers. When there's a long list of headers, it can help make quick mental scanning easier.

---

You forgot to include string.

---

Your c variable in sqrt isn't used.

---

I don't like the use of the constructor form initialization of primitives. I would stick with plain old equals.

Also, it's fairly typical to define one variable per line when values are being assigned during declaration.

double g = 1;
double ng;

---

I'm not quite sure why sqrt is templated. By using doubles internally, you've basically restricted it to doubles. If you're going to make it templated, use the templated type all the way through.

---

Y is a bad typename. Use something more descriptive like FloatingPoint or Number.

---

Consider taking x by const reference in sqrt. If an expensive-to-copy class is used as the template parameter, you're causing an unnecessary copy since x is never modified.

---

In menu, you should check if reading in a double was successful:

if (std::cin >> x) {
    // Use x
} else {
    std::cerr << "Invalid value provided\n";
}

---

Try to declare variables as close to usage as possible. For example, your g = sqrt(x); could be double g = sqrt(x);. Seeing a giant list of variables declared at the top of a function is overwhelming. If they're defined where they're used, it's much simpler to see their relation to the overall code.

---

If you're using C++11, avoiding naming types except where necessary. This will ease future change of type. For example, imagine that at some point you want to use some kind of Complex class instead of a built in double. If you only name the type for the input x and use auto else where, you'll only have to change one thing (provided the class overrode operator>> for istreams). You can read more about this here.

---

When it's not possible for the program to return a non-0 exit code, I like to omit it. This signifies at a simple glance that the program always exits with a success code.

Answer 3

I'm not enthused about the your sqrt template.

First of all, there may easily be inputs for which it won't terminate--once you get really close to an answer, Newton's method can sometimes "oscillate", switching between a couple of different values that are nearly (but not quite) equal. You rarely want to compare floating point numbers for strict equality anyway--you normally want to test whether the difference is below some delta.

Second, I prefer to avoid the while (true) ... if(something) break; structure when at all reasonable (and I think it is here).

Finally, 1 is rarely a good choice for your first guess at the root. You'll almost certainly gain at least a little speed by using a better initial guess.

double my_sqrt(double x) {
    static const double delta =.00001;
    double g = x / 2;
    double ng;
    while (fabs(g - (ng = (x / g + g) / 2)) > delta)
        g = ng;
    return g;
}

Note that I haven't tried to use a particularly good value for delta here. It's adequate for numbers in the vicinity of 1, but if (for example) you were trying to find the square root of 1e-100, it would clearly be seriously wrong. For real use, you'd typically want to estimate the magnitude of the result, then choose delta to be small enough to give (for example) 10 decimal digits of precision.

Two other minor points:

1. asking for a precision of 100 isn't likely to accomplish much with most computers. You'd need some sort of extended precision library to get even close to that precision on most computers (around 20 digits is the limit with most typical hardware).

2. While it's pretty common to try to stuff too much functionality into main, in this case I think you've gone a little too far the opposite direction. For most practical purposes, your main does nothing. This mostly requires the reader to chase through an extra level of function calls, without accomplishing anything really useful.