Implement fast sampling for weighted k-sided die

Implement a sampler for a categorical distribution with k outcomes whose probabilities are stored in probs. The input probabilities are non-negative and are normalized by the implementation so they sum to exactly one. The sampler may use only a Uniform(0,1) source, or equivalently fair coin flips; no library routine that directly samples from a categorical distribution is allowed. Testing is deterministic: instead of the sampler calling a random generator, it receives a list…