Ulam Prime Sieve

Algorithms & Numeric

A Sieve of Eratosthenes stored as a packed bit-array — set a bit with arr[i>>3] |= (1u << (i&7)), test with (arr[i>>3] >> (i&7)) & 1. The shift amount i&7 is a runtime value, so the compiler must emit a variable-count shift — the codegen corner. The primes render as an Ulam spiral, revealing the famous diagonal clustering. Compiler stress-test #85.

loading core…

Self-running — the spiral reveals outward; gold pixels are primes.

Click the screen to focus, then watch. Tab away and it pauses.

What it is

Every integer from 1 up to 1024 is placed on a square spiral around the center of the screen; the ones that are prime are lit in gold. Because primes favour the values of certain quadratic polynomials, they line up along diagonals — the Ulam spiral. The primality data comes from a Sieve of Eratosthenes packed into a 128-byte bit-array.

// A set of integers as a packed bit-array — the shift amount (i&7) is RUNTIME.
void set(uint16_t i)      { comp[i>>3] |= (1u << (i & 7)); }        // variable G_SHL
uint8_t is_prime(uint16_t i){ return !((comp[i>>3] >> (i & 7)) & 1); } // variable G_LSHR

// Sieve of Eratosthenes over [0, 1024):
set(0); set(1);
for (i = 2; i*i < N; i++)
  if (is_prime(i))
    for (j = i*i; j < N; j += i) set(j);

The interesting part for the compiler is the bit addressing: a data-dependent shift by i&7. A naive bool primes[1024] would avoid the shift but waste 8× the RAM; the bit-array is the idiomatic choice and forces the general variable-count shift path in the backend.

Compiler stress-test

Item	What it exercises
variable-count shifts	A packed bit-array addresses bit i as byte i>>3, bit (i&7). Because i&7 is a runtime value, the shift `1u << (i&7)` (and the test `>> (i&7)`) compiles to a variable-count shift — a shift loop or helper (__ashlhi3/__lshrhi3 on this target), not a single fixed shift instruction. That is the codegen corner this demo exercises.
distinct from #5 and #28	#5 Life shifts by fixed neighbour-mask amounts (1<<0, 1<<1, …) — constant shifts the compiler folds. #28 Hilbert uses fixed bit twiddles. This demo's shift amount is data-dependent, forcing the general variable-count path.
bit-array as a set	The whole sieve is a membership set: 1024 bits = 128 bytes. Marking composites and testing primality are set-insert and set-contains. This is the idiom real code uses when a bool[] would waste 8× the memory — important on a 128 KB console.
the Ulam spiral	Walking the integers 1, 2, 3, … along a square spiral and marking the primes reveals Stanislaw Ulam's famous diagonal streaks — primes cluster on certain diagonals (values of prime-rich quadratic polynomials). The demo reveals the spiral outward from the center.

Written in C with the llvm-mos 65816 toolchain and verified against bsnes-jg and MAME. Hit Verify fidelity to reproduce the build gate's WRAM assert (sieve CRC 0x1F2F — a fold of all 1024 primality bits) live in this tab. No far pointers — host == default == +mos-a16 == +mos-xy16, -verify clean.