CODEWITHSUNDEEP
c++math
blueperfect
blueperfect

Reputation: 15

How does this algorithm to calculate square root work?

I have found a piece of mathematical code to compute the square root of a real value. I obviously understand the code itself, but I must say that I badly understand the math logic of that algorithm. How does it work exactly?

inline
double _recurse(const double &_, const double &_x, const double &_y)
 
        { double _result;
 
          if(std::fabs(_y - _x) > 0.001)
            _result = _recurse(_, _y, 0.5 * (_y + _ / _y));
          else
            _result = _y;
 
          return _result;
        }

inline 
double sqrt(const double &_) 

       { return _recurse(_, 1.0, 0.5 * (1.0 + _)); }

Upvotes: 0

Views: 397

Answers (1)

user1196549
user1196549

Reputation:

Assume that you want to compute √a and have found an approxmation x. You want to improve that approximation by adding some correction δ to x. In other terms, you want to establish

x + δ = √a

or

(x + δ)² = x² + 2xδ + δ² = a

If you neglect the small term δ², you can solve for δ and get

δ ~ (a - x²)/(2x)

and finally

x + δ ~ (a + x²)/(2x) = (a/x + x)/2.

This process can be iterated and converges very quickly to √a.

E.g. for a=2 and the initial value x=1, we get the approximations

1, 3/2, 17/12, 577/408, 665857/470832, ...

and the corresponding squares,

1, 2.25, 2.00694444..., 2.0000060073049..., 2.0000000000045...

Upvotes: 2

Related Questions