User:Wvbailey/Euclid's algorithm

A sandbox page:

Algorithms for computers: an example

In computer systems, an algorithm is basically an instance of logic written in software by software developers to be effective for the intended "target" computer(s), in order for the software on the target machines to produce output from given input (perhaps null).

Algorithm versus function computed by an algorithm: For a given target computer multiple algorithms may exist. Rogers observes that "It is . . . important to distinguish between the notion of algorithm, i.e. procedure and the notion of function computable by algorithm, i.e. mapping yielded by procedure. The same function may have several different algorithms".

Computers (and computors), models of computation: A computer (or human "computor") is a restricted type of machine, a "discrete determinisitic mechanical device" that follows blindly its instructions. Melzak's and Lambek's primitive models reduced this notion to four elements: (i) discrete, distinguishable locations, (ii) discrete, indistinguishable counters; if no confusion will result, the word "counters" can be dropped, and a location can be said to contain a single "number", (iii) an agent, and (iv) a list of instructions that are effective relative to the capability of the agent.

"Elegant" programs, "good" (fast) programs ' The notion of "simplicity and elegance" appears informally in Knuth and precisely in Chaitin:

". . .we want good algorithms in some loosely defined aesthetic sense. One criterion . . . is the length of time taken to perform the algorithm . . .. Other criteria are adaptability of the algorithm to computers, its simplicty and elegance, etc" (Knuth 1973:7)

"I'll show that you can't prove that a program is 'elegant,' by which I mean that it's the smallest possible program for producing the output that it does" (Chaitin 2005:32).

Unfortunately there may be a tradeoff between goodness and elegance. An example of this will be shown below.

Simulation of an algorithm: computer(computor) language: Knuth advises the reader that "the best way to learn an algorithm is to try it . . . immediately take pen and paper and work through an example". But what about a simulation or execution of the real thing? The programmer must translate the algorithm into a language that the simulator/computer/computor can effectively execute. Stone gives an example of this: when computing the roots of a quadratic equation the computor must know how to take a square root. If they don't then for the algorithm to be effective, relative to the capabilities of the computor, it must provide a set of rules for extracting a square root.

This means that the programmer must know an "language" effective relative to a target computing agent.

Computer(computor) language for Euclid's algorithm: Only a few instruction types are required to execute Euclid's algorithm -- assignment (replacement), GOTO, subtraction, and some logical tests.

• A location is symbolized by upper case letter(s), e.g. S, A%, etc.
• The varying quantity (number) in a location will be written in lower case letter(s) and (usually) associated with the location's name. For example, location L at the start might contain the number l = 3009.

Instructions: Besides INPUT, OUTPUT, and HALT only 3 types are required:

