Scratching out the square root of 2

Square roots

Finding the square root of some numbers is easy. Take 9:  √9 = 3. Easy. For other numbers it’s a little harder – what i √2 for example?

It turns out that √2 is irrational, meaning that it can’t be written in the form y/x, where x and y are integers. However, that’s not to say you can’t find integer values for x and y that makes y/x close to the actual value of √2. How close is close? This answer is that depends on how patient you are and, if you’re using a computer, how many digits it can work with. If you’re determined you can get as close as you like – but you’ll never find them all!

So how do we find an approximation to √2? There are many methods and some are better than others. One remarkable method is the so-called ladder of Theon, which is attributed to Theon of Smyrna and dates from about 140AD, so it’s well over 1,800 year old! It’s not the fastest method but it is very simple to implement and gives us access to one of the earliest computational algorithms documented.

An algorithm is a bit like a recipe which, when followed, gives the desired result. Many algorithms have an initialisation section, which is performed once to set thins up, and a repeated section, which is repeated until a desired outcome is achieved. Because this latter section is repeated until a desired outcome is achieved, this algorithm is known as an iterative one. Theon’s ladder algorithm works like this:

Initialisation:

Set x =1

Set y = 1

Repeat:

Update x so that the new x is given be the sum of the old x and the old y:

x_new = x_old + y_old

Update y so that the new y is given by the sum of the new x and the old x:

y_new = x_new + x_old

Finding y/x gives you the approximation to √2, and the more you repeat the “repeated” section, the closer you get!

Let’s look at a few iterations to see how it works

Iteration	x	y	y/x
Initialisation	1	1	1
1	xold = 1, yold = 1, so xnew is 1+1 = 2	xnew = 2, xold = 1, so ynew is 2 + 1 = 3	3/2 = 1.5
2	xold = 2, yold = 3, so xnew is 2+3 = 5	xnew = 5, xold = 2, so ynew is 5 + 2 = 7	7/5 = 1.4
3	5 + 7 = 12	12 + 5 = 17	17/12 = 1.41666…
4	12 + 17 = 29	29+12 = 41	1.41379…
.	.	.	.

Do it with a spreadsheet

Now doing this by hand is a bit tedious for humans, but it’s the kind of thing computers are very good at. You can easily set this up on a spreadsheet. The formulae are:

This is easy to produce – type in rows 3 and 4, then copy row 4 down as far as you like. On the spreadsheet’s normal view you’ll see:

Notice how the value in column D homes in on a value. This value is the approximation to. √2 Using jargon, the value is converging on the result.

Do it with Python

The above is all good and fine but what if you want to program a computer to do this? To do this, you need to write some code. In Python the code to work through Theon’s ladder might look something like this

The xold, yold, xnew and ynew variables are integers. To prevent rounding when calculating the quotient to get the result, the float command is used to tell Python that it should be expecting a real number.

The first few lines initialise the code. There is then a repeated section in the middle and some output at the end. Notice that, because this is code, we can write a stopping condition. In this case, keep going with the ladder until the result multiplied by itself is 2. It isn’t really, but computers only keep numbers to a finite accuracy – as far as the computer is concerned the answer is exact!

Also notice that after you have found the new values for x and y you use them to overwrite the old values. This ensures than when you go back and repeat the process, the xold and yold variables represent the very last update you made.

The output you might get from this Python is shown below.

Do it with Scratch

The above is what you expect from a coding language; you type in an incantation in the form of words and get the results. Can you code this with a visual language such as MIT’s Scratch (see http://scratch.mit.edu/)? Well, it turns out you can and Scratch’s building block approach is great for translating the algorithm into coding steps.

One possible solution is shown below – don’t worry if you can’t read this, there are enlargements below! This uses the same recycling of new and old x and y values as demonstrated in the Python example. You could of course change this so that the x and y values are stored in a list, which you update according to the rules of the ladder.

Notice that two variables and the list are displayed on screen

:       

The blocks to perform the initialisation are

This is called when the green flag is clicked. I have used “join” in the say block. This little trick makes the sprite say the value of a variable to a full number of decimal places rather than rounding it.

The repeating section is

This is called by pressing the space bar. Every time you do so, the x and y values are updated, another estimate is entered into the list and the cat sprite tells you what the computer thinks the last estimate squared is – when it’s 2, you’ve converged! Again notice that after you’ve updated the values of x and y, you use them to replace the old values so that when you repeat the blocks the latest values are used to construct the next values. You could avoid this by storing the x and y values as lists and looking up the last entries in the list.

Running the code gives

After 15 iterations you’re close but not there yet.

After 22 you’ve converged to the right answer as far as the computer is concerned.

What next?

• The code examples start with x and y set to 1. What happens if you set them to other values – does the algorithm still work? Hint: don’t set the initial x to zero. This asks the computer to divide by zero – an operation which generally upsets them!
• Change the rule for finding the new y value to be:y_new = x_new + 2*x_old. What number have you found the square root of now?
• What would be the rule to work out the square root of any number, N?
• Can you work out a three column version that calculates the cube root of 2?
  Hint:
  Start with x_new = x_old + y_old + z_old
  Update y so that the new y is given by the sum of the new x and the old x:
  y_new = x_new + x_old
  Update z so that the new z is given by the sum of the new y and the old y:
  _znew = z_new + z_old
  Calculate z/y
• Can you code a different algorithm that converges faster than the 22 or so that Theon’s ladder takes?