将随机范围从 1–5 扩展到 1–7 [英] Expand a random range from 1–5 to 1–7
问题描述
给定一个产生 1 到 5 范围内随机整数的函数，编写一个产生 1 到 7 范围内随机整数的函数.
Given a function which produces a random integer in the range 1 to 5, write a function which produces a random integer in the range 1 to 7.
- 什么是简单的解决方案?
- 减少内存使用量或在较慢的 CPU 上运行的有效解决方案是什么?
推荐答案
int rand7() {
int value = rand5()
+ rand5() * 2
+ rand5() * 3
+ rand5() * 4
+ rand5() * 5
+ rand5() * 6;
return value%7;
}
与选择的解决方案不同，该算法将在恒定时间内运行.然而，它确实比所选解决方案的平均运行时间多 2 次调用 rand5.
Unlike the chosen solution, the algorithm will run in constant time. It does however make 2 more calls to rand5 than the average run time of the chosen solution.
请注意，此生成器并不完美(数字 0 的几率比任何其他数字高 0.0064%)，但对于大多数实际用途，恒定时间的保证可能会超过这种不准确性.
Note that this generator is not perfect (the number 0 has 0.0064% more chance than any other number), but for most practical purposes the guarantee of constant time probably outweighs this inaccuracy.
说明
这个解决方案源于数字 15,624 可以被 7 整除的事实，因此如果我们可以随机均匀地生成从 0 到 15,624 的数字，然后取模 7，我们可以得到一个接近均匀的 rand7 生成器.将 rand5 滚动 6 次，并用它们组成基数为 5 的数字，可以均匀地生成 0 到 15,624 之间的数字，如下所示:
This solution is derived from the fact that the number 15,624 is divisible by 7 and thus if we can randomly and uniformly generate numbers from 0 to 15,624 and then take mod 7 we can get a near-uniform rand7 generator. Numbers from 0 to 15,624 can be uniformly generated by rolling rand5 6 times and using them to form the digits of a base 5 number as follows:
rand5 * 5^5 + rand5 * 5^4 + rand5 * 5^3 + rand5 * 5^2 + rand5 * 5 + rand5
mod 7 的属性允许我们稍微简化等式:
Properties of mod 7 however allow us to simplify the equation a bit:
5^5 = 3 mod 7
5^4 = 2 mod 7
5^3 = 6 mod 7
5^2 = 4 mod 7
5^1 = 5 mod 7
所以
rand5 * 5^5 + rand5 * 5^4 + rand5 * 5^3 + rand5 * 5^2 + rand5 * 5 + rand5
变成
rand5 * 3 + rand5 * 2 + rand5 * 6 + rand5 * 4 + rand5 * 5 + rand5
理论
数字 15,624 不是随机选择的，而是可以使用费马小定理发现的，该定理指出如果 p 是素数，则
The number 15,624 was not chosen randomly, but can be discovered using fermat's little theorem, which states that if p is a prime number then
a^(p-1) = 1 mod p
所以这给了我们，
(5^6)-1 = 0 mod 7
(5^6)-1 等于
4 * 5^5 + 4 * 5^4 + 4 * 5^3 + 4 * 5^2 + 4 * 5 + 4
这是一个基数为 5 的数字，因此我们可以看到该方法可用于从任何随机数生成器到任何其他随机数生成器.尽管在使用指数 p-1 时总是会引入对 0 的小偏差.
This is a number in base 5 form and thus we can see that this method can be used to go from any random number generator to any other random number generator. Though a small bias towards 0 is always introduced when using the exponent p-1.
为了概括这种方法并更准确，我们可以使用这样的函数:
To generalize this approach and to be more accurate we can have a function like this:
def getRandomconverted(frm, to):
s = 0
for i in range(to):
s += getRandomUniform(frm)*frm**i
mx = 0
for i in range(to):
mx = (to-1)*frm**i
mx = int(mx/to)*to # maximum value till which we can take mod
if s < mx:
return s%to
else:
return getRandomconverted(frm, to)
这篇关于将随机范围从 1–5 扩展到 1–7的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
