A Difference Point

Well, didn’t get around to working much on the code this weekend, but I’ll get back on it. Regrettably, I usually find I’m most motivated when I’m at work… at home I just want to relax. I really envy people who can take that work attitude home with them.

I found a new TI forum lately, at AtariAge. I’ve been there a few times in the past, there’s some great retrogamers there from all over the world. Much to my delight, they’ve started a TI-99/4a programming board, and a number of 99′ers hang out there discussing pet projects. There’s even a contest going to write a retro game! I’d join up, but my own project is not likely to make the deadline…

And now a sedge-way into some coding discussion…

An interesting programming issue on vintage systems is the need for complex mathematics, but only using integers. Granted, most old computers did have some form of real number implementation, but it was rarely used. Why? Here are the reasons:

  • Real numbers take up more memory than integers
  • Real number handling requires special routines, either in hardware or self-written
  • Real numbers are rarely needed, and not worth the trouble to implement

The TI-99/4a has a very good floating-point number system, which uses the radix 100 implementation. The numbers are 64-bit; 8 bits for the power,  with 14 significant digits in the mantissa. This particular implementation was usually seen more in accounting and business than science, but is easier to manage than bit-wise implementations that modern processors use. The TI could beat PC’s of the era in floating-point accuracy quite handily.

However, using floating point on the TI is really annoying and expensive in time and resources. All numeric variables in BASIC and Extended BASIC are floating-point, which is one reason it’s so slow. A number of routines for manipulating floating point are present in the ROM and GROM chips of the console, but accessing them requires using the XMLLNK and GPLLNK utilities provided, or writing your own version of them. (Something I have not done myself yet, and am in no hurry to do.)

Generally, what I need floating point for is usually very specific tasks. For example, determining the distance between two points on a coordinate plane. This is easily done using the Pythagorean theorem, which states that the distance is equal to the square root of the added squares of the differences between the two points, or:

\sqrt{(x_1-x_0)^2 + (y_1-y_0)^2}.

This particular calculation could be done using the GROM routines for both power and square root, but why do that? Why not use integers? (Assuming you don’t care to have accuracy beyond a single whole number…)

Before calculators and clever programmers, there were methods to calculate square roots, as accurate as you needed them. One method is the Babylonian method, described by the greek mathematician Hero of Alexandria in the first century AD. It is a quadratically convergent algorithm, which means it doubles in accuracy with each iteration. Here’s the description:

  1. Start with an arbitrary positive start value x0 (the closer to the root, the better).
  2. Let xn+1 be the average of xn and S / xn (using the arithmetic mean to approximate the geometric mean).
  3. Repeat steps 2 and 3, until the desired accuracy is achieved.

It can also be represented as:

x_0 \approx \sqrt{S}.
x_{n+1} = \frac{1}{2} \left(x_n + \frac{S}{x_n}\right),
\sqrt S = \lim_{n \to \infty} x_n.

So, how to do this in assembly with integers? Well, first you need the deltas between the two coordinates. This is easily done with subtraction. Then you need your arbitrary value, or pseudo-root value. I decided the average between the two deltas would be all right. Technically, any positive value would work. But choosing something closer to the actual value reduces the computation cycles. Then you simply do some division and addition in loops changing the pseudo-root value each time, checking if the new value is equal to the prior value. (Ignoring the division remainder and focusing on the quotient only.) If it is, the cycle is complete and you have your distance!

Here’s the code in TMS9900 assembly. It’s VERY nice that we have multiply and division opcodes in the language; this routine would be more complicated in 6502 assembly:

* Distance calculator
* @XD - X Delta
* @YD - Y Delta
* Returns value in R0
DICCLC MOV  @XD,R0
       MPY  @XD,R0                     * @XD^2 into R1
       MOV  @YD,R2
       MPY  @YD,R2                     * @YD^2 into R3
       A    R1,R3                      * R3 = Seed value
       MOV  @XD,R4
       A    @YD,R4
       SRL  R4,1                       * R4 = (XD+YD)/2 (pseudo-root value)
DC1    MOV  R3,R1
       CLR  R0
       DIV  R4,R0                      * Divide Seed by PRV
       A    R4,R0                      * Add PRV to result
       SRL  R0,1                       * Divide by 2
       C    R0,R4                      * Compare to original PRV
       JEQ  DC2                        * If equal, value found, end routine
       MOV  R0,R4                      * Else, replace PRV and reloop
       JMP  DC1
DC2    RT

Well, that was fun. Let’s look at another…

Another floating-point function I rather wanted to have was sine and cosine. Why? So I could have sprites move in circles and arcs. Trigonometric functions are located in the ROM of the console, but of course, we want to use integers, and on the TI screen, we really don’t need all those digits anyway…

As a quick reminder, in case math class was a long time ago for you:

Sine

The sine of an angle is the ratio of the length of the opposite side to the length of the hypotenuse:

\sin A = \frac {\textrm{opposite}} {\textrm{hypotenuse}} = \frac {a} {h}.

Cosine

The cosine of an angle is the ratio of the length of the adjacent side to the length of the hypotenuse.

\cos A = \frac {\textrm{adjacent}} {\textrm{hypotenuse}} = \frac {b} {h}.

These two functions can be used to determine the exact coordinates around a center point. Radius is used as a multiplier on the ratios. The center position coordinates are just added to the results for each. Where the point for angle 0 starts depends on which one you use on which coordinate, X or Y.

