Newton & Square Roots
Tags: computerscience, algorithms
Published: 2020-11-08 14:43:50

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<sup>2</sup> - 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)**
![](https://abhimanyutimes.com/assets/img/newton_img2.png)
We start by choosing an arbitrary value **x<sub>1</sub>** as our starting point<sup>[1]</sup>. 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 **x<sub>2</sub>**.  
![](https://abhimanyutimes.com/assets/img/newton_img3.png)  

3. Repeat _step 2_ for point **x<sub>2</sub>** to obtain **x<sub>3</sub>**. You must have noticed that with each iteration we are nearing the roots of the quadratic equation. Slow and steady!
![](https://abhimanyutimes.com/assets/img/newton_img4.png)
_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<sup>2</sup> - 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<sup>th</sup>** and **(N+1)<sup>th</sup>** iteration.

- For any point **x<sub>N</sub>**, by using the equation of line we can get:
**f'(x<sub>N</sub>) = (f(x<sub>N+1</sub>) - f(x<sub>N</sub>))/(x<sub>N+1</sub> - x<sub>N</sub>)**
[_f'(x)_ being the slope at point _x_]  


- Putting **0** for y coordinate at point **x<sub>N+1</sub>** where tangent crosses x-axis we get: 
**f'(x<sub>N</sub>) = (- f(x<sub>N</sub>))/(x<sub>N+1</sub>- x<sub>N</sub>)**  


- Rearranging the terms & putting **f'(x) = 2x<sub>N</sub>** we have our final expression: 
**x<sub>N+1</sub> = (x<sub>N</sub> + N/x<sub>N</sub>)/2**


![](https://abhimanyutimes.com/assets/img/newton_img5.png)
> **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!