C 中的随机整数，rand()%N 与整数运算相比有多糟糕？它的缺陷是什么？

Question

编辑：我的问题是：rand()%N 被认为是非常糟糕的，而使用整数运算被认为是优越的，但我看不出两者之间的区别。

人们总是提到：

低位在rand()%N,
rand()%N很有预见性，
您可以将其用于游戏但不能用于加密

谁能解释一下这里是否存在这些问题以及如何看待？

低位非随机性的想法应该使我展示的两种情况的 PE 不同，但事实并非如此。

我想很多像我一样的人总是会避免使用 rand() 或 rand()%N，因为我们一直被告知这很糟糕。我很想知道用 c rand()%N 生成的 "wrong" 随机整数是如何有效的。这也是 Ryan Reich 在 How to generate a random integer number from within a range.

中的回答的跟进

老实说，那里的解释听起来很有说服力；尽管如此，我想我会试一试。所以，我以一种非常天真的方式比较分布。我运行两个随机生成器用于不同数量的样本和域。我没有看到计算密度而不是直方图的意义，所以我只是计算了直方图，并且只是通过观察，我会说它们看起来一样均匀。关于提出的另一点，关于实际的随机性（尽管是均匀分布的）。我再次天真地计算了这些运行的排列熵，这对两个样本集都是相同的，这告诉我们两者在出现的顺序方面没有区别。

所以，从很多方面来说，我觉得rand()%N就好了，怎么能看出他们的缺点呢？

在这里，我将向您展示一种非常简单、低效且不是很优雅（但我认为正确）的方法来计算这些样本并获得直方图和排列熵。对于不同数量的样本，我在 {5,10,25,50,100} 中显示域 (0,i) 的图：

我猜代码中没什么可看的，所以我将保留 C 和 matlab 代码以供复制。

#include <stdlib.h>
#include <stdio.h>
#include <time.h>

int main(int argc, char *argv[]){
        unsigned long max = atoi(argv[2]);
        int samples=atoi(argv[3]);
        srand(time(NULL));
        if(atoi(argv[1])==1){
                for(int i=0;i<samples;++i)
                        printf("%ld\n",rand()%(max+1));

        }else{
                for(int i=0;i<samples;++i){
                        unsigned long
                        num_bins = (unsigned long) max + 1,
                        num_rand = (unsigned long) RAND_MAX + 1,
                        bin_size = num_rand / num_bins,
                        defect   = num_rand % num_bins;

                        long x;
                        do {
                                x = rand();
                        }
                        while (num_rand - defect <= (unsigned long)x);
                        printf("%ld\n",x/bin_size);
                }
        }
        return 0;
}

这是绘制此图并计算 PE 的 Matlab 代码（我从中获取的排列的递归：https://www.mathworks.com/matlabcentral/answers/308255-how-to-generate-all-possible-permutations-without-using-the-function-perms-randperm）：

system('gcc randomTest.c -o randomTest.exe;');
max = 100;
samples = max*10000;
trials = 200;
system(['./randomTest.exe 1 ' num2str(max) ' ' num2str(samples) ' > file1'])
system(['./randomTest.exe 2 ' num2str(max) ' ' num2str(samples) ' > file2'])
a1=load('file1');
a2=load('file2');
uni = figure(1);
title(['Samples: ' num2str(samples)])
subplot(1,3,1)
h1 = histogram(a1,max+1);
title('rand%(max+1)')
subplot(1,3,2)
h2 = histogram(a2,max+1);
title('Integer arithmetic')
as=[a1,a2];
ns=3:8;
H = nan(numel(ns),size(as,2));
for op=1:size(as,2)
    x = as(:,op);
    for n=ns
        sequenceOcurrence = zeros(1,factorial(n));
        sequences = myperms(1:n);
        sequencesArrayIdx = sum(sequences.*10.^(size(sequences,2)-1:-1:0),2);
        for i=1:numel(x)-n
            [~,sequenceOrder] = sort(x(i:i+n-1));
            out = sequenceOrder'*10.^(numel(sequenceOrder)-1:-1:0).';
            sequenceOcurrence(sequencesArrayIdx == out) = sequenceOcurrence(sequencesArrayIdx == out) + 1;
        end
        chunks = length(x) - n + 1;
        ps = sequenceOcurrence/chunks;
        hh = sum(ps(logical(ps)).*log2(ps(logical(ps))));
        H(n,op) = hh/log2(factorial(n));
    end
