User:Wvbailey/Euclid's algorithm

A sandbox page: ---

Algorithms for computers: A computer (or human “computor” ) is a machine that follows blindly its instructions. Arguably the most primitive of these mechanisms is Lambek’s model of computation – a "countably finite number of locations (holes, wires etc.) together with an unlimited supply of counters (pebbles, beads, etc). The locations are distinguishable, the counters are not"; furthermore the holes will have unlimited capacity, and an agent to do this per a list of instructions . In other words, computers have “locations”, the “locations” have identifiers (names or numbers), and the locations are either empty or they have a quantity of discrete things in them. Each hole’s quantity can be mapped onto an integer (a positive whole number including 0). In the following, a number will be in lower case, a computer location in upper case. A location will be said to “contain a number". The computer (human or mechanical) will process numbers that appear in (named locations).

Euclid’s algorithm: Euclid’s algorithm appears as the second Proposition 2 in Book VII of his ‘’Elements’’ . It states: “Given two numbers not prime to one another, to find their greatest common measure”. In modern terms, this means, given two integers a and b, compute their greatest common divisor.. At the beginning of Book VII Euclid defines “A number [to be] a multitude composed of units”, in other words a counting number, positive integer not including 0. Furthermore, to “measure” is to “determine the length of” a longer length l by use of a measuring length s, with or without a remainder ’’r’’ after successive measures. In modern algebra: r = l – q*s, where q is the quotient and r is the fractional part.

To begin, a number a will appear in a location called A, and another number b will appear in a location called B.

Symbolically: Suppose the location B has the number b in it and this is to be copied into location L: the copy instruction will be symbolized by L := B. If subtraction of a number s in S occurs from a number l in L, the result l-s must be put somewhere. If this place is location R, then symbolically R := L - S; if this location is (back into) L (a process known as read-modify-write) then symbolically L := L – S.

For Euclid’s method to succeed, the starting lengths must satisfy two requirements: (i) If the computation is not to go on forever, the smaller number s must not be 0, AND (ii) So that the subtraction is “proper”, a test must guarantee that in all cases the smaller of the two numbers is subtracted from the larger (alternately, the two can be equal so their subtraction yields 0).

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 “zero”, in fact this eventuality is what terminates his algorithm. Heath 1908: xxx 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 a length “measures” the other exactly, i.e. the two have the same length. Indeed if this is the case then the method ends. The computer algorithm will have to account for this possibility.

A program: Given that the algorithm will follow Euclid’s and Nichomachus’ methods of successive subtraction, a possible “program” is the following. A more-optimum example appears in the flowchart and in Basic, but this represents a starting point. It consists of 3 major parts:

Part I: Given two counting numbers a and b, Put the larger number in L, and put the smaller number in S.

Part II: Until S > L, by successive subtractions of S from L compute the fractional part R remaining,

Part III: Until the subtraction of part II yields 0, copy what was the measuring number from S into location L so that now what was doing the measuring will now be the measured, copy the fractional part R into S so that the remainder becomes the measuring number, and repeat Part II. When the subtraction of part II yields 0, the greatest common divisor will be in S.

Part I: Put the larger number in L, put the smaller number in S.

1 [Into two locations A and B (i.e. memory, or registers), put the numbers a and b that represent the two lengths]: INPUT A, B

2 [Determine the smaller of the two numbers in A and B; the other will be the “measured” number; the smaller will be the “measuring” number s,]: IF A > B THEN the contents of B (number b) is the smaller number: go to step 6 ELSE continue,

3 [The contents of A ≤ B: Copy the larger from B into L and the smaller from A into S]: L := B

4 S := A

5 [Proceed to the remainder loop]: Go to step 9

6 [The contents of A > B: Copy the larger from A into L and the smaller from B into S]: L := A

7 S := B

PART II: By successive subtractions of the measuring from the measured, compute the remaining (i.e. fractional) portion. This process is equivalent to repeating two steps: “remainder R := larger L – smaller S” followed by copying the contents of R into L i.e. “L := R”. This repetition needs a test to terminate it, otherwise it will result in improper subtraction (R a negative number) and the loop will never end:

The obvious test “S>R?” will fail at the very beginning because the value of R is unspecified. A solution is to compare S to L rather than S to R; this will work because at the outset L := A, and later on when L contains l – q*s (q indicates the number of times the loop has occurred). Note also that the successful outcome of test “S>L?” implies that L ≤ S, in other words, the numbers in L and S could be equal. Suppose at the very beginning number a = 83 and b = 83. To terminate 83 > 83, which is false. So the loop executes and computes e.g. 0 := 83 – 83 followed by copying 0 into L i.e. L := 0. On the next go-round the loop will terminates and sends the process to step 12; from there it terminates the entire algorithm.

8 [Inner-loop: Test the measuring-number in S for larger than the remaining portion in L]: IF S > L THEN done measuring: go to step 12 ELSE measure again: continue,

9 [‘’Measure again: Subtract smaller number in location S from remaining portion in L, and deposit the difference in R]: R := L - S

10 [Copy the remaining portion in R into L]: L := R

11 [Inner-loop]: Go to step 8.

PART III: At this point the nut of the algorithm – “Euclid’s loop” – begins. Again a test is required for this outer loop to terminate: when the inner-loop test terminates the loop and sends the program forward to step 12, either (i) The algorithm is done: the last measure was exact and the remainder in R is 0, OR (ii) The algorithm must continue: the last measure left a remainder in R less than measuring number in S.

To continue, the algorithm uses the remainder to measure what was previously the smaller number: it copies S into L and R into S.

12 [Outer Euclid loop’s termination-test: Test number in R for 0, i.e. an exact measure]: IF R = 0 THEN done: go to step 10 ELSE continue,

13 [Copy the previous measuring number in S into L, and copy the remainder from R into S]: L := S

14 S := R

15 [Repeat the measuring process using what was the remainder to measure what was the shorter length]: Go to step 8

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

17 HALT, END, STOP.