Chapter 7 Practice Exercises: Prime Finding in X-Toy

Prime finding in X-Toy

In this assignment, you will implement two prime-finding algorithms, the trivial prime finder and the sieve of Eratosthenes, entirely in the X-Toy assembly language, and then compare their runtimes.

In years of teaching this course, I have found that students report that this is their favorite assignment because it ties the course together. I have also seen the most resistance to it, so I would say this: picture yourself finishing and loving the experience that it gave you. Keep that in mind during the journey.

Learning objectives

In completing this assignment, you will:

• see how high-level algorithmic ideas like primality testing translate into register operations, jumps, and memory manipulation;
• practice reasoning about control flow when function calls, returns, and loops must be implemented by hand;
• emulate data structures like Boolean arrays and counters using raw memory;
• contrast the efficiency of the trivial prime finder and the sieve of Eratosthenes when expressed at the machine level, and see firsthand how the sieve achieves its speedup by avoiding repeated work;
• gain confidence reading, debugging, and extending assembly programs by tracking program state across registers and memory.

Function hierarchy

The two programs that you will write are organized as follows.

Trivial prime finder

main
├─ TrivialPrimeFinder
│  └─ IsPrime
│     ├─ Multiply
│     └─ IsDivisor
└─ PrintBools

Sieve of Eratosthenes

main
├─ SieveOfEratosthenes
│  └─ CrossOffMultiples
└─ PrintBools

Each function lives in a fixed range of memory addresses and communicates through designated registers, which are described in the interface accompanying each exercise below.

Important notes

• Use the correct return registers. Each function has a designated link register; using the wrong one will silently corrupt control flow.
  • Trivial prime finder: main calls TrivialPrimeFinder using RD; TrivialPrimeFinder calls IsPrime using RE; IsPrime calls Multiply and IsDivisor using RF; and main calls PrintBools using RF.
  • Sieve of Eratosthenes: main calls SieveOfEratosthenes using RE; SieveOfEratosthenes calls CrossOffMultiples using RF; and main calls PrintBools using RF.
• Memory layout matters. Each function may write only to the memory cells listed in its interface, and the autograders check that no other cells are modified. Across both programs, the legal data cells are:
  • M[00], which holds n (written by main);
  • M[01], scratch space that TrivialPrimeFinder uses to preserve p across each IsPrime call;
  • M[0x80 + p] for 0 ≤ p ≤ n, the primeBooleans array;
  • M[FF], standard input and output.
• R0 is always zero. Writes to R0 are silently discarded, so do not use it as scratch storage. It is useful as a constant 0 operand (for example, 1410 copies R1 into R4 via R4 <- R1 + R0) or for unconditional jumps (C0xx means “if R0 == 0, go to xx”, which is always taken).
• Avoid register corruption across calls. If a function needs a value to survive a subroutine call, either confirm that the subroutine’s interface lists that register as preserved, or save the value to memory before the call and reload it afterward. For example:
  • TrivialPrimeFinder stores p in M[01] before each IsPrime call because IsPrime clobbers R1;
  • SieveOfEratosthenes reloads n from M[00] after each CrossOffMultiples call because CrossOffMultiples consumes R2.
• Respect each function’s temporary registers. The temporary registers listed in a function’s interface are the complete list of registers that the function may clobber. Writing to any other register breaks the contract with its callers; even if your code works in isolation, it will fail when combined with the rest of the program.
• Loops must terminate. A function that hangs almost always has either a bad branch target or a loop counter that is not being updated.
  • In Visual X-TOY, use the step button to single-step through the suspect loop. If the same instruction fires on every iteration without changing your loop variable, you have found the bug.
  • Watch for a counter that gets clobbered by a subroutine call.
  • Watch for a JMP0 or JMPP whose target points back into the loop body without first running the increment instruction.
• Test each function independently, starting from the bottom of the hierarchy. For the trivial prime finder, work in the order Multiply, IsDivisor, IsPrime, TrivialPrimeFinder, main. For the sieve, work in the order CrossOffMultiples, SieveOfEratosthenes, main. PrintBools is independent and can be written at any time, as long as a valid primeBooleans array exists in memory starting at M[80].

The trivial prime finder

Testing divisibility

We begin with a function that tests whether one integer divides another using repeated subtraction. If k is 0, the function immediately returns 0, since 0 divides no number. Otherwise, it repeatedly subtracts k from p until the remainder becomes 0, in which case k is a divisor of p and the function returns 1, or the remainder becomes negative, in which case k does not divide p and the function returns 0.

