e-smith@utah-cs.UUCP (Eric L. Smith) (12/01/84)
[Let's give the line-eater terminal indeigestion!] Here is my entry to the roman numeral contest (for the 6809, 48 bytes total): ******************************************************************************* VALTBL FCB 100,'C+$80 FCB 90,'X+$80,'C+$80 FCB 50,'L+$80 FCB 40,'X+$80,'L+$80 FCB 10,'X+$80 FCB 9,'I+$80,'X+$80 FCB 5,'V+$80 FCB 4,'I+$80,'V+$80 FCB 1,'I+$80 * The first byte after this table must have the MSB 0. In this case my * first instruction of the routine satisfies this. If you don't like * this type of trick, or want to put the code first, you'll have to add a * zero byte. * Enter with byte to be output as roman numerals in B register. Destroys * A, B, X, Y, and CCR ROMAN LEAX <VALTBL,PCR get the address of the data table MAINLP TSTB test for completion BEQ EXIT CMPLP CMPB ,X+ compare what's left against table, adv ptr BLO CMPLP if smaller, try next LDAY ,X ASCII of roman numeral follows value SUBB ,-X subtract the value, moving pointer back first PRNTLP LDA ,Y+ get the next byte from table BPL MAINLP if MSB=0 then done printing this one AND #$7F mask off MSB (unnecessary on many systems) JSR PRINT output the character BRA PRNTLP try for another character EXIT RTS ******************************************************************************* The PRINT routine is assumed to output the character in the A register without destroying B, X, or Y. I have tested this program under level one OS-9 on a CoCo, with the minor change of JSR PRINT to LBSR PRINT (no increase in code size). For the source of the complete program send me mail. Note that this routine is completely position independent and uses no static (or even stack) storage. It does not appear that it could be written any more compactly in absolute code, although a few clock cycles might be saved. While I have not calculated the worst case timing, I have devised a formula for the number of clock cycles for any given case, based on the following variables: p = number of cycles taken by print routine (assumed constant) P = total number of characters printed (i.e., P('CIC') = 3) M = number of iterations through main loop = number of pieces of roman numeral printed (piece = I, IV, V, IX, etc.) C = number of comparisons done. This is a little harder to determine since comparisons are done not only against the values, but also the ASCII characters (these compares always fail). Also, if a compare succeeds (B > value) then after the characters are printed the same compare is performed again T (total clock cycles) = 15 + 24*M + 9*C + (22+p)*P I have also coded a 6502 version of the same algorithm (which I will provide on request), which is 60 bytes long, primarily due to the availability of only one accumulator, and the need for a four instruction sequence to transfer the X register to the Y register (PHA, TXA, TAY, PLA). If I remember correctly, the 65C02 has a TXY instruction which would save 6 bytes. If anyone can provide a routine shorter than 48 bytes (code and data) for any processor, I would very much like to see it. -- --------------------------------------------------------------------------- Reality (for those who can't face computers): Eric L. Smith UUCP/UseNet: ...decvax!utah-cs!e-smith ARPA: e-smith@utah-20 U.S.Snail: 230 S. 500 W. Suite 133, Salt Lake City, UT, 84101 AT&T and suchlike: (801) 581-8100 (work), (801) 582-3371 (home) --------------------------------------------------------------------------- The opinions expressed herein do not necessarily represent those of the University of Utah, my friends, enemies, computer, or even me. I make no warranty, express or implied, as to the accuracy of this information of its fitness for any particular purpose. I assume no liability for any damages, actual or alleged, directly or indirectly resulting from the use of or inability to use this information. So there!