The while loop tests the indicated boolean expression at the top of the loop and does not execute the loop if the condition is false. There are times, however, when one wishes to have the loop execute at least once in any case, and then to test the condition before continuing for a second pass. As indicated in section 1.9.1, this is achieved with the repeat loop construction. In Modula-2, as in many computing notations, the general form of this type of loop is:
REPEAT Statement Sequence; UNTIL Boolean Expression;
or diagrammatically as in figure 3.6:
Notice that the UNTIL concludes the statement sequence so that there is no END. There is also no DO. This type of loop repeats the enclosed statement sequence as long as the boolean expression is FALSE and then, when it becomes TRUE, control "falls out" to the next statement beneath. Some of the code in the examples above could have been written more efficiently. Instead of
again := TRUE;
WHILE again
DO
statement sequence;
WriteLn;
WriteString ("Do you want to do another one? ");
ReadChar (answer);
WriteLn;
again := (answer = 'Y') OR (answer = 'y');
END;
it is more efficient to write:
REPEAT
statement sequence
WriteLn;
WriteString ("Do you want to do another one? ");
ReadChar (answer);
WriteLn;
again := (answer = 'Y') OR (answer = 'y');
UNTIL NOT again;
Here is a simple problem from mathematics whose solution illustrates the use of the REPEAT statement and at the same time shows the necessity of careful planning and an intimate knowledge of the problem itself.
Write a program which will find the Greatest Common Divisor (GCD) of two given numbers.
When solving problems like this one, it is essential that the terms used in the question are clearly understood.
The Greatest Common Divisor (GCD) of two numbers is the largest positive whole number which divides evenly (without remainder) into both. If their Greatest Common Divisor is one, two numbers are said to be relatively prime.
For instance,
GCD (6, 8) = 2
GCD (24, 160) = 8
GCD (25, 16) = 1, so 25 and 16 are relatively prime.
GCD (2, 0) = 2 (every number divides zero)
A number of methods are commonly taught in Junior High School mathematics to solve such problems. To illustrate, consider the following method for determining the Greatest Common Divisor of 432 and 1800.
1. List all the divisors of 432 and 1800.
2. Examine the two lists and select the largest number appearing in both.
Algorithm for listing divisors:
empty the list
set trial divisor to 1
repeat
divide number by trial divisor
if remainder is zero then
put trial divisor in list
put quotient in list
add one to trial divisor
until trial divisor is greater than the square root of the number
The latter provision is feasible since the algorithm adds both to the bottom and the top of the list simultaneously. Thus, once the square root of the number is passed on the way up, the top end contains all the divisors down to that point as well, and the process may be concluded.
Algorithm for selecting the largest number in two lists:
repeat
find the largest number in each of the two lists
if these are not equal then
discard the greater of these two numbers from its list
until the largest numbers in each list are equal; this is the GCD
For the example cited, this method produces the two lists:
432:1,2,3,4,6,8,9,12,16,18,24,27,36,48,54,72,108,144,231,432
1800:1,2,3,4,5,6,8,9,10,12,15,18,20,24,25,30,36,40,45,50,60,72,75,90,100,120,150,200,225,300,360,450,600,900,1800
Finally, examination of the lists for the highest number in both quickly produces 72 as the GCD.
There are a number of difficulties with this method. It uses the concept of square root, which is not very satisfactory when working with whole numbers. How to translate the "list" abstraction employed here into a computing notation is not at all clear. Neither is how to implement the idea of discarding an item from a list. Such difficulties cause one to consider another method, and this one too is taught in high school mathematics.
1. Factor the two numbers into products of primes.
2. Construct the GCD as the product of the largest common number of factors of each prime taken individually.
Thus, 432 = 24 * 33 and 1800 = 23 * 32 * 52
Examining the common factors gives the GCD as 23 * 32 = 72.
However, this method is even more difficult to implement as an algorithm and translate into a computing notation. It requires that the problem be refined into methods for determining primes, keeping a list of them, and maintaining lists of the prime factors of numbers, together with the appropriate exponents. Such a refinement will not be given here, as there is a better way. To see what that better way is, it is necessary to examine carefully the definition of a divisor.
We say that d is a divisor of x if there is a number m with x = d * m.
Thus, for two positive numbers x and y with a common divisor d, there would be numbers m and n with x = m * d and y = n * d. (There is always at least one such number, because 1 is a common divisor of all other natural numbers.)
To progress from this point requires a flash of insight. Suppose that x is the larger of the two numbers. Observe that
x - y = m * d - n * d = (m - n) * d
The latter expression gives the difference of the two numbers as a product of a natural number with their common divisor d. Put another way, this means that every divisor of the two given numbers is also a divisor of their difference. In particular, this is true of the greatest common divisor of the two:
either GCD (x, y) = GCD (x - y, y) OR GCD (x, y) = GCD (x, y - x) (1)
(depending on whether x > y or y > x)
It ought also to be evident that
If x = y then GCD (x, y) = x (2)
These two formulas help by reduceing the problem to that of finding the GCD of successively smaller pairs of numbers than the originals, until the pair is equal, at which point either is the GCD. A trace of this logic by hand for the earlier example produces:
GCD (1800, 432) = GCD (1368, 432)
= GCD (936, 432)
= GCD (504, 432)
= GCD (72, 432)
= GCD (72, 360)
= GCD (72, 288)
= GCD (72, 216)
= GCD (72, 144)
= GCD (72, 72)
= 72
This hand trace reveals that yet another simplification to the algorithm is possible. At one stage, the number 72 was subtracted several times in succession so what is left is really just the remainder after the larger number was divided by the smaller. For convenience, assume that the first number is the larger, and keep them in order throughout. That is,
GCD (x, y) = GCD (y, x MOD y) (1a)
(assuming always x > y and neither x nor y is zero)
Note that once the smaller number divides the larger exactly, the smaller is the GCD and the process can stop. With the properties (1a) and (2) it is possible to produce a refinement that is easy to render in computing notation that uses only comparisons and divisions, neatly evading all the messy considerations of primes, factors, divisors, and the keeping of lists.
Ask the user for the two numbers.
Read them into cardinal variables.
Arrange the two numbers in the order (larger, smaller)
Compute the GCD.
let the gcd be the larger
while the smaller is greater than zero
suppose the gcd is the smaller
Replace the smaller with (larger MOD smaller) and
the larger with the last smaller (saved as trial gcd)
end while
Say what the GCD is
1. Imports required From STextIO: WriteString, WriteLn, From SWholeIO: ReadCard, WriteCard 2. Variables required x, y : cardinals to hold the two numbers for the GCD calculation gcd : the cardinal result temp : a cardinal for use in swapping
To conserve space, the user manual has been left out. Here is the code:
MODULE GCD;
(* This program computes the GCD of two cardinal numbers
by R. Sutcliffe
revised 1993 02 15 *)
FROM STextIO IMPORT
WriteString, WriteLn, ReadChar, SkipLine;
FROM SWholeIO IMPORT
ReadCard, WriteCard;
VAR
x, y, temp, gcd : CARDINAL;
again : BOOLEAN;
answer, cr : CHAR;
BEGIN
(* write information *)
WriteString ("This program computes the GCD ");
WriteString ("of two whole numbers.");
WriteLn;
REPEAT
(* get the numbers *)
WriteString ("Enter the first number ==> ");
ReadCard (x); (* read first number *)
SkipLine; (* and end of line *)
WriteLn;
WriteString ("And now, the second ==> ");
ReadCard (y); (* read second number *)
SkipLine; (* and end of line *)
WriteLn;
(* arrange the numbers in order *)
IF y > x
THEN (* swap the numbers *)
temp := x;
x := y;
y := temp;
END;
(* compute the GCD *)
gcd := x; (* initial gcd in case y = 0 *)
WHILE y > 0
DO
gcd := y; (* let the gcd be the smaller of the two *)
y := x MOD y; (* replace smallest with new remainder *)
x := gcd; (* and larger with smaller from last step *)
END;
WriteString ("The GCD is ");
WriteCard (gcd, 0);
WriteLn;
(* check for another *)
WriteString ("Do you want to do another one? ");
ReadChar (answer);
SkipLine; (* and end of line *)
WriteLn;
again := (answer = 'Y') OR (answer = 'y');
UNTIL NOT again;
END GCD.
Here is a run from this module with some of the on-screen carriage returns deleted to save space.
This program computes the GCD of two whole numbers. Enter the first number ==> 200 And now, the second ==> 4780 The GCD is 20 Do you want to do another one? y Enter the first number ==> 50 And now, the second ==> 1001 The GCD is 1 Do you want to do another one? y Enter the first number ==> 0 And now, the second ==> 5 The GCD is 5 Do you want to do another one? n
If this example illustrates nothing else, it is that while simple algorithms take considerable intelligent human effort to discover, the repetitive calculations can then be left to the computing device. In this case, the algorithm that was finally coded here was first reported on by the Greek mathematician Euclid about 300 B.C.