MACHINE LANGUAGE

Jim Butterfield, Associate Editor

Math And Tables

I'm frequently asked for addresses within ROM that do certain operations, usually mathematical functions. I do my best to talk programmers out of this approach if possible.

For one thing, the addresses of the ROM routines vary from machine to machine. I'd prefer to see a programmer borrow the code from the ROMs and include it in the program. At least that way, transportability is not a problem.

Using ROM math routines is often awkward. They often call for one or more values to be placed into floating point accumulators before calling, and return values in the same areas. A floating point number is often an inconvenient format and takes a fair-sized conversion routine to bring back to the more convenient "fixed point" notation used by most machine language programmers. The total effort can turn out to be greater than programming it yourself.

But the main reason that I try to discourage use of these routines is this: They are designed for a certain number of digits of accuracy, and your program usually wants either greater or less accuracy. If you need less, you're wasting processor time working out the extra places. If you need more, the built-in routine will not do the job for you.

A Question

I was recently asked by a user to supply the address of the logarithm routine within a certain computer. It would have been easy to just answer the question, but I balked. I asked the user to define his objective.

This makes an interesting case history, since the objectives were changed partway through the exercise. We have a chance to see a couple of approaches to avoiding the built-in routines.

My first thought was to replace the ROM log routine with a streamlined machine language version. There are several efficient ways of calculating a logarithm; any book on numerical analysis (or an encyclopedia) will supply information on this.

First Approach

After questioning the user closely, the objective appeared to be this: An eight-bit reading was being taken from a remote device. He desired to convert this reading to a base ten logarithm (with appropriate scaling) for display purposes, and the accuracy of the result was to be 16 bits.

My concept of the approach changed. The magic words, "eight bits," had been spoken. The objectives were still a bit fuzzy, since it's hard to get a full 16 bits of useful data when your original data was only 8 bits accurate; but not to worry on that score for the moment.

Here's the pitch: If you have an eight-bit value to work through any mathematical function, use a table. There are only 256 possible values to be worked out, 256 questions and 256 corresponding answers.

We'll need to have two tables—one for the low part of the answer and one for the high part—but that's no problem: 512 bytes of storage is usually not hard to come by.

Looking up things in a table of 256 values is the ultimate in simplicity. It's sometimes called a "list type lookup," and the principle is very simple. Put the original value into an index register, and read out the indexed answer. Our code might read something like the following:

LDX —input register—
LDA LOWTABLE,X
STA LOWRESULT
LDA HIGHTABLE,X
STA HIGHRESULT

No loops, no math, no complexity: Five instructions and it's done. We must be sure to prepare the table in advance, but that's a one-shot task. In fact, BASIC could do the job for us and POKE the values into the table.

Second Approach

When the requirement was examined more closely, the rules changed and the problem was inverted: Given a 16-bit reading, compute the base ten logarithm to 8 bits of accuracy. The eight bits, by the way, were to be used to draw a high-resolution graph; 256 points were quite sufficient for the resolution required.

This requirement makes a little more sense: Converting 16 bits into 8 involves a loss of accuracy, but that was compatible with the display objective.

We still have the magic words "eight bits" embedded in the problem, but this time they describe the result. We can still use our table approach if we invert the way we use the table.

Let's build our table this way: For each of the 256 entries, we'll put the corresponding "anti logarithm" in the table. When we search the table to find the closest match to our original value, the answer will turn out to be the number of the table entry.

An example might illustrate what I mean here. Suppose the 16-bit input number has a value of 2000. The desired result, allowing for the scale, will be 165. In slot 165 of the tables (high and low), I'll find a value that's quite close to 2000. My task: search the table to find the closest value.

Binary Splitting

This isn't hard to do. Most of us have learned to search a table by using a "binary split" method, splitting the table in half again and again until we find the value we want. And on a table of size 256, a computer can do a very efficient job of binary splitting. Eight comparisons and it's all over.

The code would follow these lines:

LDA #$80
STA MASK

This says, "we're going to split the table into chunks of 128 (hex 80) this time around."

LDX #$00
STX POINTER

We'll kick off starting at position zero in the table. Here comes the loop:

LOOP LDA POINTER
     ORA MASK
     TAX

We've added our offset of 128 to the starting position of zero, so our first comparison will be at the midpoint of the 256 table.

COMPARE .....

Let's fudge the COMPARE coding for the moment. We'll need to load our high and low bytes into A, compare to the table high and low (indexed, of course) and decide whether our value is higher or lower than the table entry. If our value is LOW, we'll branch ahead to LOW; otherwise, we continue with HIGH:

HIGH	STX	POINTER

If our value is high, we store the index. If not, we skip this instruction and continue with the old value in POINTER.

LOW	LSR	MASK

Our mask contained 128, the size of the "split." Now we are dividing it by two so that it becomes 64, and 32 the next time, followed by 16, and so on. Eventually, we'll end up with zero as the bit rolls out of the end of the byte.

BNE	LOOP

We go back to do another comparison. Let's see what has happened. POINTER started at zero. If our input value is lower than table item 128, POINTER will stay at zero and the next comparison will be with item 64. On the other hand, if our input value is higher than table entry 128, POINTER will be changed to 128, and the next comparison will be with item 192. In other words, we'll split the upper half or the lower half depending on how the previous comparison went.

It's not hard to see how the program zeros in on the answer after eight comparisons. Finally, MASK becomes zero, the program stops looping, and the answer may be found in POINTER.

The user started out looking for a logarithm routine in ROM, and ended up with something much better: faster, more compact, and well-suited to the application.

And there was a free bonus. After looking at this approach, the user discovered that he could do something he had previously thought impractical: switch to a new display scale—linear, split scale, or whatever—with no difficulty. It was just a matter of turning the tables.