algorithm - 从随机字节生成给定范围内的随机数

Question

有类似的问题，但其中大部分都针对特定语言。我正在寻找一个通用的解决方案。给定一些生成 k 个随机字节和一个数字 n 的方法，我需要生成一个 1...n 范围内的随机数(包括).

到目前为止我想出了什么:

1. 要确定表示n所需的字节数，计算

f(n):=ceiling(ln(n)/8ln(2))=ceiling(0.180337*ln(n))

1. 为 0 索引字节 b[i] 获取 1...2^8f(n) 范围内的随机数:

r:=0
对于 i=0 到 k-1:
r = r + b[i] * 2^(8*i)
结束

1. 无偏差地缩放到 1...n:

   R(n,r) := ceiling(n * (r/256^f(n)))

但我不确定这是否会造成偏差或一些微妙的一次性错误。你能检查一下这是否合理和/或提出改进建议吗？这是执行此操作的正确方法吗？

在答案中，请假设没有可用的模块化位旋转操作，但您可以假设任意精度算术。 (我正在用 Scheme 编程。)

编辑:我的方法肯定有问题，因为在我的测试中掷骰子产生了一些 0 的情况!但是错误在哪里呢？

Answer 1

如果您想从 0 到 1 的随机 float 生成 1 到 n 的数字(含 0 和 1)，这类似于您要做的事情。如果 r 是随机 float :

result = (r * n) + 1

如果您有任意精度的算法，您可以通过将 k 字节整数除以 k 字节中可表示的最大值 + 1 来计算 r。

因此，如果您有 4 个字节 87 6F BD 4A，并且 n = 200:

((0x876FBd4A/0x100000000) * 200) + 1