C++ Question

Newton-Raphson using recursion in C++

I have written the following code to calculate square roots using Newton's method, but it overflows every time I run it. I have tried checking it myself but I didn't find any mistake. Can you guys help me out?

double root(double n,double init){
if(fabs(init*init-n)<=0.00001){
return init;
}else{
init=(init*init-n)/2*init;
return root(n,init);
}
}
int main()
{
double a;
cout<<"Enter any number to get its square root: ";
cin>>a;
cout<<"Square Root of "<<a<<" is: "<<root(a,2);
return 0;
}

Answer

So your issue is two-fold. Firstly, your Newton method is slightly off (which is a bigger issue). Secondly the way you are implementing it is leading to overflow.

Issue 1 (bigger issue):

The other answers seem to ignore this even though this is the bigger issue. Computers can handle the overflow from squaring for small numbers like when calculating the square root of 9, but your method doesn't work even for them. This is because, as I mentioned in the comment, your Newton method is slightly off.

You should be using a plus instead of a minus in this line (try rederiving to see why):

init=(init*init+n)/(2*init);

Derivation:

x_{k+1} = x_k - f(x_k)/f'(x_k)
        = x_k - ((x_k)^2 - n)/(2x_k)
        = x_k - 1/2*x_k + n/(2x_k)  // note the + here
        = 0.5*x_k + 0.5*n/x_k
        = 0.5*(x_k + n/x_k)

where x_k is your init variable.

Issue 2:

Doing init*init can cause the numbers to grow too quickly and overflow (there is more error in bigger numbers). You can algebraically rewrite this as:

init=0.5*(init + n/init);

Putting this together:

#include <iostream>
#include <cmath>
using namespace std;
double root(double n,double init){
    if(fabs(init*init-n)<=0.00001){
        return init;
    }else{
        init=0.5*(init + n/init);
        return root(n,init);
   }
}
int main()
{
    double a;
    cout<<"Enter any number to get its square root: ";
    cin>>a;
    cout<<"Square Root of "<<a<<" is: "<<root(a,2);
    return 0;
}
Comments