1
votes

Problème avec rand% 100 pour la génération de nombres aléatoires en C

J'ai donc un devoir, et nous devons générer des nombres aléatoires entre 1 et 100 en C. J'ai un exemple de travail avec int i = rand ()% 100.

Mais d'après les devoirs techniquement incorrects que je ne comprends pas vraiment. L'explication des devoirs est la suivante

"1.1 Nous utilisons un générateur de nombres aléatoires pour simuler les temps d'arrivée des bus. ===> la fonction rand (). La fonction rand () renvoie un pseudo nombre aléatoire 0 à RAND_MAX (2 ^ 31-1 sous linux). Pour générer un nombre aléatoire, rn, entre 0,0 et 1,0; rn = rand () / RAND_MAX. (D'ailleurs, beaucoup de gens font ci-dessous pour créer, disons, des nombres aléatoires à 2 chiffres. R_num = rand ()% 100; car% 100 est compris entre 0 et 99. Cependant, c'est faux. La bonne façon de générer un nombre aléatoire à 2 chiffres est de: diviser 0-RAND_MAX en 10 intervalles et voir où se situe le nombre aléatoire. L'intervalle de temps est, it = RAND_MAX / 100 . Ensuite, mappez-le à l'un des 0 à 99 par ce qui suit: 0 1 2 3 ......... 99 0 it 2 it 3 it 99 it to RAND_MAX If le rand () renvoie un nombre compris entre (12 it) et (13 * it), le nombre aléatoire à 2 chiffres est 12.) "

J'espérais que quelqu'un pourrait essayer d'expliquer ce qu'il dit, je ne cherche pas vraiment d'exemples de code juste pour comprendre le problème.

1 commentaires

La méthode d'intervalle a en fait le même problème que la méthode%.

3 Réponses :

6
votes

Il y a là quelques problèmes, tous deux liés au fonctionnement de l'opérateur modulo. a% b vous donne effectivement le reste lorsque vous divisez a par b. Supposons donc que nous calculons les nombres modulo 4. Supposons également que RAND_MAX = 6, car je ne veux vraiment pas avoir plus de 32768 lignes dans ma table.

  a | a % 4
------------
  0 | 0
  1 | 1
  2 | 2
  3 | 3
  4 | 0
  5 | 1
  6 | 2

Donc, si vous utilisez votre approche pour générer des nombres aléatoires entre 1 et 4, vous avez deux problèmes. Tout d'abord, le plus simple: vous générez des nombres entre 0 et 3, pas 1 et 4. Le résultat de l'opérateur modulo sera toujours compris entre 0 et le module.

L'autre problème est plus subtil. Si RAND_MAX ne se divise pas uniformément dans le module, vous n'obtiendrez pas la même probabilité pour chaque nombre. Dans le cas de notre exemple, il y a 2 façons de faire de 0 à 2, mais une seule façon de faire 3. Donc, 3 se produira ~ 14,3% du temps, et chaque autre nombre se produira ~ 28,6% du temps. Pour obtenir une distribution uniforme, vous devez trouver un moyen de traiter les cas où RAND_MAX ne se divise pas uniformément.

0 commentaires

1
votes

RAND_MAX est généralement 2 ^ 31 - 1 donc il est égal à 2147483647 .

Mais supposons pour simplifier que nous avons un système très étrange, avec RAND_MAX = 100 (donc rand () peut renvoyer 0 à 100 , soit 101 nombres ). Et supposons que la fonction rand () a une distribution uniforme a>.

Maintenant, quelle est la probabilité de rand ()% 100 ? Les nombres 1 à 99 ont la même probabilité, soit 1/101 . Mais 0 a la probabilité 2/101 car lorsque rand () retourne 0 et quand rand ( ) return 100 , l'expression rand ()% 100 sera égale à 0 . Ainsi, 0 peut venir plus souvent que n'importe quel autre nombre, en fait deux fois plus souvent. Donc notre distribution de nombres à 2 chiffres avec rand ()% 100 n'est pas uniforme.

Maintenant, le texte propose une solution au problème. La solution proposée consiste à diviser la région 0 à RAND_MAX en 100 parties paires, de sorte que les nombres dans chaque partie aient la même probabilité. Puis lancez rand () et voyez dans quelle région le numéro s'est terminé. Si RAND_MAX est 2147483647 et que nous obtenons par exemple un numéro 279172968 , nous pouvons voir qu'il se termine dans la 13e région - entre RAND_MAX / 100 * 13 = 279172868 et RAND_MAX / 100 * 14 = 300647704 .

La solution est également imparfaite, comme nous pouvons le voir, qu'il est impossible de diviser 0 à RAND_MAX en 100 parties paires lorsque RAND_MAX% 100 n'est pas égal à 0.

Je pense que la seule solution viable est de supprimer tous les nombres supérieurs à RAND_MAX / 100 * 100 (en utilisant l'arithmétique des nombres entiers C). Le reste des nombres aura une distribution uniforme et le maximum sera divisible par 100, donc avec le reste, nous pouvons simplement rand ()% 100 . Donc quelque chose comme ceci:

int get_2_digit_number() {
      int r = 0;
      while (1) {
          r = rand();
          if (r > (RAND_MAX / 100 * 100)) { 
              continue;
          }
          break;
      }
      return r % 100;
}

0 commentaires

1
votes

Vous pouvez trouver du code pertinent sur SO. Par exemple, le code rand_int () ci-dessous est basé sur le code des entiers dans une réponse à Cette implémentation C de Fisher-Yates shuffle est-elle correcte? (et en particulier le réponse de Roland Illig ):

static size_t rand_int(size_t n)
{
    size_t limit = RAND_MAX - RAND_MAX % n;
    size_t rnd;

    while ((rnd = rand()) >= limit)
        ;
    return rnd % n;
}

L'idée est de calculer et d'ignorer les grandes valeurs renvoyées par rand () qui conduiraient à des résultats biaisés. Lorsqu'une des grandes valeurs est renvoyée, vous l'ignorez et essayez la valeur suivante. Cela nécessitera rarement plus de deux appels à rand().

Vous pouvez trouver certaines des références externes dans Shuffle array en C également utile.

0 commentaires