entropy-pool
entropy-pool is a small Rust crate for drawing bounded random values,
partial permutations, and combinations while keeping unused randomness in an
internal entropy pool.
The main idea is simple: every random byte that is read expands an internal uniform state space. When a draw cannot use that space exactly, the leftover states are not thrown away. They are mapped back into the pool and reused by later draws.
Example
use EntropyPool;
let mut pool = new;
// Uniform value in 0..6.
let die_roll = pool.gen_range + 1;
// Three distinct values from 0..10, in random order.
let sample = pool.permutation;
// Five distinct values from 0..20, returned as a sorted BTreeSet.
let chosen = pool.combination;
API
EntropyPool::new()
Creates a new pool backed by rand::rng(). The pool starts by reading one
random byte.
EntropyPool::with_rng(rng)
Creates a new pool backed by a caller-provided RNG implementing
rand::Rng. This is useful for deterministic tests, seeded generators, or
specialized randomness sources.
gen_range(n: u32) -> u32
Returns a uniform integer in 0..n.
Panics if n == 0.
Use try_gen_range(n) to get Result<u32, EntropyPoolError> instead.
permutation(m: u32, n: u32) -> Vec<u32>
Returns m distinct values from 0..n in random order.
This is a partial Fisher-Yates shuffle driven by gen_range.
Panics if m > n.
Use try_permutation(m, n) to get Result<Vec<u32>, EntropyPoolError>
instead.
combination(m: u32, n: u32) -> BTreeSet<u32>
Returns m distinct values from 0..n as a sorted set.
The implementation uses Floyd's sampling algorithm with online rank recycling.
It performs min(m, n - m) bounded draws and keeps only the sampled set, using
O(min(m, n - m)) auxiliary space. For large selections it samples the
smaller excluded set and returns the complement.
Panics if m > n.
Use try_combination(m, n) to get Result<BTreeSet<u32>, EntropyPoolError>
instead.
Statistics
random_bytes_read() returns how many bytes have been read from the backing
RNG. retained_states() returns the current pool radix m, and
retained_entropy_bits() returns log2(m).
How The Entropy Pool Works
The pool stores a pair (b, m) with this invariant:
b is uniformly distributed in 0..m
To draw a value in 0..n, the algorithm writes:
m = q * n + r
If b falls in the first q * n states, the draw is exact:
output = b % n
new_pool = (b / n, q)
If b falls in the remaining r states, those rejected states are converted
back into a uniform state in 0..r and the draw continues. Before each trial,
the pool is expanded until the rejection probability is below 2^-32. While
the internal u64 state can hold the expanded radix, this appends one byte:
new_b = old_b * 256 + random_byte
new_m = old_m * 256
If another byte would overflow the u64 radix and the rejection bound is still
not met, the implementation discards the old retained state and refills the
pool with a full-width uniform state on 0..u64::MAX.
This is a byte-oriented entropy recycling method: modulo bias is avoided, but the rejection branch keeps the unused entropy instead of discarding it.
Mathematical Proof
Write [k] for the set {0, 1, ..., k - 1}. The panicking methods require the
documented preconditions; the try_* methods report invalid arguments with
EntropyPoolError.
Entropy-pool invariant
At every public draw boundary, the pool state (B, M) satisfies:
B is uniform on [M].
Future bytes produced by rand::rng() are independent of B.
When the implementation appends one random byte U, where U is uniform on
[256], it replaces:
B' = 256B + U
M' = 256M
The map
(B, U) -> 256B + U
is a bijection from [M] x [256] to [256M]. Therefore B' is uniform on
[M'], so appending bytes preserves the invariant.
If appending another byte would overflow the internal u64 radix, the
implementation may instead draw a u64 value X until X != u64::MAX, then
store:
B' = X
M' = u64::MAX
Conditioned on X != u64::MAX, X is uniform on [u64::MAX]. This full-width
refill discards older retained entropy, but it preserves the invariant and
keeps the u32 range sampler on fast u64 arithmetic.
Correctness of gen_range
Let the current pool state be (B, M), with B uniform on [M]. For a
requested range size n > 0, write:
M = qn + r, 0 <= r < n.
The algorithm accepts when:
B < qn.
On the accepted set [qn], define:
Y = B mod n
C = floor(B / n)
The map
B -> (Y, C)
is a bijection from [qn] to [n] x [q], with inverse:
(Y, C) -> Cn + Y.
Conditioned on acceptance, B is uniform on [qn]; by the bijection,
(Y, C) is uniform on [n] x [q]. Hence:
Yis uniform on[n];Cis uniform on[q];YandCare independent.
The implementation returns Y and stores (C, q) as the new pool state, so the
returned value is unbiased and the pool invariant is preserved.
If the algorithm rejects, then B lies in:
{qn, qn + 1, ..., M - 1},
which has size r. The implementation stores:
D = M - B - 1
and M = r. The map B -> D is a bijection from the rejected set to [r].
Conditioned on rejection, D is therefore uniform on [r], so the pool
invariant is again preserved and the loop can retry. No modulo-biased value is
ever returned.
The byte-extension loop is separate from the acceptance bijection above: it ensures there is an accepted region and bounds the rejection probability. Once the loop condition is false:
2^32 * (M mod n) < M,
so the next trial rejects with probability:
r / M < 2^-32.
Thus, within the finite-size limits of this implementation, repeated rejection has probability zero in the ideal random-byte model.
Correctness of permutation
permutation(m, n) is a partial Fisher-Yates shuffle. At step i, the suffix
before i is already fixed, and the array positions i..n contain exactly the
remaining n - i items. The call:
gen_range(n - i) + i
chooses one of those remaining positions uniformly, and the swap moves that
chosen item into position i.
By the gen_range proof, each choice is uniform and leaves a pool state
independent of the chosen index. Therefore the probability of any ordered
m-tuple of distinct values is:
1 / n * 1 / (n - 1) * ... * 1 / (n - m + 1)
= 1 / P(n, m),
where:
P(n, m) = n! / (n - m)!.
So permutation(m, n) is uniform over all ordered length-m samples without
replacement.
Correctness of recycle
Suppose the current pool state is (B, M), with B uniform on [M]. Suppose
D is independent of B and uniform on [d]. recycle(D, d) stores:
B' = Bd + D
M' = Md
The map:
(B, D) -> Bd + D
is a bijection from [M] x [d] to [Md]. Therefore B' is uniform on [M'].
So, when Md fits in the internal u64 state, recycling an independent
base-d digit preserves the pool invariant while adding exactly log2(d) bits
of state space.
If Md would overflow u64, the implementation discards the older retained
state and stores only:
B' = D
M' = d
Since D is uniform on [d], the pool invariant is still preserved. This
fallback can lose retained entropy, but it cannot bias future outputs.
Correctness of combination
Let k be the number of items actually sampled:
k = min(m, n - m).
The implementation applies Floyd's transition. Starting with the empty set
S, for:
j = n-k, n-k+1, ..., n-1
it draws T uniformly from [j+1] and updates:
if T is in S: S' = S union {j}
otherwise: S' = S union {T}
In both branches T belongs to S'. If the new set has size r, the
implementation recycles:
D = rank of T inside S', D in [r].
The important detail is that a collision inserts j, but the recycled digit is
the rank of the original draw T, not the rank of j.
We prove the following invariant after round r: S' is uniform over the
r-subsets of [j+1], and the entropy-pool state is uniform and independent
of S'.
Before round r, assume S is a uniform (r-1)-subset of [j]. The pool is
independent of S, and gen_range(j+1) returns a uniform T while leaving a
pool state independent of (S, T). Consider the transition:
(S, T) -> (S', D).
It has the following explicit inverse. Given an r-subset S' of [j+1] and
D in [r], let T be the D-th smallest element of S', then set:
if j is in S': S = S' without j
otherwise: S = S' without T
If j is absent, T was not in S and the non-collision branch inserted it.
If j is present, removing j reconstructs the old set: either T = j was
inserted directly, or T was already present and caused the collision. Thus
the inverse is valid and unique in every case, so the transition is a
bijection. Equivalently:
C(j, r-1) * (j+1) = C(j+1, r) * r.
Because (S, T) is uniform over the left-hand side, (S', D) is uniform over
the Cartesian product on the right. Consequently S' is uniform, D is
uniform on [r], and they are independent. The residual pool was already
independent of (S', D), so:
recycle(D, r)
preserves a uniform pool independent of S'. This completes the induction.
There is no hidden candidate ordering in Floyd's algorithm: the complete state
that affects the next round is the set S' covered by the invariant. This is
essential. A Fisher-Yates candidate array can be correlated with a recycled
rank even when the final rank tuple is independent of the final set, so the
global ordered-sample bijection alone is not sufficient for online recycling.
The recycle multiplication in this loop cannot overflow. If the working radix
immediately before the successful gen_range(j+1) split is M_work, the
residual radix is floor(M_work / (j+1)). Multiplying it by r <= j+1 cannot
exceed M_work <= u64::MAX.
Across all k rounds:
product of draw radices = (n-k+1) * ... * n = P(n, k)
product of recycled radices = 1 * 2 * ... * k = k!
Since P(n, k) = C(n, k) * k!, the returned set accounts for exactly
log2 C(n, k) bits and the recycled ranks account for exactly log2(k!) bits.
When the requested m is larger than n / 2, the implementation samples the
excluded set of size n - m and returns its complement. The complement map is a
bijection between (n - m)-subsets and m-subsets, so uniformity is preserved.
The pool is independent of the excluded set and therefore also independent of
its complement.
Entropy lower bound
Any exact sampler for m elements from n must produce one of:
C(n, m)
outputs uniformly. Thus the output itself contains:
log2 C(n, m)
bits of entropy. The tests compare this information-theoretic lower bound with
the number of random bytes actually read. For a pool state (B, M), the
remaining reusable entropy is:
log2 M.
So the useful entropy after a combination draw is measured as:
log2 C(n, m) + log2 M.
divided by the consumed random bits. Values close to 1 mean the consumed
randomness has been converted almost entirely into either the returned
combination or reusable pool state.
Correctness And Entropy Tests
Run the test suite with:
The tests include:
- deterministic custom-RNG sampling;
- checked error handling for invalid arguments;
u64recycle-overflow fallback;- exhaustive uniformity for
permutation(2, 3); - exhaustive uniformity for
combination(2, 4); - verification that
combination(2, 4)recycles the discarded order bit; - the
combination(3, 6)regression that detects feedback from a hidden candidate ordering; - exhaustive output/pool independence for every combination with
n <= 8; - edge cases for empty, full, direct, and complement combinations;
- a large entropy-utilization check against the binomial lower bound.
Example output from the large test:
combination(20000, 30000): lower_bound=27541.20 bits, retained=50.80 bits,
consumed=27592 bits (3449 bytes), output_efficiency=99.8159%,
retained_efficiency=100.0000%
The exact byte count can vary with random rejection paths, but the test asserts that output entropy stays above 99.5% of the information-theoretic lower bound. When retained pool entropy is included, the accounting should be very close to 100%.
Notes
- The default pool uses
ThreadRng, butEntropyPool::with_rngaccepts anyrand::Rng. - Public sampling APIs use
u32ranges and the internal pool state isu64. This keeps the hot path on native-width arithmetic. If expansion or recycling cannot keep older retained entropy insideu64, the implementation keeps correctness by discarding that older retained entropy. permutationbuilds aVec<u32>for the whole population.combinationkeeps an order-statistics set of sizemin(m, n - m)and therefore usesO(min(m, n - m))auxiliary space, excluding the returned set.- The non-
try_*methods are convenience wrappers that panic on invalid arguments. Use the checked methods for library-facing error handling.
License
AGPL-3.0-only