Loop Example: Iteration (Babylonian Root)

Home, Up: Loop and Script Examples

In this example:

Iterations, REPEAT, PROMPT, $loop, GOTO 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 phones, 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 to variable $z, 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 hardly changes anymore from one step to the next -- then our estimate will have become our result -- but this really calls for using 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, at the end of the loop, makes the value of $r the calculation result (other than this line, there is no calculation line in the script).

Let's run our script in an infinite loop:

Let's check if our result is correct:

? SQ

= 99

So, yes, it is! (Also, if we try 99 SQRT we get 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 saying DO 100 :: _babroot instead of the infinite loop _*babroot,

- or by adding a line IF I 100 == THEN ABORT to the script.

Also, you may want to observe the iteration process, for instance in our example by adding the line SHOW $r.

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.

Though it could be done differently, the easiest way to solve the problem is to rewrite the script so that the iteration is done in a GOTO loop.

The iteration is done as above. The expression IF $r SQ $z // is true (that is, not zero) as long as there is a difference between the square of our estimated root and the number whose root we seek (remember, the // operator returns 0 if its result, a minus b divided by b, is smaller than 1e-16):

You can call this script directly for a single calculation,

? _babroot

or in an infinite loop, for any number of calculations until you enter 0:

? _*babroot

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.

What we do not have here is the information how many steps the iteration needed -- if you want to know this, you have t use your own counter variable:

This $steps counter variable could also be used as a safeguard against the loop running indefinitely in case that the iteration does not converge, since unlike with a DO loop we cannot set an a priori limit of passes for a GOTO loop -- the line

IF $steps 100 >> THEN ABORT

somewhere inside of the GOTO loop would abort the script after 100 passes of the loop (though of course other iteration tasks might require much higher limits).

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