Skip to content
Tutorials Center
My learning

Topics

Lesson 34 of 40 ยท Projects

Project: Prime Sieve in Toy Assembly

Write the Sieve of Eratosthenes in toy assembly: an array in memory, nested loops, indexed stores. Verify it against JavaScript and a C program.

Arrays, nested loops and memory writes are what make assembly programs feel like "real" programs. The Sieve of Eratosthenes uses all three in about thirty instructions, and its answer is easy to check: a list of prime numbers. In this project you will write the sieve for the toy CPU, verify it against a reference in JavaScript, compare it with the same algorithm in C, and measure how much work it does as the limit grows.

You will need indexed addressing (Arrays and Addressing Modes) and nested loops (Writing Loops). The code runs on the toy CPU from Meet the Toy CPU; as in other TryIts the interpreter is part of the code.

The algorithm

A prime is a number greater than 1 with no divisors except 1 and itself. To find all primes up to N, the sieve keeps one flag per number, all "maybe prime" at first, and crosses out multiples:

  1. Mark every number from 2 to N as prime.
  2. Take the smallest number i that is still marked. It must be prime, because nothing smaller divides it.
  3. Cross out its multiples i*i, i*i + i, i*i + 2i, ... up to N. (Smaller multiples such as 2i were already crossed out by smaller primes, so starting at i*i is enough.)
  4. Repeat with the next marked number, and stop when i*i exceeds N: any composite number up to N has a divisor no bigger than its square root, so it was crossed out already.
  5. Every number still marked is prime.
flowchart TD
  A["mark 2..N as prime"] --> B["i = 2"]
  B --> C{"i * i <= N?"}
  C -- "no" --> H["print every marked number"]
  C -- "yes" --> D{"i still marked?"}
  D -- "no" --> G["i = i + 1"]
  D -- "yes" --> E["j = i * i"]
  E --> F{"j <= N?"}
  F -- "yes" --> F2["unmark j, j = j + i"]
  F2 --> F
  F -- "no" --> G
  G --> C

Three loops: the fill loop, the outer loop over i with an inner crossing-out loop over j, and a final reporting loop.

The data layout and the registers

Memory is our array. We pick a base address, 0x2000, and keep the flag for number i at [0x2000 + i]. In the toy CPU every memory address holds one whole value (a real machine stores each byte separately), so one cell per flag is exactly right, and the address [rsi + rcx] reaches element rcx. That base + index form is the same addressing mode a compiler uses for flag[i]; the only difference on a real machine is that a 4-byte int array multiplies the index by 4, written [rsi + rcx*4].

The registers have fixed jobs:

Register Job
rbx N, the limit
rsi base address of the flag array
rcx i, the outer candidate (and the counter in the fill and report loops)
rdx j, the multiple being crossed out
rax scratch for flags and for i*i

Nothing needs the stack: this program has no function calls, only loops. The program is a template string with the limit as a parameter, so you can change N from outside.

Run it

The sieve prints each prime with out. After it finishes, the script reads the flag array straight out of the toy CPU's memory and draws it, one character per number from 2 up, so you can see which cells ended at 1. Look at the end of the output: the picture and the list say the same thing, and the last line reports how many instructions ran.

JS The sieve up to 50

Press Run (or Ctrl + Enter) to see the console output here.

No output.

Fifteen primes, from 2 to 47, and the flag picture shows # at positions 2, 3, 5, 7, 11 and so on. Try changing N to 100 (25 primes) or to 2.

How it works, loop by loop

The fill loop writes a 1 into [rsi + rcx] for rcx from 2 to N. It uses ja (unsigned above) to leave the loop, since all our numbers are non-negative.

The outer loop computes i*i into rax and compares it with N. Doing that multiplication each time is cheap on any CPU; some compilers instead keep a running square or compare i with an integer square root. It then loads flag[i]. A test rax, rax followed by jz skips composite i without any crossing out, which is what saves most of the work.

The inner loop is only four instructions of real work: compare j with N, store 0 at [rsi + rdx], add rdx, rcx (the step is i) and jump back. Each pass touches memory with a store, and the pointer moves by a fixed stride, which is the pattern caches and prefetchers like (see Performance).

