Computers are meant to compute things. Finding square root is a very basic algorithm which can be coded in basically 3 ways :
All 3 ways are based on the Guess and check method A.K.A Exhaustive Enumeration.
>1. Brute force method :
In this method we test all the possible values and test them .
2. Bisection Search :
By cutting the problem into the half after every iteration. This is much more effective then brute force method which we will see later in this post.
3. Newton-Raphson method :
This method is based on the formula given by sir newton that if, g is a guess of a root of polynomial then,
g= g – g(x)/g'(x)
is a better guess.
We will be using phython to code the algorithms because it is most easy to understand.
Brute force method
The pic shows the algorithm of brute force method and also counts the steps taken to find the square root.
Output of the above code is :
As you can see the square root of 255 was approximated to 15.9685 , which is pretty close but the guesses made by the computer were 159685, which is pretty large.
This is the drawback of this method.
Bisection Search method :
Algorithm of bisection search method is shown in the pic, which also shows the number of steps.
The output of the above code is given below.
So, this also approximated the answer pretty well. But look at the number of steps, just 12. Compare this to the previous result.
Surely, this method is much better and faster but we can get much better results using the next method.
Newton-Raphson method :
The algorithm of this method is shown in the pic, along with the number of guesses made by the computer.
The output of the above method is given below. Look at the number of guesses taken and the accuracy of the result.
As this method is clearly the fastest of all. And took only 6 steps to guess the pretty accurate value.
Leave a Reply