end
subplot(1,3,3)
plot(ns,H(ns,:),'--*','linewidth',2)
ylabel('PE')
xlabel('Sequence length')
filename = ['all_' num2str(max) '_' num2str(samples) ];
export_fig(filename)

Answer 1

这两种方法都有其缺陷，您的图表只不过是对中心极限定理的漂亮验证！对于 rand() 的合理实施：

1u + RAND_MAX

N

% N 会受到 "pigeon-holing" 的影响
/((RAND_MAX + 1u)/N) 通常不会 均匀地 将 rand 的 return 分布在您的范围内，由于到整数截断效应。

总的来说，如果N比较小。 RAND_MAX，我喜欢 % 因为它的易处理性。在任何情况下，测试您的生成器以查看它是否具有适合您的应用程序的统计属性。

Answer 2

rand() % N 被认为非常差，不是因为分布不好，而是因为随机性差到不存在。（如果有的话，分布将太好。）

如果N相对于RAND_MAX不小，则两者

rand() % N

和

rand() / (RAND_MAX / N + 1)

会有大致相同的不良分布 -- 某些值出现的概率明显高于其他值。

查看分布直方图不会向您表明，对于某些实现，rand() % N 有一个非常非常糟糕的问题——表明您必须与以前的值进行一些关联。（例如，尝试取 rand() % 2，然后从您获得的先前值中减去，并绘制差异的直方图。如果差异永远不为 0，则您遇到了问题。）

我想说 rand() 的低位不是随机的实现只是有问题。我想所有那些有问题的实现现在都会消失。我认为程序员不必再担心调用 rand()%N 了。但是，不幸的是，我的愿望并没有改变这样一个事实，即这似乎是那些永远无法修复的错误之一，这意味着程序员仍然需要担心。

另见 C FAQ list, question 13.16。

Answer 3

由于模运算的工作方式，如果 N 与 RAND_MAX 相比显着，则执行 %N 会成功，因此您获得某些值的可能性比其他值大得多。假设 RAND_MAX 为 12，N 为 9。如果分布良好，则获得 0、1 或 2 之一的机会为 0.5，获得 3、4、5、6 之一的机会， 7、8为0.5。结果是你得到 0 而不是 4 的可能性是 2 倍。如果 N 是 RAND_MAX 的精确除数，则不会发生此分配问题，并且如果 N 与 [=23 相比非常小=] 这个问题变得不那么明显了。 RAND_MAX 可能不是一个特别大的值（可能是 2^15 - 1），使这个问题比您预期的更糟。 (rand() * n) / (RAND_MAX + 1) 的替代方案也不会给出均匀分布，但是，每 m 个值（对于某些 m）更有可能发生，而不是更可能的值都处于分布的低端。

如果 N 是 RAND_MAX 的 75%，则分布底部三分之一中的值的可能性是顶部三分之二中值的两倍（因为这是额外值映射到的位置）

rand() 的质量将取决于您所使用的系统的实施情况。我相信某些系统的实现非常糟糕，OS Xs 手册页声明 rand 已过时。 Debian 手册页说明如下：

Linux C 库中的 rand() 和 srand() 版本使用相同的随机数生成器为 random(3) 和 srandom(3)，因此低阶位应该与高阶位一样随机。然而，在年长的 rand() 实现，以及不同的当前实现系统中，低阶位的随机性远低于高阶位订单位。不要在旨在成为应用程序的应用程序中使用此功能当需要良好的随机性时可移植。（改用 random(3)。）

C 中的随机整数，rand()%N 与整数运算相比有多糟糕？它的缺陷是什么？

Random integers in C, how bad is rand()%N compared to integer arithmetic? What are its flaws?

c

random

distribution