## Guess and Check Algorithm

As the term suggests, first, we make a guess, then we check against a known condition (depending on the problem). We repeat this in a loop until we have got the answer.

We have a problem at hand i.e. to find the square root of any number.

Before we jump to the perfect solution let’s try to find the solution to a slightly easier problem. How about finding the square root of a perfect square. Numbers like 4, 9, 16, 25 … are perfect squares.

1

2

3

4

5

x = int(raw_input('Enter a perfect square : '))

guess = 0 # Our guess answer

while guess**2 < x:

guess += 1 # Shorthand for guess = guess + 1

print('Square root of ' + str(x) + ' is ' + str(guess))

Analysis of the above code:

- We declare
`guess`

as our answer and initialize it as`0`

- We continue the loop as long as the square of
`guess`

is less than`x`

- As soon as the square of
`guess`

equals or exceeds`x`

we break the loop and print the value of`guess`

Try it out on numbers such as 25 or 144 or any other perfect square.

Let’s write a better version that can guess the square root of any number. There’s one python built-in function we are going to use in this and it’s better to see how it behaves before we dive into the code.

`abs()`

- Returns the absolute value of any number. You all like to see examples, don’t you?

Now, we are good to go!

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

x = int(raw_input('Enter a number : '))

guess = 0.0 # The guess answer

epsilon = 0.01 # Used for accuracy. See the condition in While Loop

step = epsilon**2 #used to increment our guess 'ans'

total_guesses = 0

# We will understand this condition during code analysis

while (abs(guess**2 - x)) >= epsilon:

guess += step

total_guesses += 1

print('Total guesses were ' + str(total_guesses))

if abs(guess**2-x) >= epsilon:

print('Failed on square root of ' + str(x))

else:

print(str(guess) + ' is close to the square root of ' + str(x))

Analysis of the above code:

`epsilon`

is a variable that will help us in checking the condition whether we are close to our answer`step`

is variable by which we will increment our`guess`

inside the loop- The condition in the while loop checks if our guess is close to the answer. For instance, if we were to find square root of 16 and if our guess is 4 then
`guess**2-x`

results into`4**2 - 16`

i.e. 0. Here, we are simply trying to get as close as possible to the final answer, so are simply checking if the error margin is not more than the value of`epsilon`

Let’s test this code on several numbers.

How about trying some really large numbers.

How do I find square root of very large numbers? As large as 1000000000! There is always a scope of optimization. It is suggested to read about Binary Search before proceeding further.

## Efficient method to find Square Root of a number using Guess and Check algorithm

1

2

3

4

5

6

7

8

9

10

11

12

x = int(raw_input('Enter a number : '))

epsilon = 0.01

left = 0

right = x

guess = (right+left)/2.0

while abs(guess**2 - x) > :

if guess**2 < x:

left = guess

else:

right = guess

guess = (right+left)/2.0

print guess

Try to find square root of 1000000000, it will run way faster than the previous code. There are cases when this code will fail, cases when x is a fractional number between 0 and 1 or when x is negative. If you’re curious, do post a fix for that in comments.

Up next is one of the most important techniques of programming, Recursion.

Note: This is a part of what I learned in an online Open Course Ware offered by MIT on edX. Its for my personal reference & also for those who would like to revisit the course.