# 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 10n, 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 246/107, which it is, if the division is done rounding up.

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

1.  val .
2.  val . 0 0
3.  . val/107

### Timing

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

Instruction Microseconds
CBD28
MPY40
DVS44
SRA15+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).