Picking with random_u64() % n is biased, a blog post argues

Austin Seipp opens with a pattern found in codebases everywhere: given a set of objects, pick one at random with equal chances. The direct solution is to draw a big random number and clamp it to the number of choices with modulo, as in choices[random_u64() % 10]. He admits he chose this option several times when he was younger, especially in C, whose standard library offers nothing beyond rand(), and in Haskell. The hidden problem, he says, is that the modulo does not preserve the uniform distribution of the underlying random_u64() function, so the odds are not what intuition suggests.

He shows it with a toy case. Take an integer from [0, 9], each with a 10% chance, and use modulo to pick one of 3 objects. The inputs {0, 3, 6, 9} map to object 1, {1, 4, 7} to object 2 and {2, 5, 8} to object 3. Of the 10 inputs, 4 yield choice 1 while choices 2 and 3 get 3 each. Choice 1 is therefore picked 40% of the time rather than the intended 33%, and choices 2 and 3 only 30% of the time. He calls it one of the classic blunders, especially when random_u64() is all you have. The correct tool is a random_between(l, h) function that gives each inclusive number between l and h a 1/((h-l)+1) chance, which is a bit more complex to write.

Seipp sees two issues. First, he thinks it is poor API design to offer only a uniform random function, since one of its most useful variants is easy to implement incorrectly. Second, it is a case of working in the wrong mental domain. His proposed default is a random_choice() function that takes discrete options with their probabilities, so you spell out the distribution yourself. It can express uniform picks and weighted ones, and a lopsided pick such as (First, 0.4), (Second, 0.3), (Third, 0.3) stands out. He says you should still keep random_u64() and random_between(), but random_choice() is the better default because it helps you fall into the pit of success.

Probabilities that must sum exactly to 1.0 run into floating point instability and force you to compute scales by hand, so he moves to relative integer weights. He says most standard libraries, Python among them, do exactly this. The weights are summed and each choice's chance is its weight divided by the sum, so the 0.4/0.3/0.3 case becomes (4, 3, 3), where 4 + 3 + 3 = 10 and 3/10 = 0.3. Counting 10 blue things and 5 red things in a box becomes [(Blue, 10), (Red, 5)]. Implementation is easier with random_between(l, h): with weights 15 + 12 + 3 = 30, draw random_between(0, 29), and a value in [0, 14] picks the first option, 15 to 26 the second and [27, 29] the third. In his opinion that helper belongs in the library too.

On the mental-domain point, he says the things we talk about here are random variables, not numbers. Random variables have an algebra, but non-linear operators do not respect their expected values: a function of the expected value, E[f(X)], is not always the same as f(E[X]). The modulo trap comes from trying to retain a property of one drawn value x rather than of the random_u64() function itself.

Then he turns to his own case. His team are customers of Antithesis, a platform where they find bugs by exercising important code paths at random; he describes it as a big deterministic fuzzer for a whole operating system. As with any fuzzer, code coverage is the guide: a path the fuzzer never finds is code that was not tested. Coverage grows by expressing negative paths (a bad case such as an assert!() tripping, for example a cache keyed by a hash of the data whose key no longer matches a recomputed hash) and positive paths. A positive path might be making sure an upload function with different small and large paths tests both. His example gives blob sizes Small (1KiB), Medium (1MiB), Large (2MiB) and XLarge (8MiB) weights of 88, 4, 4 and 4, so under test about 7/8 of uploads are small and about 1/8 are large, in three sizes. Being able to tune those numbers helps explore the state space, and the same approach extends to something like a Poisson distribution. He also suggests extending the choice list at runtime, with choice.push() when a good or bad thing happens, to steer the search; that would require rebalancing the weights in the example.

The post was prompted by something that happened last week. On reviewing the Antithesis-related code, the team removed all the uses of random_u64() that had crept in, replacing them with weighted random_choice(), because in practice they only ever wanted discrete weighted choices. They have put a moratorium on new calls to random_u64() until further notice. Seipp says he wrote the lesson up so it would not stay buried in a commit message, since he keeps forgetting it. His closing advice: next time you see code like the original sample, ask whether you can represent the desired distribution directly.

Key facts

Picking an item with random_u64() % n does not preserve the uniform distribution; in the post's toy case, mapping 0 to 9 onto 3 objects gives choice 1 a 40% chance instead of 33%, and choices 2 and 3 30% each.
Seipp recommends a random_choice() API that takes discrete options with explicit probabilities, and keeping random_u64() and random_between() alongside it.
He prefers relative integer weights such as (4, 3, 3) over probabilities summing to 1.0, citing floating point instability, and says most standard libraries, Python among them, work this way.
His example gives blob sizes weights 88, 4, 4 and 4, so about 7/8 of test uploads are small and about 1/8 large, to exercise both code paths under Antithesis.
His team, customers of Antithesis, removed all their random_u64() uses in favour of weighted random_choice() and put a moratorium on new calls.

Why it matters

The modulo shortcut is easy to write and looks right, which is why it keeps appearing. The post's toy case makes the skew concrete: 10 inputs mapped onto 3 objects give one object 4 inputs and the others 3 each, so 40% against 30% and 30%. The deeper argument is about API design. If a library offers only a uniform number, the caller has to build distributions by hand and can get them subtly wrong. Asking for the distribution up front makes a lopsided pick visible in the code.

Who it affects

Anyone who writes code that picks randomly from a list, and anyone who designs a random-number API or helper library. It is also relevant to teams that use random exploration to find bugs. The author's own team uses Antithesis, which he describes as a deterministic fuzzer for a whole operating system, where the shape of the choice distribution decides which code paths get tested.

How to use it

Replace choices[random_u64() % n] with a weighted choice function that takes options and relative integer weights, for example (4, 3, 3) or [(Blue, 10), (Red, 5)]. If you must build one yourself, the post suggests drawing random_between(0, total - 1) and mapping each weight to a sub-interval, as in the 15 + 12 + 3 = 30 example. Keep random_between(l, h) available, since it gives each inclusive number a 1/((h-l)+1) chance. For test steering, tune the weights, as in the 88/4/4/4 blob-size example, or add choices at runtime and rebalance.

How solid is it

The central claim is simple counting, and the post tabulates it: modulo of a uniform value does not give equal odds when the range does not divide evenly. The recommendations, such as random_choice() as the better default, are the author's stated opinion ('I think'), not a measured result. The post gives no benchmarks, bug counts or coverage results from his team's change, and does not quantify the bias for a u64 modulo 10; the only worked numbers are the toy example.

Risks and caveats

Probabilities that must sum exactly to 1.0 suffer from floating point instability, which is why the author moves to relative integer weights. The post does not name a specific library implementation of random_choice or weighted_choice, and does not describe how random_between is implemented, so the reader still has to get that part right. The moratorium on random_u64() is one team's local policy, set until further notice, not a general rule. The runtime choice.push() idea would require rebalancing the probabilities, as the author notes.

“In other words, you should spell out the probability distribution yourself.”

— Austin Seipp