范围内的恒定时间随机数

Question

我有一个以恒定时间运行的随机数生成器。

这个函数的原型(prototype)如下:

uint8_t rand();

我想要做的是创建一个随机返回 uint8_t 的函数，使输出介于 0 和 max 之间，其中 max 是要返回的最大数字。这种功能的原型(prototype)是:

uint8_t randi(uint8_t max);

在线有算法可以做到这一点，并且可以防止堆栈溢出。例如，https://stackoverflow.com/a/6852396/1444313 .但我的问题是我想在固定时间内实现这一目标。我找不到在恒定时间内执行此操作的任何方法。

此外，我在没有硬件划分的 ARM Cortex-m0 上运行，因此无法使用 % 运算符。

有没有人对我如何在恒定时间内实现这一目标有任何建议或指示？

谢谢

Answer 1

从最严格的意义上说，这些要求是不可能满足的。只要您的 RNG 以二进制形式产生均匀分布，就没有办法将其映射到非二次幂范围而不丢弃某些结果或产生不完美的分布。

您可以使缺陷变得非常小，或者您可以使丢弃的情况变得非常罕见。由于罕见的丢弃代表意外发生时的时间异常(并且通过使其更罕见，您只会让它更令人惊讶)考虑 this solution ，这是常数时间，可以通过这种方式适应您的特定 rand() 函数:

int n = max + 1;
int r = n / 2;
for (int i = 0; i < 6; ++i) {
    r = (rand() * n + r) >> 8;
}
return r;

这将提取 48 个随机位作为 0 和 1 之间的小数，并将其乘以 n，仅保留整数部分，该值将不大于 max。对某些值的偏好小于其他值的万亿分之一。如果您对此不满意，则可以将 6 更改为更大的值。

这种偏差意味着，如果您每秒抽取 1000 个随机数，则需要 30 多年的时间才能看到一个结果比应有的次数多出现一次，而统计噪声仍然会淹没它。

您可以通过将 rand() 替换为在单次调用中产生更多随机位的东西，并且只迭代一次或两次，从而使这更快。