| helpline |
Computer arithmetic does not always tell the truth. Andrew Hewson makes those recalcitrant digits dance to his tune
OCCASIONALLY I have thought of arranging your letters into a 'Top Ten' of the topics which occur most frequently. The following letter, from Stan Merrifield, is on a subject which would definitely figure in the list. He writes: Just for fun I set up a loop in my Spectrum to print all the integer square roots between one and 100 as follows:
10 FOR N = 1 TO 100 20 IF SQR N = INT(SQR N) THEN PRINT N 30 NEXT N
I felt quite chuffed when it printed 1, 4, 9, 16, but after a slight delay it added 64 and finished. I cannot understand why it missed 25, 36, 49, 81 and 100. What is going wrong?
I first answered a question of this type in the second issue of Sinclair User in May 1982 and I have covered it at least once since then. I make no apology for tackling it yet again because, like a bad penny, it keeps on turning up.
It is noticeable that the question always comes from the older sort of Sinclair user. That might be because young people generally have a much deeper understanding than their elders of the rounding errors that occur when the form of a number is changed from one representation to another. For that we ought to thank the Nuffield pioneers who radically altered the Maths curriculum in schools in the late '60s and early '70s.
Those of us who went to school before 'New Maths' was established are familiar with only one example of a rounding error and it is buried so deep in our knowledge of arithmetic that we cannot look at it in an objective fashion without considerable effort. The example to which I refer is that one third cannot be exactly represented by a finite number of digits in the decimal system.
As we all know the following statements are all incorrect: 1/3 = 0.3; 1/3 = .33; 1/3 = 0.333. No matter how many trailing threes we place at the end of the number the result is still incorrect, even if only slightly. We are so familiar with that example that we no longer consider it worthy of comment or investigation. We are no different from the Romans of ancient times who no doubt knew that their system of numerals was cumbersome and slow but were happy to persist with it despite its deficiencies.
Unfortunately, because the decimal representation serves us well in everyday life we somehow assume that the inaccuracy in one third is a property of the number itself rather than the method by which we choose to represent it. In fact it is easy to show that it is the method of representation which is at fault, not the number.
If we had been created with six fingers on each hand rather than five then we would presumably count in groups of twelve, that is we would count to base twelve. When counting to base twelve the following statement is true: 1/3 = 0.4. That is easy to understand if you remember that the column following the point is the twelfths column and four twelfths equals one third.
However, counting to base twelve is not immune to problems. The fraction one fifth, for example, which is equal to 0.2 in the decimal system can only be exactly represented in base twelve by an endless repetition of the four digits 2497, after the point. The crux of the problem is that no matter what base you choose there will always be some fractions which cannot be represented exactly. There even some numbers - iT, the ratio of the circumference of a circle to its diameter, is one example - which cannot be exactly represented in any base.
Those inexactitudes do not normally matter because we are happy to accept that a number which is correct to an arbitrary number of significant figures is exact for all human purposes. The trick then when writing your programs is to build in acceptance of tiny but irrelevant differences. In particular you should not, as Stan Merrifield has done in line 20 of his program, demand exact equality in any comparison.
It may seem surprising when considering Stan's program that rounding errors creep in because he is searching for whole number solutions only, which can be exactly represented in any base. However, in order to find the square root of a number N the computer converts it to binary 'floating point' form because the calculator in the ROM will only perform calculations on such numbers. Floating point numbers are necessarily fractions and so it is at the conversion stage that the errors occur.
Stan's program will work as planned if the following line is substituted for line 20:
20 IF ABS (SQR N - INT(SQR N)) < .0000001 THEN PRINT N
That discussion about the calculator in the Spectrum ROM leads me into the following letter from Norman Strong. He writes: I am interested in mathematical problems. How can you perform calculations in machine code using logs, powers and trig functions?
Accessing the calculator in the Spectrum ROM from a machine code routine is very straightforward because it is only necessary to call RST 28h, following the instruction with a single digit code to tell the calculator what you want it to do. The system is designed around a calculator 'stack', a method used by most computers and calculators. Readers who have used one of the range of Hewlett-Packard calculators - which use so-called Reverse Polish Notation - or who are familiar with the Forth programming language will recognise the mechanism immediately.
The mechanism is mostly easily understood by way of an example. Suppose we require to subtract the Basic variable B from the Basic variable A and to PRINT the result. In other words we wish to execute the following Basic statement in a machine code program:
PRINT A - B
The steps are as follows:
1 - use a ROM routine called LOOKVAR to locate variable B in the Basic variables area; 2 - transfer the value of B to the calculator stack using the ROM routines called INTSTOR; 3 - find the variable A in the Basic variables area using LOOKVAR; 4 - transfer the value of A to the calculator stack using INTSTOR; 5 - call the ROM calculator using RST 28h and follow the instruction by a byte containing 03h which is the code for subtraction and a byte containing 38h which is the code to end calculation; 6 - PRINT the value on the top of the calculator stack using the routine FPPRINT.
A stack system is very flexible because any number of items, up to the limit of the size of the stack, can be manipulated in one operation. Similarly any number of operations can be strung together. If you wanted to divide one number by a second, multiply by a third and then find the square root of the result it would be necessary merely to place the numbers on the stack in the correct order and then call the calculator with the codes for division (05h), multiplication (04h) and square root (28h) followed by the termination code (38h).
Some of the routines which can be used to manipulate numbers on the stack have been extracted by my colleague Rob Banks, and they are named and described in table one together with their address in the Spectrum ROM. Some of the control codes are listed in table two. Neither table is comprehensive because a full study of the calculator is beyond the resources of this column. The interested reader is referred to some of the specialist books on the Spectrum including The Complete Spectrum ROM Disassembly by Ian Logan.
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||