如何从随机位流中生成 [0,n] 范围内的随机整数而不浪费位? [英] How to generate a random integer in the range [0,n] from a stream of random bits without wasting bits?

问题描述

我有一个(均匀)随机位流，我想从中均匀地生成 [0,n] 范围内的随机整数，而不会浪费位.(我正在考虑浪费超过 floor(log_2(n))+1 的比特，假设总是可以使用不超过这个值.)例如，如果 n = 5，那么我的算法寻找应该使用不超过三位.这怎么办?

I have a stream of (uniform) random bits from which I'd like to generate random integers uniformly in the range [0,n] without wasting bits. (I'm considering bits wasted which are in excess of floor(log_2(n))+1, on the assumption that it's always possible to use no more than that.) E.g., if n = 5, then the algorithm I'm looking for should use no more than three bits. How can this be done?

推荐答案

这相当于在两组不同的(有限)基数之间找到一个双向函数.这是不可能的.

This is equivalent to find a two-way function between two set of different (finite) cardinality. It is impossible.

这篇关于如何从随机位流中生成 [0,n] 范围内的随机整数而不浪费位?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！