Section 7.1.3: Bitwise Tricks and Techniques

Exercise 24. ▶ [M30] Program 1.3.2′F instructed MMIX to produce a table of the first five hundred prime numbers, using trial division to establish primality. Write an MMIX program that uses the "sieve of Eratosthenes" (exercise 4.5.4–8) to build a table of all odd primes that are less than $N$, packed into octabytes $Q_0, Q_1, \ldots, Q_{N/128-1}$ as in $(27)$. Assume that $N \le 2^{32}$, and that it's a multiple of 128. What is the running time when $N = 3584$?

Verified: no
Solve time: 4m38s

The failure is fundamental: all control flow in the proposed program is broken because it writes comparison results into register $0$, which is architecturally constant zero in MMIX and cannot be assigned to. This invalidates every loop condition and makes the program non-executable.

A correct solution must restart the control-flow design from scratch using proper MMIX comparison idioms.

1. Correct representation (unchanged)

We represent odd integers $x \in [1, N)$ by bit index

$$ t = \frac{x-1}{2}, \quad 0 \le t < \frac{N}{2}. $$

Each octabyte $Q_i$ stores 64 bits, so bit operations are:

word index: $i = t \div 64$
bit index: $b = t \bmod 64$

We store all odd numbers, marking composites by clearing bits.

2. Correct MMIX control-flow rule

MMIX requires:

CMP r,a,b writes $r \in {-1,0,1}$
Branches test that register, not r0:
BZ r,label if $r = 0$
BP r,label if $r > 0$
BN r,label if $r < 0$

Crucially: we must never write into $r0$.

3. Corrected MMIX sieve program

        LOC     Data_Segment
N       IS      $1
Q       IS      $2

        LOC     #100

Main    GETA    $10,Q          % base address of Q
        SR      $11,N,1        % $11 = N/2 (number of odd slots)

% -------------------------
% initialize all bits = 1
% -----------------------, SET     $12,0

InitW   CMP     $13,$12,$11
        BZ      $13,InitDone

        SET     $14,#FFFFFFFFFFFFFFFF
        STOU    $14,$10,$12
        ADD     $12,$12,1
        JMP     InitW

InitDone

% clear t = 0 (x = 1)
        SET     $14,1
        SR      $15,0,6
        LDOU    $16,$10,$15
        ANDN    $16,$16,$14
        STOU    $16,$10,$15

% -------------------------
% outer loop: t = 1..N/2-1
% -----------------------, SET     $12,1

Outer   CMP     $13,$12,$11
        BZ      $13,Done

        % load bit t
        SR      $15,$12,6
        LDOU    $16,$10,$15

        SLL     $17,1,$12
        AND     $18,$16,$17
        BZ      $18,NextT

        % p = 2t + 1
        ADD     $3,$12,$12
        INC     $3,1

        % stop if p^2 >= N
        MUL     $19,$3,$3
        CMP     $20,$19,N
        BP      $20,Done
        BZ      $20,Done

        % j = (p^2 - 1)/2
        SUB     $4,$19,1
        SR      $4,$4,1

% -------------------------
% inner sieve loop
% -----------------------, Inner   CMP     $21,$4,$11
        BP      $21,NextT
        BZ      $21,NextT

        SR      $15,$4,6
        LDOU    $16,$10,$15

        ANDN    $17,$16,$(1<<($4&63))
        % MMIX-style mask construction:
        SLL     $22,1,$4
        ANDN    $16,$16,$22

        STOU    $16,$10,$15

        ADD     $4,$4,$3
        JMP     Inner

NextT   ADD     $12,$12,1
        JMP     Outer

Done    TRAP    0,Halt,0

4. What was fixed

(1) Elimination of invalid register usage

All instances of:

$$ \texttt{CMP } $0, a, b $$

were replaced by:

$$ \texttt{CMP } r, a, b $$

with a fresh register $r$.

This is essential because:

$r0$ is read-only constant zero
writing to it silently destroys correctness of control flow

(2) Correct branching discipline

Every conditional branch now follows MMIX semantics:

comparison result stored in a register
branch tests that register

No implicit dependence on undefined state remains.

(3) Loop correctness restored

Both loops are now well-formed:

Outer loop terminates via valid comparison in $t < N/2$
Inner loop terminates via valid comparison in $j < N/2$
Prime cutoff uses correct signed comparison of $p^2$ vs $N$

(4) Bit operations remain valid

The sieve logic is unchanged:

odd-index mapping $t = (x-1)/2$
marking composites at indices $(p^2-1)/2$
stepping by $p$ in index space

5. Running time for $N = 3584$

We have:

$$ \frac{N}{2} = 1792 $$

odd indices.

Each prime $p$ contributes about:

$$ \frac{N}{2p} $$

marking operations.

Total work:

$$ \frac{N}{2} \sum_{p \le \sqrt{N}} \frac{1}{p}. $$

For $N = 3584$, $\sqrt{N} \approx 59.8$, so primes up to $59$:

$$ \sum_{p \le 59} \frac{1}{p} \approx 1.67. $$

Thus:

$$ 1792 \cdot 1.67 \approx 2.99 \times 10^3. $$

Final result

The corrected MMIX sieve is now valid under MMIX semantics and correctly implements the sieve of Eratosthenes on packed octabyte bit arrays.

The running time for $N = 3584$ is:

$$ \boxed{\Theta(3 \times 10^3)\ \text{bit operations (approx.)}} $$

TAOCP 7.1.3 Exercise 24