有没有办法给一个范围内的均匀分布的随机数转换成另一种范围的均匀分布的随机数省吃俭用？
让我解释一下我所说的“节俭”是什么意思。
在给定范围内生成随机数的典型方法（例如 r ? [0..10) ）是采用一些固定的随机位，比如说 31，这会产生小于 2147483648 的非负随机数。然后确保该值小于 2147483640（因为 2147483648 不能被 10 整除，因此可能导致分布不均）。如果该值大于或等于 2147483640，则将其丢弃并重试（获取接下来的 31 个随机位等）。如果 value 小于 2147483640，则只返回除以 10 的余数。这种方法每个十进制数字至少消耗 31 位。由于理论极限是log 2 (10) = 3.321928...，相当浪费。
我们可以改进这一点，如果我们使用 4 位而不是 31。在这种情况下，我们将消耗 4 × 1.6 = 6.4 位每个十进制数字。这样比较节俭，但离理想还差得很远。
public int nextDit() {
int result;
do {
result = next4Bits();
} while (result >= 10);
return result;
}
我们可以尝试一次生成 3 个十进制数字。由于 1024 与 1000 非常接近，因此原始源随机数被拒绝的概率小于前一种情况。一旦我们生成了 3 个十进制数字，我们就返回 1 个数字并保留其余的 2 个数字。
像下面这样
private int _decDigits = 0;
private int _decCount = 0;
public int nextDit() {
if (_decCount > 0) {
// take numbers from the reserve
int result = _decDigits % 10;
_decDigits /= 10;
_decCount -= 1;
return result;
} else {
int result;
do {
result = next10Bits();
} while (result >= 1000);
// reserve 2 decimal digits
_decCount = 2;
_decDigits = result % 100;
result /= 100;
return result;
}
}
这种方法更加节俭：每个十进制数字消耗 10 × 1.024 / 3 = 3.41(3) 位。
如果我们尝试重用之前一直丢弃的数字，我们甚至可以走得更远。随机数 r ? [0, 1024) 属于以下 3 个范围之一：[0, 1000), [1000, 1020), [1020, 1024)]
如果落入[0, 1000)，我们就和之前一样，保留2位十进制数（十进制数保留），返回1位十进制数。
如果它落入 [1000, 1020)，我们减去 1000 转换为范围 [0, 20)。然后我们通过将其除以 10 得到 1 位，并通过将除以 10 的余数得到 1 个十进制数字。我们将该位放入二进制数字保留并返回十进制数字。
如果它落入 [1020, 1024)，我们减去 1020 转换为范围 [0, 4)。在这里，我们只得到 2 位，我们将其放入二进制数字储备中。
// decimal digit reserve
private int _decDigits = 0;
private int _decCount = 0;
// binary digit reserve
private int _binDigits = 0;
private int _binCount = 0;
private int nextBits(int bits, int n) {
for (int i = 0; i < n; i += 1) {
bits = (bits << 1) + _bitRandomDevice.nextBit();
}
return bits;
}
private int next10Bits() {
// take bits from the binary reserve first, then from _bitRandomDevice
int result;
if (_binCount >= 10) {
result = _binDigits >> (_binCount - 10);
_binDigits = _binDigits & (1 << (_binCount - 10) - 1);
_binCount -= 10;
} else {
result = nextBits(_binDigits, 10 - _binCount);
_binCount = 0;
_binDigits = 0;
}
return result;
}
public int nextDit() {
if (_decCount > 0) {
// take numbers from the decimal reserve
int result = _decDigits % 10;
_decDigits /= 10;
_decCount -= 1;
return result;
} else {
int result;
while (true) {
result = next10Bits();
if (result < 1000) {
assert result >= 0 && result < 1000;
// reserve 2 decimal digits
_decCount = 2;
_decDigits = result % 100;
result /= 100;
// return 1 decimal digit
return result;
} else if (result < 1020) {
result -= 1000;
assert result >= 0 && result < 20;
// reserve 1 binary digit
_binCount += 1;
_binDigits = (_binDigits << 1) + (result / 10);
// return 1 decimal digit
return result % 10;
} else {
result -= 1020;
assert result >= 0 && result < 4;
// reserve 2 binary digits
_binCount += 2;
_binDigits = (_binDigits << 2) + result;
}
}
}
}
这种方法每十进制数字消耗大约 3.38... 位。这是我能找到的最节俭的方法，但它仍然会浪费/丢失一些来自随机源的信息。
因此，我的问题是：是否有任何通用方法/算法可以将一个任意范围 [0, s)（后称为源数）的均匀分布随机数转换为另一个任意范围 [0, t) 的均匀分布随机数（稍后称为目标编号），每个目标编号仅消耗 log s (t) + C 个源编号？其中 C 是某个常数。如果没有这种方法，为什么？是什么阻止了达到理想极限？
节俭的目的是减少对 RNG 的调用次数。当我们使用通常吞吐量有限的 True RNG 时，这尤其值得做。
至于“节俭优化”，它们基于以下假设：
您的目标最终是在仅给定p面骰子的情况下掷出k面骰子，而不会浪费随机性。
从这个意义上说，根据B. Kloeckner在“用骰子模拟骰子”中的引理 3 ，这种浪费是不可避免的，除非“每个除k 的质数也除掉p ”。因此，例如，如果p是 2 的幂（并且任何随机位块都与掷骰子的面数为 2 的幂相同）并且k 的质因数不是 2，那么您能做的最好的事情是随意接近不浪费随机性。
此外，除了批量位以减少“位浪费”（另请参见数学论坛）之外，还有随机性提取技术，在Devroye 和 Gravel 2015-2020以及我的随机性提取笔记中进行了讨论。
另请参阅问题：如何从随机位流中生成 [0,n] 范围内的随机整数而不浪费位？，尤其是我在那里的回答。