<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">This implementation in \MMIX\ of Algorithm~A has made
some changes to the input format of the data compared
to the \MIX\ version.
First the reader is replaced by a file and the output is
sent to StdOut. It is assumed that StdOut can handle lines
of arbitrary length.
Next, the line length for the input is still 80 bytes but now
20~fields of 4~bytes each are formed. The length of an
input line might be shorter so no fields with 4~spaces are
considered. The equal sign is kept but it plays no role
in the implementation. Its tetra in memory is used as
a temporary storage.
Third, all symbols are placed flush right in their fields.

Some aspects have not been changed.
The MSB of the tetra that is build from the 4~bytes of a
field is used to tag elements. So negative values indicate
a tagged element as in the \MIX\ implementation.
No error checking for the input data is implemented.
The frequency counts uses the same letters as in the old
implementation if it was possible. The variable `S' is no
longer needed and a new frequency counter `O' is introduced.
And the implementation was done in a way that the loops in
steps A2 and A4 use the same number of mems and oops.
This allows to keep the analysis similar to the \MIX\ program.
Of course, a faster implementation is possible.

The algorithm needs without input and output
$(A+2C+D+G+3H+2J+K+O+Q+2R)\mems + (8+3A+7B+5C+3D+E+3F+2G+9H+4J+5K+4L+4P+3O+4Q+8R)\oops$.

As in \eq(8) of TAOCP V1, Section 1.3.3, the following equations hold: 
$$A=C;\qquad E=R+1;\qquad R=P-Q.$$
And we find the new equations
$$\eqalign{
    F&amp;=E+G-H=G-H+P-Q+1;\cr
    G&amp;=F-1;\cr
    J&amp;=H+O \iff O=J-H;\cr}
\qquad\eqalign{
    L&amp;=J+Q=H+O+Q;\cr
    P&amp;=L-O=H+Q \iff Q=P-H.\cr}$$
Applying these equations to the used mems and oops several variables are eliminated:
$(2B+C+D+G+3H+3J+K+P)\mems + (7B+8C+3D+5G+7H+11J+5K+12P+12)\oops$.

Next, the following equations hold:
$$\eqalign{ B+C &amp;= \rb{number of words of input;}\cr
            B   &amp;= \rb{number of ``('' in input;}\cr
            D   &amp;= \rb{number of ``)'' in input;}\cr
            B=D &amp;= \rb{number of cycles in input;}\cr
            H   &amp;= \rb{number of cycles in output (inclusive singletons);}\cr
            B+C &amp;= B+B+H+O \iff J=C-B\ \rb{as all symbols get tagged once;}\cr
            P   &amp;= \rb{number of distinct elements in input.}\cr}$$
And the nontrivial relation is now $F+J+K=(B+C)(P+1)$. The first
left parenthesis is skipped but a sentinel is read.

With the variables of \eq(19) the profile of the algorithm is
$(NY+4Y-2M+N+3U-1)\mems + (5NY+19Y-10M+12N+7U+7)\oops$.

Running the program with \eq(6) as input the \MMIX-simulator shows at the end:
{\tt 1569 instructions, 330 mems, 1705 oops; 305 good guesses, 50 bad}.
With this input it follows that $Y=29$, $N=7$, $M=5$, and $U=3$.
The algorithm itself needs
{\tt 1532 instructions, 324 mems, 1628 oops; 300 good guesses, 48 bad}.
As expected the following equations hold:
$11*29-10+7+9-1=324$ and $54*29-50+84+21+7=1628$.
</pre></body></html>