Here I keep a collection of visualizations for algorithms that compute Square root as I experiment with them. This page is presented as is and does not claim to be a complete guide on such algorithms. You can find the source code at GitHub
I came up with this algorithm myself based on my understanding of the square root definition. If you have y it is very easy to check if it is a square root of x. You just check if y*y == x.
So the algorithm starts with defining two values: y0 = 0 and y1 = x. The value sqrt(x) lies somewhere between y0 and y1. We simply perform Binary search on them until we narrow down y0 and y1 to y == sqrt(x) with an acceptable precision.
Very slow algorithm but it works and was fun to implement and animate.
Click the plot to set the x value.
The algorithm based on Newton's method is much more efficient and actually really clever. The thing about Newton's method is that it's not designed specifically for finding square roots. It's a method that finds roots of any function. (the root of a function f is a such value x that f(x) == 0)
So what you need to do given a value a the square root of which you want to find is to come up with such function f the root of which is equal to sqrt(a). That is f(sqrt(a)) == 0. A good instance of such function would be f(x) = x^2 - a. Once you've got such function you just need to apply the Newton's method on it and voilà! You found sqrt(a).
The idea of Newton's method is really simple. You start with a certain approximation x[0]. And you keep computing the next approximation x[i] = x[i-1] - f(x[i-1])/f'(x[i-1]) iteratively until you've reached an acceptable precision. f'(x) is the first derivative of function f(x).
Since the derivative of a function is basically the velocity of that function at a certain point by dividing by it and subtracting it we sort of move in an opposite direction trying to reach the zero. But I personally do not fully understand how it works yet.
In case of the function f(x) = x^2 - a the next approximation looks like x[i] = x[i-1] - (x[i-1]^2 - a)/(2*x[i-1]).
Click the plot to set the x value.
Source Code on GitHub | Font Libre Baskerville