Python Programming

Step 2: Design an algorithm to solve the problem

You now have the problem formulated clearly in your head (or on paper). Now, you are ready to design your recipe to estimate the square root of a number.

Now, think for a bit. What is the stupidest, most naive way you can think of to estimate the square root of a number?

Nothing clever is needed. Maybe something that uses simple brute force?

Here is one idea. While it is not too easy to find the square root of a number $n$, it is very easy to compute the square of a number (just multiply a number by itself!) So you can now reframe the problem as the task of searching for a number that, when squared, is approximately $n$!

How do you go about searching for the mysterious number? One possible solution: go through all floating point numbers from $0$ to $n$, multiply the number by itself, and if the result is close enough to $n$, then you’ve found the square root of $n$!

Simple enough?

Now think more carefully. How would you instruct the computer to do this?

Obviously, you will need a while loop to go through the numbers $0$ to $n$.

But then you cannot possibly check all floating point numbers! (e.g. 4.9070342402349120123905)

So what can you do?

One way is to trade off accuracy of your estimate for efficiency.

So you can for example check only up to a certain number of decimal places (e.g. 4.9000071, 4.9000072, 4.9000073, etc.). Of course, if you chose too few decimal places, you might miss some possible solutions.

And when you multiply the number by itself, and if it is ‘close enough’ to $n$, then you can assume you have your answer. How do you decide whether a number is ‘close enough’? I will leave this up to you!

Now, design your algorithm. Think about the basic “building blocks” you have learnt so far - statements (and all its components), selection, repetition.

One thing you might have to think carefully about is how to exit the loop once you have found the square root. Remember to design your algorithm to get around this.

Write out your pseudocode, or make your algorithm visual by drawing a flowchart or whatever diagram or doodle that suits your fancy. You can even just sketch out an example of how the algorithm searches for a number and stops. Your choice - I am not bothered.

Make sure you have finished designing your algorithm on paper (or equivalent) before proceeding further!