C++ Square Root with recursion

Question

My square root program for some reason gets an answer that is a little off from what it should get for most inputs. I'm not sure why this is. Only certain inputs are wrong. I also get a segmentation fault at then very end after the answer is given and am not sure why that is either.

#include<iostream>
#include<cmath>
#include<cfloat>
#include<string>
#include <cstdlib>
using namespace std;

//declare sqroot function calls recursive function newton
double sqroot1(double num );
double newton(double num, double guess);
int main(int argc, char **argv)
{

    for( int i = 0 ; i < argc ; i++)
    {
       cout<<"sqroot("<<argv[i+1]<<") is "<< sqroot1(atoi(argv[i+1]))     <<endl;
    }
}

double newton(double num, double a)
{
    if ((abs(a*a - num) <= FLT_EPSILON))
    {
        return a;
    }
    else
    {
        newton(num, (a+num/a)/2 );
    }
}

double sqroot1(double num)
{
    double sqrt = newton(num,num/2);
    return sqrt;
}

Enable all warnings and see what the compiler tells you. And see [Why is “using namespace std” considered bad practice?](http://stackoverflow.com/q/1452721/995714) — phuclv, Nov 19 '16 at 04:27
What are some values that give bad square roots, and what values are you getting for them? — 1201ProgramAlarm, Nov 19 '16 at 04:36

score 2 · Answer 1 · answered Nov 19 '16 at 04:20

The function has undefined behavior because you forgot to place the return statement

double newton(double num, double a)
{


    if ((abs(a*a - num) <= FLT_EPSILON))
    {
        return a;
    }
    else
    {
        newton(num, (a+num/a)/2 );
       ^^^^^^^^^^^^^^^^^^^^^^^^^^^
    }


}

there must be

    return newton(num, (a+num/a)/2 );

score 1 · Answer 2 · answered Nov 19 '16 at 04:53

You're getting the crash because you try to access argv[argc], which is past the end of the argv array.

Your numbers are likely off because you're comparing with FLT_EPSILON, which is for float values. DBL_EPSILON is used for doubles. Comparing with either of those is not the right approach for this problem, though. You need to check against a difference that is scaled relative to your a value.

score 0 · Answer 3 · answered Nov 19 '16 at 05:50

I see two fundamental errors that should be fixed first:

Your main function doesn't have a return. You should place return 0; at the end of your main function before the last }.
You are trying to access the argv[argc], which doesn't exist. The last existing element in that array is argv[argc - 1]. Try changing your loop statement so that it doesn't try to read in that non-existent part of the array.

Paul Floyd · Answer 4 · 2017-12-06T08:52:57.473

Adding to 1201ProgramAlarm's answer, why is the following so bad?

if ((abs(a*a - num) <= eps))

Let's say eps is 1e-15, a bit bigger than DBL_EPSILON. Well, if a is even moderately large (something like 5 or greater) then the unit in the last place (ulp) of a*a is bigger than eps and the condition can only be true if a*a == num. There's a risk, with rounding, that this won't be reached and you end up with infinite recursion and a crash.

Now let's say that num is very small such that for the initial guess

abs(num/2*num/2 - num) <= eps

So for instance, sqroot1(1e-20) will evaluate

abs(1e-40/4 - 1e-20)   <= 1e-15

which is true and you will get 5e-21 as the square root of 1e-20. This is atrocious precision.

C++ Square Root with recursion

4 Answers4