c - 从预填充的随机缓冲区中提取基数 K 随机 “bits”

Question

假设我需要 [0, K) 范围内的 N 个加密安全伪随机整数。最明显的实现方式是 N 次调用 arc4random_uniform(3)。 ，而这正是我正在做的。

但是，探查器告诉我对 arc4random_uniform(3) 的多次调用占用了整个执行时间的 2/3，我真的需要让我的代码更快。这就是为什么我计划提前生成一些随机字节(可能使用 arc4random_buf(3))，然后一点一点地从中提取。

对于 K = 2，我可以简单地屏蔽掉所需的位，但是当 K 不是 2 的幂时，事情就变得棘手了。当然，我可以使用一堆 %= 和 /=，但这样我会有模偏差。另一个问题是当 N 变得太大时，我无法再将整个缓冲区解释为一个整数并对其执行算术运算。

如果相关，K 将小于 20，而 N 可以非常大，例如数百万。

Answer 1

你可以使用取模运算符和除法，你只需要做一些额外的预处理。正常生成值数组。取P为小于或等于2^32的K的最大幂(其中^表示求幂)，并遍历您的数组，确保所有随机值都严格小于 P。任何不是的，替换为一个小于 P 的新随机数。这将消除偏见。

现在要处理大的 N，您需要两个循环。第一个循环遍历数组中的元素，第二个循环从每个元素中提取多个随机数。如果 P = k ^ e，那么您可以从数组中的每个元素的 [0, k) 中提取 e 随机数。每次从元素中提取一个随机数时，对该元素进行 k 的底除法。

当然，这不一定是实际的循环。您可以存储两个变量(数组索引、子元素索引)并在调用函数时从 array_index 元素中提取。如果 sub_element_index == e，则将其重置为零并增加 array_index。从此数组元素中提取一个随机数并将其返回。