• Logical test (conditional GOTO): IF [the test goes here] yields "true" THEN [the goto-instruction number goes here] ELSE continue in numerical sequence -- the ELSE part will be assumed and not written. Example: IF R > S THEN GOTO
• Unconditional GOTO: GOTO [the instruction number goes here.
• Assignment (replacement, substitution)": a rectange with the := symbol; on the left is the destination, on the right is the source location(s) with or without a formula. Examples:

S := R replaces the contents s in location S with the contents r in location R.

R := L - S subtacts the number s in location S from the number l in L and replaces the contents of R with the number l - s. Alternately, if the destination location is L (a process known as read-modify-write) then symbolically L := L – S.

Structured programming, canonical structures: Kemeny and Kurtz observe that while "undisciplined" use of GOTOs and IF-THENS can result in "spaghetti code" a programmer can write structured programs using these instructions; on the other hand "it is also possible, and not too hard, to write badly structured programs in a structured language." In particular they mention the DO-LOOP (DO-WHILE) and the IF-THEN-ELSE strutures These are two of the three Böhm-Jacopini canonical structures, the other being the simple DO-THEN sequence DO-THEN, IF-THEN-ELSE, and WHILE-DO perhaps augmented with DO-WHILE and CASE. An additional benefit will be a program that lends itself to proofs of correctness using mathematical induction.

Canonical flowchart symbols: These include the basic rectangle (DO-THEN), the diamond (IF-THEN-ELSE), and the dot (OR-tie) with "directed lines" between them. Flowcharts always start at the top of a page and proceed down. "Nesting" of sub-structures in a superstructure is permitted only if a single exit occurs from the superstructure. The symbols:

• IF-THEN-ELSE. Diamond with arrow entering top and arrows leaving at left or right vertex and from on bottom
• DO-THEN: An assignment-rectangle with an entry and an exit.

• Unconditional GOTO: not recommended in structured programming but is embedded in the WHILE-DO: rectangle with single arrow exiting bottom but going to instruction specified.

• WHILE-DO: IF-THEN followed by DO-THEN ending in a GOTO that returns its arrow to the top of the diamond and OR-ties with the arrow entering it.

Euclid’s algorithm

The example-diagram of Euclid's algorithm from T.L. Heath 1908 with more detail added. Euclid does not go beyond a third measuring and gives no numerical examples. Nicomachus gives the example of 49 and 21: "I subtract the less from the greater; 28 is left; then again I subtract from this the same 21 (for this is possible); 7 is left; I subtact this from 21, 14 is left; from which I again subtract 7 (for this is possible); 7 will be left, but 7 cannot be subtracted from 7." Heath comments that "The last phrase is curious, but the meaning of it is obvious enough, as also the meaning of the phrase about ending "at one and the same number"(Heath 1908:300).

Euclid’s algorithm appears as Proposition II in Book VII ("Elementary Number Theory") of his Elements . Euclid poses the problem: "Given two numbers not prime to one another, to find their greatest common measure". He defines "A number [to be] a multitude composed of units": a counting number, a positive integer not including 0. And to "measure" is to place a shorter measuring length s successively (q times) along longer length l until the remaining portion r is less than the shorter length s. In modern words, remainder r = l - q*s, q being the quotient, or remainder r is the "modulus", the integer-fractional part left over after the division.

For Euclid’s method to succeed, the starting lengths must satisfy three requirements: (i) the lengths must not be 0, AND (ii) The subtraction must be “proper”, a test must guarantee that the smaller of the two numbers is subtracted from the larger (alternately, the two can be equal so their subtraction yields 0), AND (iii) the two lengths are not prime to one another.

For Euclid, the first requirement was tacit and not discussed: a length of 0 would not meet the definition of “a number”, i.e. a multitude of units. However, Nichomachus’ example hints at the problem of a remainder equal to “zero”, in fact the equivalent is what terminates his algorithm. Heath 1908:300 reports (quoting Nicomachus) “ ‘. . . but 7 cannot be subtracted from 7.’ The last phrase is curious, but the meaning of it is obvious, as also the meaning of the phrase about ending 'at one and the same number' ".

With regards to the second requirement, Euclid begins his proof with the possibility that at the outset the two lengths are the same. Indeed if this is the case then the method ends. The computer algorithm will have to account for this possibility.

With regards to the third requirement, Euclid stipulated this so that he could construct a reductio ad absurdum proof that the two numbers' common measure is in fact the greatest. While Nicomachus' algorithm is the same as Euclid's, when the numbers are prime to one another it yields the number "1" for their common measure. So to be precise the following is really Nicomachus' algorithm.

A inelegant program for Euclid's algorithm

"Inelegant" is a translation of Knuth's version of the algorithm with a subtraction-based remainder-loop replacing his use of division (or a "modulus" instruction). Derived from Knuth 1973:2-4. "Less-inelegant" on the right computes the same function with fewer instructions, sometimes faster, sometimes slower. Depending on the two numbers "Less inelegant" maybe faster than "Elegant".

The following algorithm is framed as Knuth's 4-step version of Euclid's and Nichomachus', but rather than using division to find the remainder it uses successive subtractions of the shorter length s from the remaining length r until r is less than s. The bold-face headings are adapted from Knuth 1973:2-4:

1 [Into two locations L and S put the numbers l and s that represent the two lengths]: INPUT L, S

E0: [Insure r ≥ s.]

2 [Initialize R: make the remaining length r equal to the starting/initial/input length l] R := L

3 [Insure the smaller of the two numbers is in S and the larger in R]: IF R > S THEN the contents of L is the larger number: skip over the exchange-steps 4, 5 and 6: GOTO step 6 ELSE continue,

4 [The contents of R (and L) are less than or equal to the contents of S: Swap the contents of R and S.] L := R (this first step is redundant, but will be useful for later discussion).

5 R := S ( s is larger so it goes into R)

6 S := L ( l, and also r is smaller so it goes into S)

E1:[Find remainder]: Until the remaining length r in R is less than the shorter length s in S, repeatedly subtract the measuring number s in S from the remaining length r in R.

7 [Test the measuring-number s in S for greater than the remaining portion r in R.]: IF S > R THEN done measuring: go to step 12 ELSE measure again: continue,

8 [Measure again: Subtract smaller number s in location S from remaining portion r in R, and deposit the difference back in R, i.e. r_new := r_old - s]: R := R - S

9 [Remainder-loop]: Go to step 7.

E2: [Is the remainder 0?]: After the inner-loop test terminates it sends the program forward to test whether or not the algorithm is done: EITHER (i) the last measure was exact and the remainder in R is 0 program can halt, OR (ii) the algorithm must continue: the last measure left a remainder in R less than measuring number in S.

10 IF R = 0 then done: go to step 15, else continue,

E3.: [Interchange]: The nut of Euclid's algorithm. Use the remainder r to measure what was previously the smaller number s: L serves as a temporary location for the exchange: R-->L, S --> R, L --> S; then go back to E1.

11 L := R

12 R := S

13 S := L

14 [Repeat the measuring process]: Go to step 7

15 [Done, the contents of S, is the greatest common divisor]: PRINT S

16 HALT, END, STOP.

An elegant program

The following version of Euclid's algorithm requires only 6 core instructions to do what 13 are required to do in the inelegant version; worse, "Inelegant" requires more types of instructions. The flowchart of "Elegant" can be found at the top of this article, abbreviated somewhat from the "old Basic":

   10 REM Euclid's algorithm for greatest common divisor
   20 PRINT "Type two integers greater than 0"
   30 INPUT A%,B%
   40 IF B%=0 THEN GOTO 100
   50 IF A% > B% THEN GOTO 80
   60 LET B%=B%-A%
   70 GOTO 40
   80 LET A%=A%-B%
   90 GOTO 40
  100 PRINT A%
  110 END

How "elegant" works: In place of an outer "Euclid loop", "Elegant" shifts back and forth between two "co-loops", an A% > B% loop that computes A% := A% - B%, and a B% ≤ A% loop that computes B% := B% - A%. This works because, when at last the minuend M is less than or equal to the subtrahend S ( Difference = Minuend - Subtrahend), the minuend can become s (the new measuring length) and the subtrahend can become the new l (the length to be measured); in other words the "sense" of the subtraction reverses.

Testing the algorithms

Does an algorithm do what its author wants it to do? The exceptional cases must be identified. Will the above algorithms perform properly when B > A, A > B, A = B? (Yes to all). What happens when A = 0?, B = 0? Both A and B = 0? (No: Inelegant computes forever in all cases; elegant computes forever when A% = 0. A fully-effective algorithm will have to solve these cases).

As suggested by Knuth one can proceed with paper and pencil to do a few test cases. One source uses 3009 and 884. Another interesting case is the two relatively-prime numbers 14157 and 5950.

Proof of program correctness by use of mathematical induction: Knuth demonstrates the application of Mathematical induction to an "extended" version of Euclid's algorithm, and he proposes "a general method applicable to proving the validity of any algorithm" . Tausworthe proposes that a measure of the complexity of a program be the length of its correctness proof .

When it comes to simulating the algorithm on a machine, can it be so general that the mechancial "platform" does not matter? In this regard, Philosopher Daniel Dennett identifies a key feature of an algorithm: what he calls its "substrate neutrality":

"Substrate neutrality: an algorithm relies on its logical structure. Thus, the particular form in which an algorithm is manifested is not important".

Van Emde Boas, on the other hand, observes "even if we base complexity theory on abstract instead of concrete machines, arbitrariness of the choice of a model remains. It is at this point that the notion of simulation enters". But what model should be used for the simulation? When speed is being measured, the matters. For example, "inelegant" will execute much faster if division is available.

Can the inelegant algorithm be improved?

Once the author of the algorithm judges "fit" and "effective" -- that is, it does what its author wants it to do -- then the question becomes, can it be improved?

Improvement may involve an acceptance of a tradeoff. Examination of where time is lost points to the loops, in particular an inner loop. If one were to combine the two-step sequence R := L - S followed by L := R, into a single L := L - S, then "inelegant's" execution-time would be shortened. (This requires other changes, see "less-elegant" below.

Given the two numbers 3009, 884, the count is "less-inelegant" 73, "elegant" 71; "less-elegant" looses. But given 14157, 5950 the results are "less-inelegant" 301, "elegant" 321; "elegant" looses. Which is better? Knuth's method of averaging over a large number of trials offers a possible measure of their goodness.