CODEWITHSUNDEEP
c++recursion
zspar
zspar

Reputation: 23

C++ Square Root with recursion

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;
}

Upvotes: 1

Views: 3176

Answers (4)

Paul Floyd
Paul Floyd

Reputation: 6946

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.

Upvotes: 0

Josh Simani
Josh Simani

Reputation: 107

I see two fundamental errors that should be fixed first:

  1. Your main function doesn't have a return. You should place return 0; at the end of your main function before the last }.

  2. 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.

Upvotes: 0

1201ProgramAlarm
1201ProgramAlarm

Reputation: 32727

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.

Upvotes: 1

Vlad from Moscow
Vlad from Moscow

Reputation: 311126

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 );

Upvotes: 2

Related Questions