Nombre entier aléatoire en C, quelle est la valeur de rand ()% N par rapport à l’arithmétique entière? Quels sont ses défauts?

EDIT: Ma question est la suivante: rand()%N est considéré comme très mauvais, alors que l’utilisation de l’arithmétique entière est considérée comme supérieure, mais je ne vois pas la différence entre les deux.

Les gens mentionnent toujours:

  • les bits faibles ne sont pas aléatoires dans rand()%N ,

  • rand()%N est très prévisible,

  • vous pouvez l’utiliser pour les jeux mais pas pour la cryptographie

Quelqu’un peut-il expliquer si l’un de ces points est le cas ici et comment voir cela?

L’idée du caractère non aléatoire des bits inférieurs est quelque chose qui devrait différencier le PE des deux cas que je montre, mais ce n’est pas le cas.

J’imagine que beaucoup, comme moi, éviteraient toujours d’utiliser rand() ou rand()%N parce que nous avons toujours appris que c’est très mauvais. J’étais curieux de voir comment “faux” entiers aléatoires générés avec c rand()%N sont effectivement. Cela fait également suite à la réponse de Ryan Reich dans Comment générer un nombre entier aléatoire dans une plage .

L’explication semble très convaincante, pour être honnête; Néanmoins, j’ai pensé essayer. Donc, je compare les dissortingbutions d’une manière TRÈS naïve. Je lance les deux générateurs aléatoires pour différents nombres d’échantillons et de domaines. Je ne voyais pas l’intérêt de calculer une densité plutôt que des histogrammes, alors je me suis contenté de calculer des histogrammes et, rien qu’en regardant, je dirais qu’ils ont tous deux la même apparence. En ce qui concerne l’autre point qui a été soulevé, à savoir le caractère aléatoire réel (bien qu’il soit uniformément dissortingbué). Encore une fois naïvement, je calcule l’entropie de permutation pour ces exécutions, qui sont les mêmes pour les deux ensembles d’échantillons, ce qui nous indique qu’il n’y a pas de différence entre les deux en ce qui concerne le classement de l’occurrence.

Donc, pour de nombreuses raisons, il me semble que rand()%N serait très bien, comment pouvons-nous voir leurs défauts?

Ici, je vous montre une manière très simple, inefficace et pas très élégante (mais je pense correcte) de calculer ces échantillons et d’obtenir les histogrammes avec les entropies de permutation. Je montre des tracés pour les domaines (0, i) avec i dans {5,10,25,50,100} pour un nombre différent d’échantillons:

5 valeurs, 5k échantillons

10 valeurs 10k échantillons

25 valeurs, 250k échantillons

100 valeurs, échantillons 1M

Je suppose qu’il n’y a pas grand-chose à voir dans le code. Je vais donc laisser le code C et le code matlab à des fins de réplication.

 #include  #include  #include  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; } 

