How the Roll Function Works (In APL\360 and Its Descendants)

How the roll function works

The roll function in APL and its descendants is, at heart, a clever multiplicative generator: start with 16807, multiply repeatedly, and reduce modulo 2,147,483,647 (that’s 7FFFFFFF in hex). Do that and you get a permutation of every integer from 1 up to 2,147,483,646 — no repeats, cycles back to 1 when the multiplicative order completes. Neat, compact, and fast. Want reproducible pseudo‑randomness that also passes a surprising number of statistical tests? This trick delivers, because 16807 is a primitive root modulo that prime and so generates the full multiplicative group.

A brief history

Why those two magic numbers? Because 2,147,483,647 = 2^31 − 1 is a Mersenne prime (Euler proved it prime in 1772), which fits perfectly into 32‑bit signed arithmetic, and 16807 turns out to be a generator for the multiplicative group modulo that prime. It has been reported that D. H. Lehmer suggested this multiplicative technique in 1948; later accounts by Holz & Clark and Hutchinson adapted it for 36‑bit machines and influenced APL implementations. The JSoftware paper and a Hacker News discussion walk through this lineage — ancient prime lore meets practical machine choices. Euler being blind at 65 when he handled these primes? A nice historical aside. The math reads like a small miracle: hardware constraints and number theory aligning just so.

The symbol and the original problem

Early APL’s question mark (?) wasn’t a single thing. Niladic ? returned an inscrutable 0 or 1; monadic ?(B) produced a Boolean vector of length B; dyadic ?A(B) gave a vector with A ones and B−A zeros. In other words, the random primitives began life firmly rooted in Boolean, machine‑description territory. By the 7090 time‑sharing version (late 1965) the definitions had morphed toward the modern forms used today. One concrete programming challenge from that era still reads like a classic exercise: “Write a function that prepares a table of all patterns of A ones and B−A zeros.” Simple to state, subtle to implement efficiently — and a reminder that what looks like an innocent symbol can hide a rich computational story.

Sources: jsoftware.com, Hacker News