我看到很多人问过这个问题，但从未见过一个真正具体的答案。所以我打算在这里发布一个，希望能帮助人们理解为什么在使用随机数生成器时，比如c++中的rand()，会有“模偏置”。
当前回答
RAND_MAX值为3(实际上它应该比这个值高得多，但偏差仍然存在)，从这些计算中可以看出存在偏差:
1% 2 = 1 2% 2 = 0 3% 2 = 1 Random_between(1,3) % 2 =更可能是1
在本例中，当您想要0到1之间的随机数时，不应该使用% 2。你可以通过% 3得到一个0到2之间的随机数，因为在这种情况下:RAND_MAX是3的倍数。
另一种方法
有更简单的方法，但要加上其他答案，这是我的解，得到一个0到n - 1之间的随机数，所以有n种不同的可能性，没有偏差。
编码可能性数量所需的比特数(不是字节数)就是您需要的随机数据的比特数 从随机位编码数字 如果这个数字是>= n，重新启动(不取模)。
真正随机的数据是不容易获得的，所以为什么使用比需要更多的比特。
下面是Smalltalk中的一个示例，使用伪随机数生成器的位缓存。我不是安全专家，所以请自担风险。
next: n
| bitSize r from to |
n < 0 ifTrue: [^0 - (self next: 0 - n)].
n = 0 ifTrue: [^nil].
n = 1 ifTrue: [^0].
cache isNil ifTrue: [cache := OrderedCollection new].
cache size < (self randmax highBit) ifTrue: [
Security.DSSRandom default next asByteArray do: [ :byte |
(1 to: 8) do: [ :i | cache add: (byte bitAt: i)]
]
].
r := 0.
bitSize := n highBit.
to := cache size.
from := to - bitSize + 1.
(from to: to) do: [ :i |
r := r bitAt: i - from + 1 put: (cache at: i)
].
cache removeFrom: from to: to.
r >= n ifTrue: [^self next: n].
^r
其他回答
正如公认的答案所示，“模偏置”的根源在于RAND_MAX的低值。他使用一个非常小的RAND_MAX(10)值来表明，如果RAND_MAX为10，那么您尝试使用%生成一个0到2之间的数字，将导致以下结果:
rand() % 3 // if RAND_MAX were only 10, gives
output of rand() | rand()%3
0 | 0
1 | 1
2 | 2
3 | 0
4 | 1
5 | 2
6 | 0
7 | 1
8 | 2
9 | 0
所以有4个0的输出(4/10的概率)，只有3个1和2的输出(各3/10的概率)。
所以这是有偏见的。数字越小，出来的几率越大。
但这只在RAND_MAX很小的时候才会很明显。或者更具体地说，当你modding的数字比RAND_MAX大的时候。
一个比循环更好的解决方案(循环效率非常低，甚至不应该被建议使用)是使用输出范围大得多的PRNG。梅森Twister算法的最大输出为4,294,967,295。这样做MersenneTwister::genrand_int32() % 10，将是均匀分布的，模偏效应将几乎消失。
对于模的使用，有两种常见的抱怨。
one is valid for all generators. It is easier to see in a limit case. If your generator has a RAND_MAX which is 2 (that isn't compliant with the C standard) and you want only 0 or 1 as value, using modulo will generate 0 twice as often (when the generator generates 0 and 2) as it will generate 1 (when the generator generates 1). Note that this is true as soon as you don't drop values, whatever the mapping you are using from the generator values to the wanted one, one will occurs twice as often as the other. some kind of generator have their less significant bits less random than the other, at least for some of their parameters, but sadly those parameter have other interesting characteristic (such has being able to have RAND_MAX one less than a power of 2). The problem is well known and for a long time library implementation probably avoid the problem (for instance the sample rand() implementation in the C standard use this kind of generator, but drop the 16 less significant bits), but some like to complain about that and you may have bad luck
使用类似于
int alea(int n){
assert (0 < n && n <= RAND_MAX);
int partSize =
n == RAND_MAX ? 1 : 1 + (RAND_MAX-n)/(n+1);
int maxUsefull = partSize * n + (partSize-1);
int draw;
do {
draw = rand();
} while (draw > maxUsefull);
return draw/partSize;
}
生成0到n之间的随机数将避免这两个问题(并且它避免RAND_MAX == INT_MAX溢出)
顺便说一句，c++ 11引入了标准方法来简化和rand()以外的其他生成器。
马克的解决方案(公认的解决方案)近乎完美。
int x; {做 X = rand(); } while (x >= (RAND_MAX - RAND_MAX % n)); X %= n; 编辑于2016年3月25日23:16 Mark Amery 39k21170211
然而，它有一个警告，在RAND_MAX (RM)小于N的倍数(其中N =可能有效结果的数量)的任何场景中，它会丢弃1个有效结果集。
也就是说，当'count of values discarded' (D)等于N时，那么它们实际上是一个有效的集合(V)，而不是一个无效的集合(I)。
造成这种情况的原因是Mark在某些时候忽略了N和Rand_Max之间的差异。
N是一个集合，它的有效成员仅由正整数组成，因为它包含了有效响应的计数。(例如:Set N ={1,2,3，…N})
Rand_max然而是一个集合，它(根据我们的目的定义)包括任意数量的非负整数。
在最通用的形式中，这里定义为Rand Max的是所有有效结果的集合，理论上可以包括负数或非数值。
因此，Rand_Max最好被定义为“可能的响应”的集合。
然而，N是针对有效响应集合中的值的计数进行操作的，因此即使在我们的特定情况下定义，Rand_Max也将是一个比它所包含的总数小1的值。
使用Mark的解决方案，当X => RM - RM % N时，值被丢弃
EG:
Ran Max Value (RM) = 255
Valid Outcome (N) = 4
When X => 252, Discarded values for X are: 252, 253, 254, 255
So, if Random Value Selected (X) = {252, 253, 254, 255}
Number of discarded Values (I) = RM % N + 1 == N
IE:
I = RM % N + 1
I = 255 % 4 + 1
I = 3 + 1
I = 4
X => ( RM - RM % N )
255 => (255 - 255 % 4)
255 => (255 - 3)
255 => (252)
Discard Returns $True
正如你在上面的例子中看到的，当X的值(我们从初始函数中得到的随机数)是252、253、254或255时，我们将丢弃它，即使这四个值组成了一组有效的返回值。
IE:当被丢弃的值的计数(I) = N(有效结果的数量)，那么一个有效的返回值集将被原始函数丢弃。
如果我们将N和RM之间的差值描述为D，即:
D = (RM - N)
然后，随着D的值变得越来越小，由于这种方法导致的不需要的重新滚动的百分比在每次自然相乘时增加。(当RAND_MAX不等于质数时，这是有效的关注)
EG:
RM=255 , N=2 Then: D = 253, Lost percentage = 0.78125%
RM=255 , N=4 Then: D = 251, Lost percentage = 1.5625%
RM=255 , N=8 Then: D = 247, Lost percentage = 3.125%
RM=255 , N=16 Then: D = 239, Lost percentage = 6.25%
RM=255 , N=32 Then: D = 223, Lost percentage = 12.5%
RM=255 , N=64 Then: D = 191, Lost percentage = 25%
RM=255 , N= 128 Then D = 127, Lost percentage = 50%
由于N越接近RM，所需的rerroll的百分比就越高，因此根据运行代码的系统的约束条件和所寻找的值，在许多不同的值上，这可能是值得关注的问题。
要否定这一点，我们可以做一个简单的修正，如下所示:
int x;
do {
x = rand();
} while (x > (RAND_MAX - ( ( ( RAND_MAX % n ) + 1 ) % n) );
x %= n;
这提供了一个更通用的公式版本，说明了使用模量定义最大值的附加特性。
使用小值RAND_MAX的例子，它是N的乘法。
Mark’original版:
RAND_MAX = 3, n = 2, Values in RAND_MAX = 0,1,2,3, Valid Sets = 0,1 and 2,3.
When X >= (RAND_MAX - ( RAND_MAX % n ) )
When X >= 2 the value will be discarded, even though the set is valid.
通用版本1:
RAND_MAX = 3, n = 2, Values in RAND_MAX = 0,1,2,3, Valid Sets = 0,1 and 2,3.
When X > (RAND_MAX - ( ( RAND_MAX % n ) + 1 ) % n )
When X > 3 the value would be discarded, but this is not a vlue in the set RAND_MAX so there will be no discard.
此外，在N应为RAND_MAX中值的数量的情况下;在这种情况下，你可以设置N = RAND_MAX +1，除非RAND_MAX = INT_MAX。
在循环方面，你可以使用N = 1, X的任何值都将被接受，然而，在你的最终乘数中放入一个IF语句。但是也许你的代码有一个合理的理由，当函数被n = 1调用时，返回1…
因此，当你希望n = RAND_MAX+1时，最好使用0，它通常会提供一个Div 0错误
通用版本2:
int x;
if n != 0 {
do {
x = rand();
} while (x > (RAND_MAX - ( ( ( RAND_MAX % n ) + 1 ) % n) );
x %= n;
} else {
x = rand();
}
这两个解决方案都解决了当RM+1是n的乘积时不必要地丢弃有效结果的问题。
第二个版本还涵盖了边缘情况，即需要n等于RAND_MAX中包含的全部可能值集。
在这两种方法中，修改后的方法是相同的，并且允许提供更通用的解决方案，以满足提供有效随机数和最小化丢弃值的需要。
再次重申:
扩展mark示例的基本通解:
// Assumes:
// RAND_MAX is a globally defined constant, returned from the environment.
// int n; // User input, or externally defined, number of valid choices.
int x;
do {
x = rand();
} while (x > (RAND_MAX - ( ( ( RAND_MAX % n ) + 1 ) % n) ) );
x %= n;
扩展通解允许RAND_MAX+1 = n的一个附加场景:
// Assumes:
// RAND_MAX is a globally defined constant, returned from the environment.
// int n; // User input, or externally defined, number of valid choices.
int x;
if n != 0 {
do {
x = rand();
} while (x > (RAND_MAX - ( ( ( RAND_MAX % n ) + 1 ) % n) ) );
x %= n;
} else {
x = rand();
}
在某些语言(特别是解释型语言)中，在while条件之外执行比较操作的计算可能会导致更快的结果，因为无论需要重试多少次，这都是一次性计算。YMMV !
// Assumes:
// RAND_MAX is a globally defined constant, returned from the environment.
// int n; // User input, or externally defined, number of valid choices.
int x; // Resulting random number
int y; // One-time calculation of the compare value for x
y = RAND_MAX - ( ( ( RAND_MAX % n ) + 1 ) % n)
if n != 0 {
do {
x = rand();
} while (x > y);
x %= n;
} else {
x = rand();
}
不断随机选取是去除偏差的好方法。
更新
如果我们在能被n整除的范围内搜索x，我们可以让代码更快。
// Assumptions
// rand() in [0, RAND_MAX]
// n in (0, RAND_MAX]
int x;
// Keep searching for an x in a range divisible by n
do {
x = rand();
} while (x >= RAND_MAX - (RAND_MAX % n))
x %= n;
上面的循环应该非常快，平均1次迭代。
RAND_MAX值为3(实际上它应该比这个值高得多，但偏差仍然存在)，从这些计算中可以看出存在偏差:
1% 2 = 1 2% 2 = 0 3% 2 = 1 Random_between(1,3) % 2 =更可能是1
在本例中，当您想要0到1之间的随机数时，不应该使用% 2。你可以通过% 3得到一个0到2之间的随机数，因为在这种情况下:RAND_MAX是3的倍数。
另一种方法
有更简单的方法，但要加上其他答案，这是我的解，得到一个0到n - 1之间的随机数，所以有n种不同的可能性，没有偏差。
编码可能性数量所需的比特数(不是字节数)就是您需要的随机数据的比特数 从随机位编码数字 如果这个数字是>= n，重新启动(不取模)。
真正随机的数据是不容易获得的，所以为什么使用比需要更多的比特。
下面是Smalltalk中的一个示例，使用伪随机数生成器的位缓存。我不是安全专家，所以请自担风险。
next: n
| bitSize r from to |
n < 0 ifTrue: [^0 - (self next: 0 - n)].
n = 0 ifTrue: [^nil].
n = 1 ifTrue: [^0].
cache isNil ifTrue: [cache := OrderedCollection new].
cache size < (self randmax highBit) ifTrue: [
Security.DSSRandom default next asByteArray do: [ :byte |
(1 to: 8) do: [ :i | cache add: (byte bitAt: i)]
]
].
r := 0.
bitSize := n highBit.
to := cache size.
from := to - bitSize + 1.
(from to: to) do: [ :i |
r := r bitAt: i - from + 1 put: (cache at: i)
].
cache removeFrom: from to: to.
r >= n ifTrue: [^self next: n].
^r
推荐文章
- cplusplus.com给出的错误、误解或坏建议是什么?
- 如何在bash中使用mod操作符?
- 找出质数最快的算法是什么?
- 生成具有给定(数值)分布的随机数
- 为什么不使用异常作为常规的控制流呢?
- c++枚举类可以有方法吗?
- 格式化IO函数(*printf / *scanf)中的转换说明符%i和%d之间的区别是什么?
- 什么是序列化?
- 将析构函数设为私有有什么用?
- main()中的Return语句vs exit()
- 为什么c#不提供c++风格的'friend'关键字?
- 在php中生成一个随机密码
- GLSL的随机/噪声函数
- 在函数的签名中添加关键字
- 我如何在Visual Studio中预处理后看到C/ c++源文件?
