★ CODING ★ AMSTRAD ACTION DISCOURSE - EUCLID'S ALGORITH TO CALCULATE THE H.C.F OF TWO NUMBERS|Amstrad Action #44) ★ |
| Amstrad Action Discourse - Euclid's Algorith to Calculate the H.C.F of Two Numbers |
You may already realise that many techniques used in computing are not that new at all. But did you know that some of them are more than 2,000 years old? JAMES WILSON demonstrates. Calculating was originally an activity performed by priests, and its advance, in early times, sat on the back of priestly philosophical discussions on the nature of their gods, on perfection and on the general shape of things. The second of the Ptolemaic rulers of Egypt founded a library and museum at Alexandria in about 300 B.C. Amongst the first of the scholars to be called to this Alexandrian Academy was Euclid (C.330BC - C.260BC), that illustrious mathematician. He came from Athens where he had probably trained under Plato. For the next 22 centuries, the first six books of his thirteen volume Elements of Geometry were the customary school intro duction to geometry. Although the work is called Elements of Geometry three of the volumes are devoted to the theory of numbers. In Book 9, Proposition 20 is the proof that there is no 'highest Prime Number, a remarkable deduction in an area that has exercised great minds ever since. In his tenth book he explored the irrational quantities, first discussed by Pythagoras, and to this day the subject of deep research by eminent mathematicians under dreaming spires. Getting things in proportion The theory of proportion is a geometric commonality that is discussed in his fifth book and gives rise to the theory of irrational numbers which was eventually developed by Rene Descartes (1596-1650). Euclid also wrote a mathematical treatise on Optics. He believed that light moved in straight lines and that vision was something that went forth from the eye. Many of his other works on astronomy and music are lost lo us though some survive in Arabic translations of dubious accuracy. The algorithm method One especial loss is his work entitled On Fallacies which dealt with the causes of error in geometrical research. However, one remarkable legacy of this ancient sage is his algorithm, expounded in Proposition 2 of Book 7, for calculating the Highest Common Factor of two numbers. This algorithm is an excellent example of a mathematical process which only works correctly with integers (ie. whole numbers). Let us choose any two whole numbers a and b, and suppose that a > b. If a is not divisible by b then we can express a as a multiple of b together with a remainder which is less than b. that is xa = kb + c where 0 < c < b eg. 38 - 3 x 12 + 2 Any common divisor of b and c is also a divi- Ail example best illustrates this algorithm. Take the numbers 4862 and 1793. The algorithm runs as follows - 4862 = 2x1793 + 1276 1793 = 1 x 1276 +517 1276 - 2 x 517 + 242 5l7 = 2 x242+ 33 242 = 7x 33+ 11 33 = 3 x 11 + 0 and the H.C.F. is the 11, the last remainder. (For the aficionados, if, and only if, the last remainder of Euclid's algorithm when applied to two numbers is 1. then these two numbers are relatively prime and their H.C.F. is 1.) The following program illustrates Euclid's Algorithm and was used to calculate the above result. If you want to print the result on your printer change the value of a in Line 60 to 8. I will be expanding on this algorithm later in this series. Interestingly, the reasoning behind this algorithm can also be used to prove Proposition 30 of Book 7, the proposition often referred to as Euclid's Theorem: If a prime divides the product of two numbers. then it must divide at least one of these two numbers.
|
