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!