Division and decimal conversion

CBD - Convert Binary to Decimal

Unlike some contemporary machines the 1900 has no decimal arithmetic instructions. All calculation is done in binary. In order to run languages like COBOL at reasonable speed a fast way was needed to convert between binary and decimal (character) representations.

This was the CBD (Convert Binary to Decimal) instruction:

CBD X N(M)

The CBD instruction multiplies the positive double-length binary fraction in X and X* by ten. The integral part of the product is then stored as a decimal character in the position specified by N(M), and the fractional part is left in XX*

Use

So, how to use this? What is a "double length binary fraction"?

To produce the "n" digit decimal representation of a binary number we first divide the number by 10ⁿ, then repeatedly run the CBD instruction to get each digit of the number.

For example, to output the number 313149 in six positions we do:

num = 314149
frac = num / 1000000       [ frac = 0.314159
for 1 .. 6
    digit = CBD frac       [ digit = 3, frac = 0.14159 and so on

Or, in real PLAN (Thanks to Brian Spoor):

      LDX   2  '5/CHAR+0.0'        [ 6 DIGIT O/P PTR
      LDN   5  0                   [ MAKE DOUBLE LENGTH (X4/X5)
      DVR   4  '1000000'           [ INTEGER IN X4
      LDCT  6  #200                [ ROUND UP FOR CONVERSION
      MODE     1                   [ SET ZERO SUPPRESSION
      CBD   5  0(2)                [ CONVERT DIGIT
      BCHX  2  *-1                 [ REPEAT FOR 5 DIGITS
      MODE     0                   [ CLEAR ZERO SUPPRESSION
      CBD   5  0(2)                [ CONVERT FINAL DIGIT

(The MODE instruction is used to convert leading zeroes to spaces).

But what if we want to output MAXINT? The largest single length integer on the 1900 is 8388607, seven decimal digits, so we need to divide by 10.000.000, which is (obviously) a double length quantity.

The problem is that the 1900 doesn't have a double length divide instruction. (It can divide a double length number by a single length number, but if the result doesn't fit into a single length number it will overflow).

Magic numbers to the rescue!

The following obscure code is how ICL did it (although this appears nowhere in the documentation):

#
#
#     BINARY TO DECIMAL CONVERSION USING MAGIC NUMBER.
#     PRODUCES MAX. 7 LEADING ZERO SUPRESSED DIGITS,
#     PLUS A TRAILING SIGN (+/-) - 8 CHARS IN ALL.
#
#     ON ENTRY X1 = LINK ACCUMULATOR
#              X2 = CT/MOD FOR OUTPUT, 1 CHAR LESS THAN REQUIRED
#              X4 = INTEGER FOR CONVERSION
#
#     ALTERS   X2&  X4
#     USES     X5&  X6
#
#
MCONV  LDN   6  #33                 [ X6 = '+' SIGN
       MPY   4  '+7036875'          [ TIMES CONVERSION FACTOR
       BPZ   4  *+4                 [ J IF NUMBER POSITIVE
       NGXC  5  5                   [ MAKE LOW WORD POSITIVE
       NGX   4  4                   [ MAKE AND HIGH WORD POSITIVE
       LDN   6  #35                 [ X6 = '-' SIGN
       MODE     1                   [ SET ZERO SUPPRESSION
       CBD   4  0(2)                [ CONVERT DIGIT
       BCHX  2  *-1                 [ REPEAT UNTIL LAST DIGIT
       MODE     0                   [ UNSET ZERO SUPPRESSION
       CBD   4  0(2)                [ CONVERT LAST DIGIT
       BCHX  2  *+1                 [ STEP POINTER
       DCH   6  0(2)                [ ADD TRAILING SIGN
       EXIT  1  0                   [ RETURN

But how does it work? What does it do? What is 7036875?

Comments in some ICL code claim that 7036875 is 2⁴⁶/10⁷, which it is, if the division is done rounding up.

So what the magic constant does is simultaneously multiply the number by 2⁴⁶, pushing the bit before the decimal point up above the first bit of the double-word result and divide the number by 10⁷, to make the binary fraction we want.

val .
val . 0 0
. val/10⁷

And what about multi-length integers?

Timing

The CBD instruction is quite fast, on the original 1904:

Instruction Microseconds

CBD 28
MPY 40
DVS 44
SRA 15+N

Instruction	Microseconds
CBD	28
MPY	40
DVS	44
SRA	15+N

How does CBD manage to be so much faster than MPY? Examination of the 1904 microcode shows that it does the "multiply by 10" operation as

x_times_10 = ( x + x * 4 ) * 2

where the multiplications are of course done by shifts. (The 1900 hardware could only do one bit shifts, so this is three shifts and an add. Stil much faster than a general multiply).