★ CODING ★ AMSTRAD ACTION DISCOURSE - HERO'S ALGORITHM TO APPROXIMATE THE SQUARE ROOT OF A NUMBER|Amstrad Action) ★ |
| Amstrad Action Discourse - Hero's Algorithm to Approximate the Square Root of a Number |
This month Hero's engine gets a demonstration at the capable hands of JAMES WILSON. In 50 BC Egypt. fell into the hands of the Roman Empire and the decline of Alexandria as a centre of intellectual innovation and excellence got well under way. But the great school still had a genius or two left from whom we inherit some useful algorithms. In Discourse II Diophantus was mentioned in connection with his implicit use of the idea of a limit. Such a method was also used by Hero to estimate square roots of numbers which were not perfect squares.
Hero of Alexandria (ca.62 AD) was a practical man rather than a philosophical mathematician. In his book Pneumatica he describes the famous Hero's Engine whereby a small tank of water mounted on an axle is made to spin by heating the tank and allowing the steam to escape through two opposing holes - the first suggestion of a steam engine. In his Mechanica he discusses gear trains, worm wheels, pulleys and levers in various combinations. His surveyor's Dioptra a form of theodolite, used screws and worm gears for fine adjustments. Hero also advanced Euclid's optical work. He was the first to demonstrate the Law of Reflection of light - that the angle a: which light is reflected from a surface is equal the angle at which it strikes and he designed other surveying instruments which depended upon this. He also investigated refraction are he mused on the effect of refraction on astronomical observations made near the horizon. But like the rest he also spent some time studying numbers. The square roots of many integers are not only themselves not integers, but cannot even be represented properly and completely as a fraction. For instance , 2, the square root of 4 , can be equally well written as 2/1 or 36/18. However, SQR(2) cannot be represented as a fraction no matter how large the numerator (top number) 0n denominator (bottom number) and therefore is called an irrational number. Hero developed an algorithm that makes it possible to create a fraction which is as close as we wish to get to the actual value of the square root of any integer. The Heronian Algorithm depends on the fact that if we have any two numbers which, when multiplied together, form a third, then the average of these two numbers is closer to the square root of the third than either of them. For example. 4 x 9 = 36. One could say that cither 4 or 9 are approximations of SQR(36): but their average (6 ½) is closer still. This is clearly true. If we can find a number n so that n x 6 ½ = 36, then the average of n and 6 ½ will be even closer still! This number n is known as the inverse of the approximation (6 ½ i:i this instance). By schoolboy algebra this must be 72/13. Interestingly, the values of the approximation approach the square root from 'above' , whereas the inverse approaches it from 'below' , the two converging on the actual limiting value. The gap between them narrows quickly and the values of both the numerator and denominators of these fractions increase very rapidly. For this reason, though we are dealing with integers , their values so quickly exceed 32676 that we have had to use Real numbers to represent them and, even then, after a couple of iterations we exceed the real top limit of 1..7E+38. This restriction of the CPC means the algorithm looses too much accuracy after about SQR(36) to be of real use, but is is a very fine example of a convergent algorithm.
|
