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

Question

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

人们总是提到:

• 低位不是随机的rand()%N,

• rand()%N 是非常可预测的,

• 你可以将它用于游戏,但不能用于加密

有人可以解释这些问题是否属于这种情况以及如何看待？

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

我想像我这样的很多人总是会避免使用rand(),或者rand()%N因为我们总是被教导它非常糟糕.我很想知道rand()%N有效地生成c的"错误"随机整数是多少.这也是Ryan Reich在如何从一个范围内生成随机整数的答案的后续.

说实话,那里的解释听起来很有说服力; 尽管如此,我还以为我试一试.所以,我以非常天真的方式比较分布.我为不同数量的样本和域运行两个随机生成器.我没有看到计算密度而不是直方图的重点,所以我只计算直方图,只是通过观察,我会说它们看起来都一样均匀.关于提出的另一点,关于实际的随机性(尽管是均匀分布的).I - 再次天真地计算这些运行的置换熵,对于两个样本集都是相同的,这告诉我们两者之间关于事件排序没有区别.

因此,出于多种目的,在我看来,rand()%N这样就好了,我们怎么能看到它们的缺陷呢？

在这里,我向您展示了一种非常简单,低效且不太优雅(但我认为正确)的计算这些样本的方法,并将直方图与排列熵一起得到.对于不同数量的样本,我在{5,10,25,50,100}中显示了域(0,i)和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;
}

这里是Matlab代码来绘制这个并计算PE(我从中获取的排列的递归:https://www.mathworks.com/matlabcentral/answers/308255-how-to-generate-all-possible-排列 - 不使用功能 - 烫发 - 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

由于模算术的工作方式，如果 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 与 RAND_MAX 相比非常小，则问题会变得不那么明显。RAND_MAX 可能不是一个特别大的值（可能是 2^15 - 1），使这个问题比您想象的更糟糕。另一种做法(rand() * n) / (RAND_MAX + 1)也不会给出均匀分布，但是，它将是每个m值（对于某些m）更有可能出现，而不是更可能的值都位于分布的低端。

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

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

Linux C 库中的 rand() 和 srand() 版本使用与 random(3) 和 srandom(3) 相同的随机数生成器，因此低阶位应该与高阶位一样随机。然而，在较旧的 rand() 实现上以及在不同系统上的当前实现上，低阶位比高阶位的随机性要低得多。当需要良好的随机性时，请勿在便携式应用程序中使用此功能。（使用 random(3) 代替。）