Interface

• Memory addresses: starting address 50, last allowable address 5F.
• Inputs:
  • R1 = p (an integer)
  • R2 = k (the potential divisor)
• Outputs:
  • R3 = 1 if k is a divisor of p, and R3 = 0 otherwise
• Temporary registers (clobbered; callers must not rely on these being preserved):
  • R3, R4
• Preserved registers (callers can rely on these being unchanged):
  • R0, R1, R2, R5, R6, R7, R8, R9, RA, RB, RC, RD, RE, RF
• Memory usage:
  • None (no memory reads and no memory writes)
• Return: returns to the caller via RF (EF00).

Multiplication

Next, we need a function that computes the product a * b as the repeated addition a + a + ... + a with b summands.

Interface

• Memory addresses: starting address 30, last allowable address 3F.
• Inputs:
  • R3 = a (an integer)
  • R4 = b (an integer, consumed by the function)
• Outputs:
  • R6 = a * b
• Temporary registers (clobbered; callers must not rely on these being preserved):
  • R1, R4, R5, R6
  • R4 decrements to zero by the time the loop exits.
  • R5 is left holding the loop’s jump-back address (0x33), not 0 or 1, after the function returns. Callers that need a known value in R5 after the call must reinitialize it themselves.
• Preserved registers (callers can rely on these being unchanged):
  • R0, R2, R3, R7, R8, R9, RA, RB, RC, RD, RE, RF
• Memory usage:
  • None (no memory reads and no memory writes)
• Return: returns to the caller via RF (EF00).

Testing primality

Recall that IsPrime() can be represented in pseudocode as follows.

IsPrime(p)
    for every integer k between 2 and √p
        if k is a divisor of p
            return false
    return true

Interface

• Memory addresses: starting address 60, last allowable address 7F.
• Inputs:
  • R1 = p (the number being tested)
• Outputs:
  • R2 = 1 if p is prime, and R2 = 0 otherwise
• Temporary registers (clobbered; callers must not rely on these being preserved):
  • R1, R2, R3, R4, R5, R6, R7, R8, R9, RF
  • R1 is the input p, but it is consumed during execution.
• Preserved registers (callers can rely on these being unchanged):
  • R0, RA, RB, RC, RD, RE
  • RE is this function’s return-address register; IsPrime reads it but never writes it.
• Memory usage:
  • None; all scratch values are held in registers. (Because Multiply clobbers R5, you may need to reinitialize R5 on every iteration of your loop.)
• Return: returns to the caller via RE (EE00).

Multiply()

• Memory: lines 30 through 3F
• Inputs: R3 = a, R4 = b
• Output: R6 = a * b
• Clobbers: R1, R4, R5, R6 (R5 is left holding 0x33 after the call, not 1)
• Preserves: R2, R3, and R7 through RF
• Return address: RF

IsDivisor()

• Memory: lines 50 through 5F
• Inputs: R1 = p, R2 = k
• Output: R3 = 1 if R2 divides R1, and 0 otherwise
• Clobbers: R3, R4
• Preserves: R1, R2, and R5 through RF
• Return address: RF

Finding primes

Recall that TrivialPrimeFinder() can be represented in pseudocode as follows. It is now time to implement it!

TrivialPrimeFinder(n)
    primeBooleans ← array of n + 1 false boolean variables
    for every integer p from 2 to n
        if IsPrime(p) is true
            primeBooleans[p] ← true
    return primeBooleans

Interface

• Memory addresses: starting address 18, last allowable address 2F.
• Inputs:
  • None directly; reads n from M[00].
• Outputs:
  • None directly; for each integer p with 2 ≤ p ≤ n, stores 1 at M[0x80 + p] if p is prime, and 0 otherwise.
• Temporary registers (clobbered; callers must not rely on these being preserved):
  • R1, R2, R4, R5, R6, R7, RE
  • RE is clobbered because TrivialPrimeFinder calls IsPrime using JAL RE, 60 (FE60), which overwrites RE with the return address.
• Preserved registers (callers can rely on these being unchanged):
  • R0, RA, RB, RC, RD
  • RD is this function’s return-address register; TrivialPrimeFinder reads it but never writes it.
• Memory usage:
  • Reads M[00] (n) and M[01] (the saved copy of p).
  • Writes M[01] (scratch space holding p across each IsPrime call) and M[0x80 + p] for 2 ≤ p ≤ n. No other memory cells are modified.
• Return: returns to the caller via RD (ED00).

