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
guessas our answer and initialize it as
- We continue the loop as long as the square of
guessis less than
- As soon as the square of
guessequals or exceeds
xwe break the loop and print the value of
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:
epsilonis a variable that will help us in checking the condition whether we are close to our answer
stepis variable by which we will increment our
guessinside 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
4**2 - 16i.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
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.