Et voici le code Matlab permettant de tracer cela et de calculer les PE (la récursivité des permutations dont je tire le sens: https://www.mathworks.com/matlabcentral/answers/308255-how-to-generate-all-possible-possible- permutations-sans-utilisation-de-la-fonction-perms-randperm ):

 system('gcc randomTest.c -o randomTest.exe;'); max = 100; samples = max*10000; sortingals = 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) 

    Les deux approches ont leurs pièges, et vos graphiques ne sont guère plus qu’une jolie vérification du théorème de la limite centrale! Pour une implémentation judicieuse de rand() :

    1. % N souffre d’un effet de “pigeon” si 1u + RAND_MAX n’est pas un multiple de N

    2. /((RAND_MAX + 1u)/N) ne dissortingbue généralement pas le retour de rand de manière uniforme sur votre plage, en raison d’effets de troncature d’entier.

    Dans l’ensemble, si N est petit, cf. RAND_MAX , je RAND_MAX % pour sa RAND_MAX . Dans tous les cas, testez votre générateur pour voir s’il possède les propriétés statistiques appropriées pour votre application.

    rand() % N est considéré comme extrêmement pauvre non pas parce que la dissortingbution est mauvaise, mais parce que le caractère aléatoire est faible à inexistant. (Si quelque chose la dissortingbution sera trop bonne.)

    Si N n’est pas petit par rapport à RAND_MAX, les deux

     rand() % N 

    et

     rand() / (RAND_MAX / N + 1) 

    aura plus ou moins la même dissortingbution médiocre – certaines valeurs apparaîtront avec une probabilité beaucoup plus élevée que d’autres.

    Examiner les histogrammes de dissortingbution ne vous montrera pas que pour certaines implémentations, rand() % N a un problème bien plus grave: montrer que vous devez effectuer certaines corrélations avec les valeurs précédentes. (Par exemple, essayez de prendre rand() % 2 , puis de soustraire de la valeur précédente et de tracer un histogramme des différences. Si la différence n’est jamais égale à 0, vous avez un problème.)

    Je voudrais dire que les implémentations pour lesquelles les bits de poids faible de rand() ne sont pas aléatoires sont simplement boguées. J’aimerais penser que toutes ces implémentations de buggy auraient déjà disparu. J’aimerais penser que les programmeurs ne devraient plus avoir à s’inquiéter d’appeler davantage rand()%N Mais, malheureusement, mes souhaits ne changent pas le fait que cela semble être l’un de ces bugs qui ne sont jamais corrigés, ce qui signifie que les programmeurs doivent toujours s’inquiéter.

    Voir aussi la liste des FAQ C , question 13.16 .

    En raison du fonctionnement de l’arithmétique modulo, si N est significatif par rapport à RAND_MAX, faire% N vous permettra d’obtenir beaucoup plus de chances d’obtenir certaines valeurs que d’autres. Imaginez que RAND_MAX vaut 12 et N, 9. Si la dissortingbution est bonne, les chances d’obtenir 0, 1 ou 2 sont respectivement égales à 0,5 et 3, 4, 5, 6, 7 et 8. 0,5. Le résultat étant que vous êtes deux fois plus susceptible d’obtenir un 0 au lieu de 4. Si N est un diviseur exact de RAND_MAX, ce problème de dissortingbution ne se produit pas et si N est très petit par rapport à RAND_MAX, le problème devient moins perceptible. RAND_MAX peut ne pas être une valeur particulièrement élevée (peut-être 2 ^ 15 – 1), ce qui rend le problème plus grave que prévu. L’alternative de faire (rand() * n) / (RAND_MAX + 1) ne donne pas non plus une dissortingbution égale, cependant, ce sera chaque m ème valeur (pour certains m ) qui sera plus susceptible de se produire plutôt que la des valeurs plus probables toutes se situant au bas de la dissortingbution.

    Si N est égal à 75% de RAND_MAX, les valeurs du tiers inférieur de votre dissortingbution sont deux fois plus susceptibles que les valeurs des deux tiers supérieurs (car c’est là que les valeurs supplémentaires correspondent).

    La qualité de rand() dépendra de la mise en oeuvre du système sur lequel vous êtes. Je pense que la mise en œuvre de certains systèmes est très médiocre. Les pages de manuel d’OS X déclarent rand obsolète. La page de manuel Debian dit ce qui suit:

    Les versions de rand () et srand () de la bibliothèque Linux C utilisent le même générateur de nombres aléatoires que random (3) et srandom (3). Par conséquent, les bits de poids faible doivent être aussi aléatoires que les bits de poids fort. Cependant, sur les implémentations plus anciennes de rand () et sur les implémentations actuelles sur différents systèmes, les bits de poids faible sont beaucoup moins aléatoires que les bits de poids fort. N’utilisez pas cette fonction dans des applications destinées à être portables lorsqu’un bon caractère aléatoire est requirejs. (Utilisez random (3) à la place.)