IsPrime()

• Memory: lines 60 through 7F
• Input: R1 = p
• Output: R2 = 1 if p is prime, and 0 otherwise
• Clobbers: R1, R2, R3, R4, R5, R6, R7, R8, R9, RF
• Preserves: RD, RE (RE is the return register, which is read but not written)
• Return address: RE

Printing primes

Now that we can find primes and store them in memory, we would like to print all the primes up to a given number.

Interface

• Memory addresses: starting address 40, last allowable address 4F.
• Inputs:
  • None directly; reads n from M[00].
• Outputs:
  • None directly; prints each integer p such that M[0x80 + p] is 1 to standard output (M[FF]).
• Temporary registers (clobbered; callers must not rely on these being preserved):
  • R1, R2, R4, R5, R7, R9
  • Because PrintBools runs at the end of the program, callers do not need to preserve any of these.
• Preserved registers (callers can rely on these being unchanged):
  • R0, R3, R6, R8, RA, RB, RC, RD, RE, RF
  • RF is this function’s return-address register; PrintBools reads it but never writes it.
• Memory usage:
  • Reads M[00] (n) and M[0x80 + p] for 0 ≤ p ≤ n.
  • Writes M[FF] (standard output), once per prime found. No other memory cells are modified.
• Return: returns to the caller via RF (EF00).

The sieve of Eratosthenes

Crossing off multiples

Recall that CrossOffMultiples(), the main subroutine of the sieve of Eratosthenes, can be represented in pseudocode as follows.

CrossOffMultiples(primeBooleans, p)
    n ← length(primeBooleans) - 1
    for every multiple k of p (from 2p to n)
        primeBooleans[k] ← false
    return primeBooleans

Interface

• Memory addresses: starting address 50, last allowable address 5F.
• Inputs:
  • R1 = p (the prime whose multiples we cross off)
  • R2 = n (the largest number we are sieving up to)
• Outputs:
  • None directly; writes 0 to M[0x80 + k] for each multiple k of p between 2p and n.
• Temporary registers (clobbered; callers must not rely on these being preserved):
  • R2, R3, R4, R5, R6
  • R2 is the input n, but it is consumed during the loop. Callers that need n after the call must save it themselves (for example, to M[00]) before calling.
• Preserved registers (callers can rely on these being unchanged):
  • R0, R1, R7, R8, R9, RA, RB, RC, RD, RE, RF
• Memory usage:
  • Reads: none.
  • Writes M[0x80 + k] for each multiple k = 2p, 3p, and so on, up to and possibly including n. No other memory cells are modified.
• Return: returns to the caller via RF (EF00).

Sieving

We now turn to SieveOfEratosthenes(), whose pseudocode is shown below.

SieveOfEratosthenes(n)
    primeBooleans ← array of n + 1 true boolean variables
    primeBooleans[0] ← false
    primeBooleans[1] ← false
    for every integer p between 2 and √n
        if primeBooleans[p] = true
            primeBooleans ← CrossOffMultiples(primeBooleans, p)
    return primeBooleans

Interface

• Memory addresses: starting address 20, last allowable address 3F.
• Inputs:
  • R2 = n
• Outputs:
  • None directly; for each integer p with 0 ≤ p ≤ n, stores a primality flag at M[0x80 + p].
• Temporary registers (clobbered; callers must not rely on these being preserved):
  • R1, R2, R3, R4, R5, R6, R9, RF
  • R2 is the input n, but it is consumed during the function.
• Preserved registers (callers can rely on these being unchanged):
  • R0, R7, R8, RA, RB, RC, RD, RE
  • RE is this function’s return-address register; SieveOfEratosthenes reads it but never writes it.
• Memory usage:
  • Reads M[00] (n is reloaded after R2 is consumed).
  • Writes M[00] (n is stored here on entry as a safety copy) and M[0x80 + p] for 0 ≤ p ≤ n; in particular, M[80] and M[81] are set to 0. No other memory cells are modified.
• Return: returns to the caller via RE (EE00).

Putting it all together

Once all your functions pass their autograders, complete the main function at address 10 of each starter file. In trivial_prime_finder_starter.toy, main should read n from standard input, store it at M[00], call TrivialPrimeFinder and then PrintBools, and halt. In sieve_of_eratosthenes_starter.toy, main should do the same with SieveOfEratosthenes in place of TrivialPrimeFinder.

Then, run both programs on increasing values of n and compare their runtimes. How much faster is the sieve at the machine level?