Loop Example: Iteration (Babylonian Root)

Home, Up: Loop and Script Examples

In this example:

Iterations, PROMPT, $loop, Loop Within a Loop.

Hypatia is an excellent tool for performing iterative calculations -- to demonstrate this, let us calculate square roots using the "Babylonian method," which was known and used in antiquity.

(Obviously this has little practical value for us when we could just use the SQRT operator or the calculator app on our cell phone, but is a good example to show how Hypatia can be used for iterative calculations which, of course, can be more complex and more useful.)

The mathematics behind it are in fact a bit more sophisticated, but the principle is this:

When z is the number whose square root you want to draw, you start with an estimate. Then you divide z by that estimate, take the arithmetic mean of your estimate and that quotient, and use this as your new estimate. Let’s do this for the number 99 (as always, the question mark at the beginning of the line is Hypatia's input prompt, you do not type it).

First we assign the number whose square root we seek, then we enter a first estimate (it does not have to be anywhere close) -- this becomes the value of $:

The calculation line after we have entered the estimate calculates the next estimate: the mean value of $ (the estimate) and the quotient $z divided by that estimate $.

The result becomes the new value of $ and thus our new estimate.

Now we can repeat this -- each new iteration uses the previous result $ as its starting point and gets us closer to the desired square root of z:

? REPEAT

= 10.6309782608696

(REPEAT repeats the last calculation line, which is $ $z $ / MEAN.)

And again ...

? REPEAT

= 9.97169280100377

We could keep doing this until the result stays hardly changes anymore from one step to the next -- then our estimate will have become our result -- but it's far more elegant to use a script and a loop. Let's call the script babroot.

When the loop starts, it prompts us for the number whose root we want, and for an estimate. Instead of using the result variable $ for our estimates (and ultimately for the result, the square root of $z), we use a variable $r.

The iteration is done by the line $r = $r $z $r / MEAN

The last but one line $loop = $r SQ $z // is our exit condition. The operator // returns the "relative difference" of a and b -- a minus b divided by b -- in this case, between the number whose root we seek and the square of our current estimate. The closer we get to the desired result, the smaller this relative difference becomes.

The loop is ended after the loop variable $loop is set to exactly zero. The square of our estimated root may never exactly match $z, but // has a threshold built in: when its absolute value is less than 1e-16, it returns zero.

The last line is a calculation line that sets the result to the alue of $r at the end of the loop.

Let's run our script in an infinite loop:

Let's check if our result is correct:

? SQ

? 99

(Also, 99 SQRT gives the same result!)

By the way, if you enter a negative number of which you want the root drawn, the iteration will not converge, and the script will run until the maximum number of loops has been reached -- one hundred thousand by default, but it could be as high as ten million. In our example we could avoid this by adding a line IF $z IS-0 THEN ABORT after PROMPT, but as a general rule, if you are not sure about how your iteration behaves it is a good idea to limit the possible number of passes.

There are three ways in which you can do that (for instance, to 100): with the command MAXLOOP 100, by using DO 100 :: _babroot instead of the infinite loop _*babroot,

When we want to calculate another square root we have to run the script again, which is easily done -- press Arrow Up three times and press and ENTER -- but as a challenge, let's write the script so that it can do one calculation after the other until we enter 0, as was the case with the Body Mass Index example.

This is not trivial, though, because the iteration is done in a loop, and for more than one calculation we'd have to run this loop in a loop, which Hypatia does not allow (this is also why we cannot use REPEAT -- it would call the babroot script but not in a loop -- _babroot instead of _*babroot -- so it wouldn't work).

We have to modify our script in two ways: We cannot use the I1: condition to prompt for user input and start a new iteration process -- instead, we have to use our own variable -- and we cannot use the $loop = 0 condition to display the result and exit the loop.

Also, out of curiosity, we want to konw how many iterations were needed to arrive at the result -- for this we use a counter variable $iterations.

(The loop index I will keep growing, but as long as it doesn't hit the maximum, by default one hundred thousand, it doesn't concern us.)

This is how the script could do multiple iteration loops: At the beginning of a new calculation user input is requested, and the variable $new and the iterations counter are set to zero.

When we are satisfied with our result (the same criterion as above) the counter variable and the result variable are displayed with the command SHOW $iterations $r, and $new is set to 1 so that a new calculation can begin:

When you end the loop by entering 0, the variable $r holds the latest result (Hypatia's result variable $ was never updated in this script, because there is no calculation line -- remember, variable assignment lines are not calculation lines!)

By entering $r as a calculation line its value becomes the value of $, it gets written to hy in the currently chosen format, and you can copy it to the Windows clipboard with COPY.

Home, Up: Loop and Script Examples, Prev: Loop Example: Rectangles, Next: Loop Example: Nested Loops