Newton-Raphson vs Bisection Search vs Brute force for finding square root of number.

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

brute force
Algorithm of brute force method to find square root.

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 :

Output of Brute force method
The pic shows the output of brute force method to find the square root of 255.
Look at the number of steps.

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.

Bisection Method
Bisection method to find the square root of a number.

The output of the above code is given below.

Output of bisection Search.
Output of bisection search . Look at the number of steps.

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.

Newton raphson method
Algorithm of newton raphson method.

The output of the above method is given below. Look at the number of guesses taken and the accuracy of the result.

Output of newton Raphson method
Ouptut of newton Raphson method. look at the number of guesses made by the computer.

As this method is clearly the fastest of all. And took only 6 steps to guess the pretty accurate value.

Advertisements

One thought on “Newton-Raphson vs Bisection Search vs Brute force for finding square root of number.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s