Coding choices. (Machine Language)
by Jim Butterfield

Recently, I saw the following message posted on a computer network: "I have a value in a single byte, and I want to calculate the remainder after dividing by 5. What code do you suggest?"

The remainder after division is often called the modulo; I don't know why the user wanted to calculate this, but there are several methods available that we can try. In this column, we'll discuss a couple of methods for solving the problem, and we'll also demonstrate the tradeoff between a program's speed and size. While we're at it, this might be a good time to gain some insight into hexadecimal numbers.

The standard method for solving this problem would be to use a conventional division routine that would yield both quotient and remainder. There are methods, however, that are designed either to achieve maximum speed or to utilize minimum memory. One rarely finds a piece of code that offers both. Almost all coding is a tradeoff between these two extremes.

A sample program called MOD5, printed at the end of this column, provides us with three approaches. The first routine offers speed, the second efficiency, and the third is a compromise of the two. You may want to examine the code of each one.

The fastest method is to look up the remainder in a table. Since a one-byte number can contain only 256 possible values, we can do this with a table of 256 bytes. This method couldn't be faster. We put the original byte into the Y register, and do the translation with a single instruction: LDA TABLE, Y. You'll find this at hex address 2015 in the program at the end of this column.

The method wastes memory, since we must devote 256 bytes to hold the table. The table could be loaded in, but it's quicker to calculate it when the program starts. You'll see this one-shot table build at addresses $2000-$2011. If only a few values were to be calculated, we couldn't justify this extra work. On the other hand, if there were thousands of values, this program would be speed efficient.

If the byte in question contains a value of 5 or more, we could subtract 5 and then repeat. Eventually, we end up with a value of 0 to 4; that's the remainder. The calculation loop, at addresses $202C-$2033, requires only four instructions: compare to 5, branch out if less (BCC), subtract 5, and branch back to the loop (BCS). Serious students of code will be able to explain why we don't need to set the C (carry) flag before subtraction and why the BCS (Branch Carry Set) command always branches.

The code is compact, fitting within eight bytes, but it could be slow. Since the original value could be as high as 255, the loop might be repeated as many as 51 times!

Most programs trade off speed against size. Programs that need to be fast will unfold their loops; this saves time but calls for more instructions. In this case, it really doesn't matter much. We have plenty of memory, and even the slowest method runs plenty fast for our purposes.

I wanted to add one more method, however. This third piece of code is moderately compact and fast. More important, it helps to show an interesting aspect of hex numbers.

It takes only a glance at a decimal number to tell whether it divides evenly by 5 or what the remainder would be. The last digit of the number tells the story (5 is a factor of 10, the base of decimal numbers). That's not true of hexadecimal numbers. The last digit will signal whether the number is divisible by 2, 4, 8 or 16, but it won't help you on the mod-5 question. Hex numbers such as 20 and 65 seem as if they should divide by 5, but they don't. Their decimal values are 32 and 101.

There is, however, a quick way to inspect hex numbers to see whether or not they will divide by 5. It's similar to the method we use with decimal numbers in testing whether or not a number divides by 9 or by 3. Add the decimal digits together; the total will have the same mod-9 value as the original number. Thus, decimal value 1234 will have a remainder of 1 when divided by 9. Calculate 1+2+3+4, giving 10, and the answer is a snap. The same holds true for division by 3, which is a factor of 9.

In hex, the sum of digits tells us about division by 15 or either of its factors (3 or 5). So, hex 23 will divide exactly by 5, and hex BC would have a remainder of 3. We know this because 2+3 gives 5, B+C or 11+12 gives 23, which would leave a remainder of 3 when divided by 5.

How would we do this in a computer program? A hex digit corresponds to four bits. We can extract the value of the high hex digit by shifting the number right four places. We extract the low digit value with a simple AND #$0F. Add them together, and we have the sum of the two hex digits within a byte.

This sum cannot be greater than 30 (decimal), so we know that the simple subtraction of method 2 will now loop not more than six times. Quite an improvement from a possible 51 times around the loop.

Four LSR (Logical Shift Right) commands extract our high hex digit. We store the result and then call back the original value; masking with AND #$0F isolates the low digit. Add them together (don't forget to clear the carry flag first with CLC), and we can repeat the subtract loop of method 2. The whole thing goes from hex address 2040 to 205B. That's a bit longer than the previous method, but there's quite a speed advantage.

The program works on almost any Commodore 8-bit computer. It first pokes the machine language code into place. Then it does the mod-5 calculation four times.

The first calculation is in BASIC, followed by each of the three above methods. The values used for the calculation are from ROM, hex addresses E000 through E006. You'll get the same results each time, of course.

You might want to use a machine language monitor to inspect the MOD5 code more closely. That'll give you an even better understanding of what's happening in the different routines.

100 DATA 162,0,160,0,152,157,

0,33,200,192,5,144,2,160,0 110 DATA 232,208,242,188,0,224,

185,0,33,9,48,32,210,255 120 DATA 232,224,7,144,240,169,

13,76,210,255 130 DATA 162,0,189,0,224,201,5,

144,4,233,5,176,248,9,48 140 DATA 32,210,255,232,224,7,

144, 235, 176,226 150 DATA 162,0,189,0,224,72,74,

74,74,74,141,255,32,104 160 DATA 41,15,24,109,255,32,

201,5,144.4,233,5,176,248 170 DATA 9,48,32,210,255,232,

224,7,144,220,176,186 200 FOR J=8192 TO 8295 210 READ X:T=T+X 220 POKE J,X 230 NEXT J 240 IF T<>12902 THEN STOP 400 PRINT "BASIC" 410 FOR J=57344 TO 57350 420 X=PEEK(J):PRINT X-5*INT(X/5); 430 NEXT J 440 PRINT 450 PRINT"TABLE LOOKUP:" 460 SYS 8256 470 PRINT "SUBTRACT LOOP:" 480 SYS 8231 490 PRINT "HEX CHECKSUM:" 500 SYS 8256 510 PRINT "END."