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

前端之家收集整理的这篇文章主要介绍了C中的随机整数,与整数运算相比,rand()%N有多糟糕?它的缺点是什么?前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。
编辑:
我的问题是:rand()%N被认为非常糟糕,而整数算术的使用被认为是优越的,但我看不出两者之间的区别.

人们总是提到:

> rand()%N中的低位不是随机的,
> rand()%N是非常可预测的,
>您可以将它用于游戏,但不能用于加密

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

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

我想像我一样的人总是会避免使用rand()或rand()%N,因为我们总是被教导它非常糟糕.我很想知道c rand()%N生成的“错误随机整数有效.这也是Ryan Reich在How to generate a random integer number from within a range年回答的后续行动.

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

所以,出于很多目的,在我看来rand()%N会很好,我们怎么能看到它们的缺陷呢?

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

我想在代码中没什么可看的,所以我会留下C和matlab代码用于复制目的.

  1. #include <stdlib.h>
  2. #include <stdio.h>
  3. #include <time.h>
  4.  
  5. int main(int argc,char *argv[]){
  6. unsigned long max = atoi(argv[2]);
  7. int samples=atoi(argv[3]);
  8. srand(time(NULL));
  9. if(atoi(argv[1])==1){
  10. for(int i=0;i<samples;++i)
  11. printf("%ld\n",rand()%(max+1));
  12.  
  13. }else{
  14. for(int i=0;i<samples;++i){
  15. unsigned long
  16. num_bins = (unsigned long) max + 1,num_rand = (unsigned long) RAND_MAX + 1,bin_size = num_rand / num_bins,defect = num_rand % num_bins;
  17.  
  18. long x;
  19. do {
  20. x = rand();
  21. }
  22. while (num_rand - defect <= (unsigned long)x);
  23. printf("%ld\n",x/bin_size);
  24. }
  25. }
  26. return 0;
  27. }

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

  1. system('gcc randomTest.c -o randomTest.exe;');
  2. max = 100;
  3. samples = max*10000;
  4. trials = 200;
  5. system(['./randomTest.exe 1 ' num2str(max) ' ' num2str(samples) ' > file1'])
  6. system(['./randomTest.exe 2 ' num2str(max) ' ' num2str(samples) ' > file2'])
  7. a1=load('file1');
  8. a2=load('file2');
  9. uni = figure(1);
  10. title(['Samples: ' num2str(samples)])
  11. subplot(1,3,1)
  12. h1 = histogram(a1,max+1);
  13. title('rand%(max+1)')
  14. subplot(1,2)
  15. h2 = histogram(a2,max+1);
  16. title('Integer arithmetic')
  17. as=[a1,a2];
  18. ns=3:8;
  19. H = nan(numel(ns),size(as,2));
  20. for op=1:size(as,2)
  21. x = as(:,op);
  22. for n=ns
  23. sequenceOcurrence = zeros(1,factorial(n));
  24. sequences = myperms(1:n);
  25. sequencesArrayIdx = sum(sequences.*10.^(size(sequences,2)-1:-1:0),2);
  26. for i=1:numel(x)-n
  27. [~,sequenceOrder] = sort(x(i:i+n-1));
  28. out = sequenceOrder'*10.^(numel(sequenceOrder)-1:-1:0).';
  29. sequenceOcurrence(sequencesArrayIdx == out) = sequenceOcurrence(sequencesArrayIdx == out) + 1;
  30. end
  31. chunks = length(x) - n + 1;
  32. ps = sequenceOcurrence/chunks;
  33. hh = sum(ps(logical(ps)).*log2(ps(logical(ps))));
  34. H(n,op) = hh/log2(factorial(n));
  35. end
  36. end
  37. subplot(1,3)
  38. plot(ns,H(ns,:),'--*','linewidth',2)
  39. ylabel('PE')
  40. xlabel('Sequence length')
  41. filename = ['all_' num2str(max) '_' num2str(samples) ];
  42. export_fig(filename)

解决方法

由于模数运算的方式如果N与RAND_MAX相比显着,那么%N将使得它更有可能获得某些值而不是其他值.想象一下,RAND_MAX是12,N是9.如果分布是好的,那么获得0,1或2之一的几率是0.5,获得3,4,5,6,7,8之一的机会是0.5.结果是你获得0而不是4的可能性是两倍.如果N是RAND_MAX的精确分频器,则不会发生这种分布问题,并且如果N与RAND_MAX相比非常小,则问题变得不那么明显. RAND_MAX可能不是特别大的值(可能是2 ^ 15 – 1),这使得这个问题比你预期的更糟. do(rand()* n)/(RAND_MAX 1)的替代方案也不会给出均匀分布,但是,每个m值(对于某些m)将更可能发生而不是更可能发生值都在分布的低端.

如果N是RAND_MAX的75%,则分布的底部三分之一的值是前三分之二的值的两倍(因为这是额外值映射到的位置)

rand()的质量取决于您所使用的系统的实现.我相信有些系统的实现很差,OS Xs手册页声明rand已经过时了. Debian手册页说明如下:

Linux C Library中的rand()和srand()版本使用相同的版本随机生成随机(3)和srandom(3),所以低阶比特应该与高阶比特一样随机.但是,老年人rand()实现,以及不同的当前实现系统中,低阶位的随机性要小于订单位.请勿在应用程序中使用此功能便携式,需要良好的随机性. (改为使用随机(3).)

猜你在找的C&C++相关文章