Square Root Approximation Techniques
In this article let’s look at some square root approximation algorithms and techniques. We will start with a basic brute force approach and gradually improve its efficiency and sophistication.
In the real world, we will never need to write an algorithm to calculate the square root of a number, as it is handled by the basic math package/module of almost all predominant programming languages.
Then why would we need to know it? one might ask. Well, knowing this will deepen our understanding of how computers work with numbers in general and fractions in particular. And this newfound understanding will help us write code that is resilient to floating point approximation-related bugs.
Also, this exercise of arriving at a quite sophisticated solution by starting from a trivial brute force approach will help us practice the art of thinking like a programmer.
Why Just Approximation?
At this point, one might wonder, why just approximate the square root of a number and not find the accurate result?
A square root calculation is one of the many problems, that would expose the limitations of computing systems.
For instance, the square root of 2 is an irrational number and there is no way a computer, or a human for that matter, could express the answer as a fraction. Hence, the square root of 2 will just be an approximation with a precision good enough to perform the intended calculation with a negligible offset.
There are many numbers whose square roots are irrational. So we can only approximate the results in such cases.
Exhaustive Enumeration:
This is the most naive way to approach the problem. Often referred to as the “Brute force approach”.
From a problem-solving perspective, this would be the ideal approach to start thinking about a solution and then later optimize it as we progress. So let’s start here.
As the name suggests, we try to arrive at a result by checking all the possible solutions until we get the right answer or until we run out of options to check.