The report loop walks the array again and prints each index whose flag survived. It is a separate loop on purpose: the sieve finishes first, and only then do we read the results.

One lesson in program shape: every label needs a unique name in the toy assembler, and the loop names (fill, cross, show) read like the C loops they replace. In a long program, good label names are the difference between an assembly file you can read next month and one you cannot.

Checking against a reference

A sieve with one wrong bound (ja instead of jae, or starting j at 2*i) still prints plausible numbers for small N and goes wrong only later. So test it against an independent implementation over several limits. The script below also records how many instructions the CPU ran, divided by N.

JS Verify against JavaScript and measure the work

Press Run (or Ctrl + Enter) to see the console output here.

No output.

Every row matches. The last column is the interesting one: the sieve does roughly 20 instructions per number, and the figure creeps up only slowly as N grows by a factor of 200. In textbook terms the sieve costs about N log log N steps, nearly linear, while testing each number for divisors one by one costs far more. The algorithm, not the instruction set, decides how the work scales; assembly only fixes the constant in front.

The same sieve in C

Here is the same algorithm in C, which runs on the site's real C compiler. Compare its three loops with the three loops of the assembly: the structure is identical, and so is the output.

C The sieve in C (compiled and run on the server)

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with scanf or fgets), it gets the next line from this box.

A compiler such as GCC at -O1 turns the inner for loop into something of the following shape (read-only, typical and approximate; the registers and details vary by compiler version):

NASM
.cross:
    mov   DWORD PTR [rsp+rdx*4], 0    ; flag[j] = 0, index scaled by the size of an int
    add   edx, ecx                    ; j += i
    cmp   edx, 50                     ; j <= N ?
    jle   .cross

It is our toy inner loop almost instruction for instruction: a store through base + index*scale, an add of the step, a compare and a conditional jump. That is the practical payoff of this project. Once you can write the sieve in toy assembly, you can read what a compiler produces for it.

Ideas to extend it

  • Start j at 2 * i instead of i * i and watch the instruction count rise; the result stays correct, only slower.
  • Print the largest prime below N instead of all of them, keeping only the last survivor in a register.
  • Count primes instead of printing them (inc a counter), then compare with the known count of 168 primes below 1,000 (it appears in the table above).
  • Skip even numbers entirely, which halves the array and the fill loop.
  • Think about what changes on a real machine: use one bit per number (bts, shr, masks from Logic, Shifts and Bit Tricks) so a million-number sieve fits in L1 cache instead of megabytes of flags.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Why can the outer loop of the sieve stop once i * i is greater than N?

    If a composite c <= N had only divisors above sqrt(N), their product would exceed N. So c has a small divisor and was crossed out while processing that smaller prime.
  2. 2. What does the instruction mov [rsi+rdx], rax do in the inner loop when rax is 0?

    The brackets mean memory at the address base + index. With the value on the right, this is a store: flag[j] = 0.
  3. 3. Why does the toy assembly use [rsi+rcx] while a C compiler for an int array writes [rsp+rdx*4]?

    Real memory is addressed by byte, so element i of a 4-byte-element array lives at base + 4*i. Our toy memory holds a whole value per address, so no scaling is needed.
  4. 4. The measured instructions per number rose only from 19 to 22 while N grew 200 times. What does this tell you?

    Total work is about N log log N, so work per number grows extremely slowly. Algorithm choice dominates the cost far more than individual instructions do.

Summary

  • The Sieve of Eratosthenes keeps one flag per number, crosses out multiples starting at i*i, and stops when i*i > N.
  • In assembly it is three loops over an array in memory; [base + index] is the addressing mode for flag[i], and a real compiler adds a scale for element size.
  • Give each register one job and each label a clear name; the program then reads like the C it came from.
  • Verify against an independent reference over several inputs; off-by-one errors in loop bounds hide on small inputs.
  • Counting executed instructions shows how work scales: the sieve costs roughly N log log N.
  • A compiler's loop for the same C code has the same shape: indexed store, add the step, compare, conditional jump.

Next: functions that share one calling convention in Project: A String Toolkit.