# Newton & Square Roots
The web is an interesting place, it humbles you down and shows how little you actually know. While hitchhiking through the hyperlinks, I had one such realization recently.
What if I ask you to calculate the square root of a number? Depending upon your background you are likely to come up with a variety of solutions. Let me talk about that specific fraction of you who will be interested in churning out code for doing so. _[No, sqrt()]_
_Binary Search_ seems to be a valid and intuitive approach, after all, we can easily discard half of the search space in each iteration. But I want you to hold that thought and glance over this small snippet below.
```cpp
double sq(double num)
{
double xn = num/2;
while(abs((xn*xn)-num)>eps) //eps is precision
{
xn = (xn + num/xn)/2;
}
return xn;
}
```
Magical isn't it? When I first looked at this, I was really startled by the elegance of this solution. So what is it and why does it work?
## Sweet Mathematics
You just witnessed the glamour of ***Newton Raphson*** method.
In simple terms, it is a way to quickly find a good approximation for the roots of a real-valued function **f(x) = 0**.
This is our cue, square root for a number can be minimally represented by solving for the roots of **f(x) = x^2- N**, where *N* is the number we have to find the root of.
That is all cool! But how does it actually work? Let's look at the simple math behind this:-
1. Consider a general function: **y = f(x)**
We start by choosing an arbitrary value **x1** as our starting point[1]. For our specific case, we can choose **N/2** as our starting point and can safely discard values greater than that from the candidature of **√N**.
2. Now let's draw a tangent (Differential) to the curve at that point and mark its intersection with the x-axis. Let's call this **x2**.
3. Repeat _step 2_ for point **x2** to obtain **x3**. You must have noticed that with each iteration we are nearing the roots of the quadratic equation. Slow and steady!
_Depending upon the precision, you can decide upon the number of iterations required._
## Formal Expression
Let's try to workout an elegant formula for **f(x) = x^2 - N** which will get us the compact code we saw in the beginning. Please note that we are aiming to get a relation between **N** and **(N+1)** iteration.
- For any point **xn**, by using the equation of line we can get:
**f'(x[n]) = (f(x[n+1]) - f(x[n]))/(x[n+1]- x[n])**
[_f'(x)_ being the slope at point _x_]
- Putting **0** for y coordinate at point **x[n+1]** where tangent crosses x-axis we get:
**f'(x[n]) = (- f(x[n]))/(x[n+1]- x[n])**
- Rearranging the terms & putting **f'(x) = 2x[n]** we have our final expression:
**x[n+1] = (x[n]+ N/x[n])/2**
> **Visualising Newton Raphson method for N = 10000**
## Notes
[1] For the sake of simplicity, I have omitted the details about choosing the initial value which plays a crucial role in more complex functions.
_Special thanks to [AMSI](https://amsi.org.au/) for facilitating illustrations_
***
>If you liked this post, you can find more by:
>Following me on **Twitter**: [@abshekha](https://twitter.com/abshekha)
>Connecting on **LinkedIn**: [abhimanyubitsgoa](https://www.linkedin.com/in/abhimanyubitsgoa/)
>Visiting my **website**: [https://abhimanyutimes.com](https://abhimanyutimes.com)
***
Thanks for reading!