This is a bit more of a difficult implementation, namely because even calculating sine and cosine using integers is a lot of work. Instead, I use a data table. This isn’t a new idea; until dedicated floating-point hardware existed in 3D video cards for the modern PC, most PC games used data tables for their trigonometric values instead of calling functions. And for the same reason we use it here, speed and efficiency!

I only need to have a quarter-circle of ratio values; the other three quadrants can be determined by inverting signs on values. The ratio divisions and angle use the range of a single byte, which is accurate enough for my purposes. By just running angles from 0-255 through the function, I can continually update a point’s position so it does a circle around the point.

The routine below will generate a position change on an X or Y coordinate to move it to the expected point for the radius and angle. Changing the radius along with the angle will make it spiral inward or outward. Increasing the angle differential in the loop will speed it up, making the angle differential negative will move in the opposite direction. Very cool!

* Data block for trigonomic values
TRGDAT BYTE 0,6,12,18,25,31,37,43
       BYTE 49,56,62,68,74,80,86,92
       BYTE 97,103,109,115,120,126,131,136
       BYTE 142,147,152,157,162,167,171,176
       BYTE 181,185,189,193,197,201,205,209
       BYTE 212,216,219,222,225,228,231,234
       BYTE 236,238,241,243,244,246,248,249
       BYTE 251,252,253,254,254,255,255,255

* R0 = Radius
* R1 - Angle (0-255)
* R2 = Position Adjustment
TRIGX  AI   R1,64                      * Add 64 to angle
       ANDI R1,>00FF                   * Keep in 0-255 range
TRIGY  MOV  R1,R3
       SRL  R3,6                       * Divide angle by 64
       JEQ  TG1                        * If 0 (first quadrant) goto TG1
       CI   R3,1
       JEQ  TG2                        * If 1 (second quadrant) goto TG2
       CI   R3,2                       * If 2 (third quadrant) goto TG3
       JEQ  TG3                        * Otherwise is 3 (fourth quadrant)
       MOVB @TRGDAT(R1),R2             * Copy ratio of angle
       SRL  R2,8                       * Adjust for full register
       AI   R2,-256                    * Adjust angle by -256
       ABS  R2                         * Make angle absolute value
       MPY  R0,R2                      * Multiply radius by angle
       DIV  @W256,R2                   * Divide total by 256
       NEG  R2                         * Negate position change value
       JMP  TG4                        * End routine
TG1    MOVB @TRGDAT(R1),R2             * Copy ratio of angle
       SRL  R2,8                       * Adjust for full register
       MPY  R0,R2                      * Multiply radius by angle
       DIV  @W256,R2                   * Divide total by 256
       JMP  TG4                        * End routine
TG2    MOVB @TRGDAT(R1),R2             * Copy ratio of angle
       SRL  R2,8                       * Adjust for full register
       AI   R2,-256                    * Adjust angle by -256
       ABS  R2                         * Make angle absolute value
       MPY  R0,R2                      * Multiply radius by angle
       DIV  @W256,R2                   * Divide total by 256
       JMP  TG4                        * End routine
TG3    MOV  @TRGDAT(R1),R2             * Copy ratio of angle
       SRL  R2,8                       * Adjust for full register
       MPY  R0,R2                      * Multiply radius by angle
       DIV  @W256,R2                   * Divide total by 256
       NEG  R2                         * Negate position change value
TG4    RT                              * End routine

That’s all for now!

AtariAge TI-99/4a Programming Forum

TI-99/4a Tech Pages (Real number section)

Wikipedia: Methods of Computing Square Roots

This entry was posted on Tuesday, February 9th, 2010 at 11:33 pm and is filed under Code, Development, TI-99/4a. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

  1. Stu says:
    February 12, 2010 at 8:57 am

    I remember using qbasic a lot to generate sin tables of various lengths for quick lookups etc..

    worse, I remember some home computers not even having a div instructions :( and using BCD for numbers.. oooh bcd :(

  2. adamantyr says:
    February 12, 2010 at 9:17 am

    Yeah, the 6502 was awful to program in. Two registers, one accumulator, and NO multiplication or division supported in hardware. You spent a lot of instructions just pushing stuff into and out of accumulators.

    TMS9900 assembly, by contrast, is nearly identical to programming in a modern PC assembly. (16-bit/32-bit era, anyway) It’s overall slower since it has to reference to external memory, but the flexibility is a very powerful tool.

  3. Calibrator says:
    February 12, 2010 at 1:45 pm

    The TMS9900 is a good processor, in some aspects even a great one while the 6502 is a much simpler design – for a much lower price point: Around $25 a piece which was unheard of at 1975. It was designed to be cheap and quickly adopted. It offers some interesting things, too, like the zero page (instead of scratchpad RAM for the registers) and it’s shitload of addressing modes. What I like perhaps the most about it, however, is the clean assembly code with three-letter mnemonics – it’s just easy to read and perhaps even more qualified for handcrafting assembly code.
    The 9900 on the other hand looks more like something a compiler might feel itself at home – similar to the 68K platform.
    I just wish there would have been more home platforms for this chip than just the TI 99/4(a) – at least one that was specifically created with the 9900 in mind and making use of it’s strengths…

  1. There are no trackbacks for this post yet.

Leave a Reply