Est-ce que «n * (rand () / RAND_MAX)» crée une dissortingbution de nombres aléatoires asymésortingque?

J’aimerais trouver un moyen non aléatoire d’obtenir des nombres aléatoires dans C (même si tout au plus je vais l’utiliser pour des valeurs de 0 à 20, et plus vraisemblablement que de 0 à 8). J’ai vu cette formule, mais après quelques tests, je ne sais pas si elle est biaisée ou non. De l’aide?

Voici la fonction complète utilisée:

int randNum() { return 1 + (int) (10.0 * (rand() / (RAND_MAX + 1.0))); } 

Je l’ai ensemencé en utilisant:

 unsigned int iseed = (unsigned int)time(NULL); srand (iseed); 

Celui suggéré ci-dessous refuse de travailler pour moi, j’ai essayé

 int greek; for (j=0; j<50000; j++) { greek =rand_lim(5); printf("%d, " greek); greek =(int) (NUM * (rand() / (RAND_MAX + 1.0))); int togo=number[greek]; number[greek]=togo+1; } 

et il cesse de fonctionner et me donne le même nombre 50000 fois lorsque je commente printf.

Oui, il est asymésortingque, à moins que votre RAND_MAX ne soit un multiple de 10.

Si vous prenez les nombres de 0 à RAND_MAX et essayez de les diviser en 10 stacks, vous n’avez en réalité que trois possibilités:

  1. RAND_MAX est un multiple de 10 et les stacks sont égales.
  2. RAND_MAX n’est pas un multiple de 10 et les stacks sont inégales.
  3. Vous le divisez en groupes inégaux pour commencer, mais vous éliminez tous les “suppléments” qui le rendraient inégal.

Vous avez rarement le contrôle sur RAND_MAX, et c’est souvent un nombre premier de toute façon. Cela ne laisse vraiment que 2 et 3 comme possibilités.

La troisième option ressemble à peu près à ceci: [Edit: Après mûre reflection, j’ai révisé cette méthode pour produire des nombres compris dans la plage 0 … (limite-1), afin de s’adapter à la plupart des opérations en C et C ++. Cela simplifie également le code (un tout petit peu).

 int rand_lim(int limit) { /* return a random number in the range [0..limit) */ int divisor = RAND_MAX/limit; int retval; do { retval = rand() / divisor; } while (retval == limit); return retval; } 

Pour tous ceux qui doutent que cette méthode laisse un peu de côté, j’ai aussi écrit une version assez différente, uniquement à des fins de test. Celui-ci utilise un générateur résolument non aléatoire avec une plage très limitée, nous pouvons donc simplement parcourir tous les nombres de la plage. Cela ressemble à ceci:

 #include  #include  #define MAX 1009 int next_val() { // just return consecutive numbers static int v=0; return v++; } int lim(int limit) { int divisor = MAX/limit; int retval; do { retval = next_val() / divisor; } while (retval == limit); return retval; } #define LIMIT 10 int main() { // we'll allocate extra space at the end of the array: int buckets[LIMIT+2] = {0}; int i; for (i=0; i 

Nous commençons donc par des nombres de 0 à 1009 (1009 étant le nombre premier, il ne s'agira donc pas d'un multiple exact de la plage choisie). Nous commençons donc avec 1009 nombres et nous les divisons en 10 catégories. Cela devrait donner 100 dans chaque seau, et les 9 restants (pour ainsi dire) sont "mangés" par la boucle do / while. Comme il est écrit en ce moment, il alloue et imprime un seau supplémentaire. Quand je le lance, j'obtiens exactement 100 dans chacun des seaux 0..9 et 0 dans le seau 10. Si je commente la boucle do / while, je vois 100 dans chacun des 0..9 et 9 dans le seau 10. .

Juste pour être sûr, j'ai relancé le test avec divers autres nombres à la fois pour la plage produite (principalement des nombres premiers utilisés) et pour le nombre de compartiments. Jusqu'à présent, je n'ai pas réussi à obtenir des résultats asymésortingques pour une plage donnée (tant que la boucle do / while est activée, bien sûr).

Un autre détail: il y a une raison pour laquelle j'ai utilisé la division au lieu du rest dans cet algorithme. Avec une bonne implémentation (voire décente) de rand() cela n’a aucune importance, mais lorsque vous attachez des nombres à une plage à l’aide de la division, vous conservez les bits supérieurs de l’entrée. Lorsque vous le faites avec le rest, vous conservez les bits les plus bas de l’entrée. En l'occurrence, avec un générateur de nombres pseudo aléatoires congruentiels linéaire typique, les bits inférieurs tendent à être moins aléatoires que les bits supérieurs. Une implémentation raisonnable éliminera déjà un certain nombre des bits les moins significatifs, rendant ainsi cette opération non pertinente. D'un autre côté, il existe de très mauvaises implémentations de rand , et avec la plupart d'entre elles, vous obtenez une meilleure qualité de sortie en utilisant la division plutôt que le rest.

Je devrais également souligner qu'il existe des générateurs qui font à peu près le contraire - les bits inférieurs sont plus aléatoires que les bits supérieurs. Au moins dans mon expérience, ce sont assez rares. Ce avec quoi les bits supérieurs sont plus aléatoires sont considérablement plus communs.