TAOCP 4.4 Exercise 13

Let x=(.

taocpmathematicsalgorithmsvolume-2medium

Section 4.4: Radix Conversion

Exercise 13. ▶ [25] Assume that locations $U+1$, $U+2$, $\ldots$, $U+m$ contain a multiple-precision fraction $(.u_1 u_2 \ldots u_m)_b$ where $b$ is the byte size of MIX. Write a MIX routine that converts this fraction to decimal notation, truncating it to 180 decimal digits. The answer should be printed on two lines, with the digits grouped into 20 blocks of nine each separated by blanks. (Use the CHAR instruction.)

Verified: no
Solve time: 7m41s

Solution

Let

$$ x=(.u_1u_2\cdots u_m)b =\sum{i=1}^{m}u_i b^{-i}, \qquad 0\le u_i<b, $$

be stored in locations $U+1,\ldots,U+m$, one base-$b$ digit per word.

The standard decimal-conversion method for fractions is:

$$ x_0=x, $$

and for $k=1,2,\ldots,180$,

$$ 10x_{k-1}=d_k+x_k, \qquad 0\le d_k\le 9, \qquad 0\le x_k<1. $$

Then $d_1d_2\cdots d_{180}$ are precisely the first $180$ decimal digits of $x$, truncated after the $180$-th digit.

Hence we must repeatedly:

  1. Multiply the current fraction by $10$.
  2. Extract the integer part $d_k$.
  3. Retain the fractional part for the next step.

Because the fraction is represented in base $b$, multiplication by $10$ is performed by a right-to-left carry propagation.

Memory layout

Assume:

  • $U+1,\ldots,U+m$: current fraction digits $u_1,\ldots,u_m$.
  • $D$: beginning of a table of $180$ words used to store the decimal digits.
  • $TEN$: word containing $10$.
  • $BETA$: word containing $b$.
  • $ZERO$: word containing $0$.

Registers:

  • $I1$: address of current fraction word.
  • $I2$: address of current output digit.
  • $I3$: digit counter.
  • $I4$: temporary index.
  • $X$: carry.

The carry never exceeds $9$, since

$$ 10(b-1)+9=10b-1, $$

hence

$$ \left\lfloor \frac{10(b-1)+9}{b}\right\rfloor = 9. $$

Therefore one word is sufficient for the carry.

Generation of the 180 decimal digits

Suppose the current fraction is

$$ (.u_1u_2\cdots u_m)_b . $$

Set $c=0$. For $i=m,m-1,\ldots,1$ compute

$$ t=10u_i+c, $$

$$ u_i \leftarrow t\bmod b, $$

$$ c\leftarrow \left\lfloor \frac{t}{b}\right\rfloor . $$

After the loop,

$$ 10(.u_1u_2\cdots u_m)_b = c + (.u'_1u'_2\cdots u'_m)_b . $$

Since the original number is $<1$,

$$ 0\le c\le 9, $$

and $c$ is exactly the next decimal digit.

Store $c$ in the digit table and repeat $180$ times.

The following MIX routine performs this operation.

         ORIG 2000

START    ENT2 D            * next position in digit table
         ENT3 180          * 180 digits required

DIGIT    ENTX 0            * carry := 0
         ENT1 U+M          * start with least significant word

MPY10    LDA 0,1           * u_i
         MUL TEN           * rA:rX = 10*u_i

         STA TEMP          * save high part
         STX TEMP+1        * save low part

         LDA TEMP+1        * low part = 10*u_i
         ADD CARRY         * + carry

         STA TEMP+1

         LDA TEMP          * form dividend in rA:rX
         LDX TEMP+1

         DIV BETA          * quotient in A, remainder in X

         STX 0,1           * new base-b digit
         STA CARRY         * new carry

         DEC1 1
         J1P MPY10

         LDA CARRY         * decimal digit obtained
         STA 0,2
         INC2 1

         DEC3 1
         J3P DIGIT

After termination,

$$ D,D+1,\ldots,D+179 $$

contain the $180$ decimal digits.

Packing digits for output

The digits must be printed as

$$ 20 $$

blocks of nine digits, with a blank after each block. Ten blocks are printed on each line.

A word can hold five characters after a CHAR instruction. Therefore a block of nine digits is output as:

  • first five digits in one word,
  • remaining four digits followed by a blank in a second word.

Thus each block occupies exactly two output words.

Let $P$ denote the beginning of a print buffer. Each line contains

$$ 10\times 2=20 $$

words.

The packing routine is:

PACK     ENT1 D            * source digits
         ENT4 P            * print buffer

         ENT3 20           * 20 blocks

BLOCK    LDA 0,1
         SLA 6
         ADD 1,1
         SLA 6
         ADD 2,1
         SLA 6
         ADD 3,1
         SLA 6
         ADD 4,1
         CHAR
         STA 0,4           * first 5 digits

         INC4 1

         LDA 5,1
         SLA 6
         ADD 6,1
         SLA 6
         ADD 7,1
         SLA 6
         ADD 8,1
         SLA 6
         ADD BLANK
         CHAR
         STA 0,4           * last 4 digits + blank

         INC4 1
         INC1 9

         DEC3 1
         J3P BLOCK

Here BLANK contains the MIX character code for a blank.

Printing

The first twenty words of the print buffer contain the first ten blocks; the next twenty words contain the last ten blocks.

         OUT P(PRINTER)
         OUT P+20(PRINTER)
         HLT

The output has the form

ddddddddd ddddddddd ··· ddddddddd
ddddddddd ddddddddd ··· ddddddddd

with ten blocks on each line and $180$ digits altogether.

Correctness

We prove that the routine outputs the first $180$ decimal digits of $x$.

For one iteration, let

$$ x=(.u_1u_2\cdots u_m)_b. $$

The right-to-left loop computes numbers $u'_i$ and $c$ satisfying

$$ 10u_i+c_{i+1}=c_i b+u'_i, \qquad 0\le u'_i<b. $$

Summing these relations with weights $b^{-i}$ yields

$$ 10x = c_1 + (.u'_1u'_2\cdots u'_m)_b . $$

Since $0\le x<1$, we have $0\le c_1\le 9$. Thus $c_1$ is the decimal digit

$$ \lfloor 10x\rfloor, $$

and the updated fraction is

$$ 10x-c_1. $$

Therefore each pass produces exactly the next decimal digit and leaves the correct remainder for the next pass.

After $180$ iterations, the table $D$ contains

$$ d_1,d_2,\ldots,d_{180}, $$

the first $180$ decimal digits of $x$. The packing routine merely rearranges these digits into twenty groups of nine, inserting blanks after each group. The two OUT instructions print the first ten groups on one line and the remaining ten groups on the second line.

Hence the routine prints the decimal expansion of $x$, truncated after $180$ digits, in the required format. ∎