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.

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) = x2 - 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 towards 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) = x2 - N which will get us the compact code we saw in the beginning. Please note that we are aiming to get a relation between Nth and (N+1)th iteration.

  • For any point xN, by using the equation of line we can get:

    f’(xN) = (f(xN+1) - f(xN))/(xN+1 - xN) [f’(x) being the slope at point x]

  • Putting 0 for y coordinate at point xN+1 where tangent crosses x-axis we get:

    f’(xN) = (- f(xN))/(xN+1 - xN)

  • Rearranging the terms & putting f’(x) = 2xN we have our final expression:

    xN+1 = (xN + N/xN)/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 for facilitating illustrations