IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

C++ Discussion :

Pourquoi rand()%N n'est il pas équiprobable?


Sujet :

C++

  1. #1
    Expert confirmé
    Avatar de Pragmateek
    Homme Profil pro
    Formateur expert .Net/C#
    Inscrit en
    Mars 2006
    Messages
    2 635
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 37
    Localisation : France, Val de Marne (Île de France)

    Informations professionnelles :
    Activité : Formateur expert .Net/C#
    Secteur : Conseil

    Informations forums :
    Inscription : Mars 2006
    Messages : 2 635
    Points : 4 062
    Points
    4 062
    Par défaut Pourquoi rand()%N n'est il pas équiprobable?
    Salut!

    J'ai vu dans la FAQ C:
    http://c.developpez.com/faq/c/?page=..._random_bornes

    que rand%N n'était pas équiprobable et qu'il fallait préferer:
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    (int)((float)rand() / RAND_MAX * (N - 1));
    Pourquoi?

    La partie aléatoire n'est que dans "rand()" les autres opérations,une fois que "rand()" est fixé n'ont rien d'aléatoire.

    Pourriez vous m'éclairer?

    Merci!
    Formateur expert .Net/C#/WPF/EF Certifié MCP disponible sur Paris, province et pays limitrophes (enseignement en français uniquement).
    Mon blog : pragmateek.com

  2. #2
    Membre éprouvé

    Homme Profil pro
    Étudiant
    Inscrit en
    Mars 2005
    Messages
    634
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 36
    Localisation : Suisse

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Mars 2005
    Messages : 634
    Points : 1 205
    Points
    1 205
    Par défaut
    Quelques explications dans ce thread : http://www.developpez.net/forums/vie...atoire#2464639
    Fiquet
    - FAQ SDL
    - FAQ C++

  3. #3
    Rédacteur

    Avatar de Matthieu Brucher
    Profil pro
    Développeur HPC
    Inscrit en
    Juillet 2005
    Messages
    9 810
    Détails du profil
    Informations personnelles :
    Âge : 42
    Localisation : France, Pyrénées Atlantiques (Aquitaine)

    Informations professionnelles :
    Activité : Développeur HPC
    Secteur : Industrie

    Informations forums :
    Inscription : Juillet 2005
    Messages : 9 810
    Points : 20 970
    Points
    20 970
    Par défaut
    Si rand() tire un nombre entre 0 et 6 inclus de manière uniforme et que tu fais rand() % N, tu as une chance sur 4 d'avoir 0 et 1 sur 3 d'avoir 1. Ce n'est pas équiprobable.

  4. #4
    Expert confirmé
    Avatar de Pragmateek
    Homme Profil pro
    Formateur expert .Net/C#
    Inscrit en
    Mars 2006
    Messages
    2 635
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 37
    Localisation : France, Val de Marne (Île de France)

    Informations professionnelles :
    Activité : Formateur expert .Net/C#
    Secteur : Conseil

    Informations forums :
    Inscription : Mars 2006
    Messages : 2 635
    Points : 4 062
    Points
    4 062
    Par défaut
    Citation Envoyé par Miles
    Si rand() tire un nombre entre 0 et 6 inclus de manière uniforme et que tu fais rand() % N, tu as une chance sur 4 d'avoir 0 et 1 sur 3 d'avoir 1. Ce n'est pas équiprobable.
    par exemple si N=10:

    on aura jamais 7,8,9!

    Je commence à voir pourquoi ça ne marche pas sans pour autant cerner entierement le probleme.

    Je vais consulter l'autre topic.

    Merci!
    Formateur expert .Net/C#/WPF/EF Certifié MCP disponible sur Paris, province et pays limitrophes (enseignement en français uniquement).
    Mon blog : pragmateek.com

  5. #5
    Expert confirmé
    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    Décembre 2003
    Messages
    3 549
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Essonne (Île de France)

    Informations professionnelles :
    Activité : Ingénieur développement logiciels

    Informations forums :
    Inscription : Décembre 2003
    Messages : 3 549
    Points : 4 625
    Points
    4 625
    Par défaut
    par exemple si N=10:

    on aura jamais 7,8,9!
    Euh si, quand même.
    Boost ftw

  6. #6
    Expert éminent sénior
    Avatar de Luc Hermitte
    Homme Profil pro
    Développeur informatique
    Inscrit en
    Août 2003
    Messages
    5 275
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Haute Garonne (Midi Pyrénées)

    Informations professionnelles :
    Activité : Développeur informatique
    Secteur : Aéronautique - Marine - Espace - Armement

    Informations forums :
    Inscription : Août 2003
    Messages : 5 275
    Points : 10 985
    Points
    10 985
    Par défaut
    Tous les cas ne sont pas précisément équiprobables. On n'y peut pas forcément grand chose. Par contre, cela s'agrave un petit peu si tu considères la probabibilité que ton résultat soit inférieur à un certan seuil.

    Avec u_N uniforme sur [0..N[, amuses-toi à calculer formellement les réparttion de "u_N % K", et les probas de "u_N % k < S". Avec des valeurs petites les écarts introduits se voient mieux.
    Après, remplace le modulo par une "remise à l'échelle" et refais les calculs.
    Blog|FAQ C++|FAQ fclc++|FAQ Comeau|FAQ C++lite|FAQ BS|Bons livres sur le C++
    Les MP ne sont pas une hotline. Je ne réponds à aucune question technique par le biais de ce média. Et de toutes façons, ma BAL sur dvpz est pleine...

  7. #7
    Rédacteur

    Avatar de Matthieu Brucher
    Profil pro
    Développeur HPC
    Inscrit en
    Juillet 2005
    Messages
    9 810
    Détails du profil
    Informations personnelles :
    Âge : 42
    Localisation : France, Pyrénées Atlantiques (Aquitaine)

    Informations professionnelles :
    Activité : Développeur HPC
    Secteur : Industrie

    Informations forums :
    Inscription : Juillet 2005
    Messages : 9 810
    Points : 20 970
    Points
    20 970
    Par défaut
    Citation Envoyé par loufoque
    par exemple si N=10:

    on aura jamais 7,8,9!
    Euh si, quand même.
    Euh... non. Si rand() retourne un nombre entre 0 et 6, il n'y a aucune chance pour qu'il retourne 7, 8 ou 9.

  8. #8
    Expert éminent

    Inscrit en
    Novembre 2005
    Messages
    5 145
    Détails du profil
    Informations forums :
    Inscription : Novembre 2005
    Messages : 5 145
    Points : 6 911
    Points
    6 911
    Par défaut
    Citation Envoyé par Luc Hermitte
    Tous les cas ne sont pas précisément équiprobables. On n'y peut pas forcément grand chose. Par contre, cela s'agrave un petit peu si tu considères la probabibilité que ton résultat soit inférieur à un certan seuil.

    Avec u_N uniforme sur [0..N[, amuses-toi à calculer formellement les réparttion de "u_N % K", et les probas de "u_N % k < S". Avec des valeurs petites les écarts introduits se voient mieux.
    Après, remplace le modulo par une "remise à l'échelle" et refais les calculs.
    Note que la remise a l'echelle dans la FAQ est mal faite et ne fait que changer les nombres qui sont choisis plus souvent que les autres. Mais bon, je crois que j'expliquais ca dans l'autre thread.
    Les MP ne sont pas là pour les questions techniques, les forums sont là pour ça.

  9. #9
    Membre actif
    Inscrit en
    Décembre 2003
    Messages
    272
    Détails du profil
    Informations forums :
    Inscription : Décembre 2003
    Messages : 272
    Points : 284
    Points
    284
    Par défaut
    Le problème d'équiprobabilité ne vient pas vraiment de là. Les nombres générés sont assez grands pour éviter ce problème. Même si on considère des octets générés aléatoirement, et un modulo 6, on a des proba 42/256 et 43/256. En pratique c'est suffisemment proche.

    Le gros problème est que lors que le générateur sort un nombre "aléatoire", tout les bits ne sont pas équivalent. Pour les générateurs les plus connus, les bits de poid fort sont assez bien répartis, ceux de poid faible ont une structure assez prévisible.
    Il est par exemple possible que le bit 0 soit toujours nul. Dans ce cas un rand()%2 donnera toujours 0, alors qu'un rand()/2.0 aura le comportement souhaité.

    C'est pour la même raison qu'on déconseille vivement de tirer plusieurs bits aléatoire d'un seul tirage. Si on a besoin de 4 bits, on fait 4 fois rand()/2.0, et pas un truc du genre rand() >> 12.

  10. #10
    Expert confirmé
    Avatar de Pragmateek
    Homme Profil pro
    Formateur expert .Net/C#
    Inscrit en
    Mars 2006
    Messages
    2 635
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 37
    Localisation : France, Val de Marne (Île de France)

    Informations professionnelles :
    Activité : Formateur expert .Net/C#
    Secteur : Conseil

    Informations forums :
    Inscription : Mars 2006
    Messages : 2 635
    Points : 4 062
    Points
    4 062
    Par défaut
    Merci de toutes vos explications!

    J'y vois beaucoup plus clair.

    Je met le tag
    Formateur expert .Net/C#/WPF/EF Certifié MCP disponible sur Paris, province et pays limitrophes (enseignement en français uniquement).
    Mon blog : pragmateek.com

  11. #11
    Expert éminent

    Inscrit en
    Novembre 2005
    Messages
    5 145
    Détails du profil
    Informations forums :
    Inscription : Novembre 2005
    Messages : 5 145
    Points : 6 911
    Points
    6 911
    Par défaut
    Citation Envoyé par Ulmo
    Le problème d'équiprobabilité ne vient pas vraiment de là. Les nombres générés sont assez grands pour éviter ce problème. Même si on considère des octets générés aléatoirement, et un modulo 6, on a des proba 42/256 et 43/256. En pratique c'est suffisemment proche.
    La, il faut connaitre l'application pour se prononcer.

    Le gros problème est que lors que le générateur sort un nombre "aléatoire", tout les bits ne sont pas équivalent. Pour les générateurs les plus connus, les bits de poid fort sont assez bien répartis, ceux de poid faible ont une structure assez prévisible.
    Tu as des references? Parce que ma comprehension etait pour le moins differente: un certain type de generateur a ce probleme pour de mauvais parametres. Un generateur de ce type etait donne en exemple dans la norme C avec de mauvais parametres mais a ete repris tel quel par certaines implementations. Une fois je me suis amuse a verifier, aucunes implementations que j'ai regardees n'utilisait ce generateur.
    Les MP ne sont pas là pour les questions techniques, les forums sont là pour ça.

  12. #12
    Expert confirmé
    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    Décembre 2003
    Messages
    3 549
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Essonne (Île de France)

    Informations professionnelles :
    Activité : Ingénieur développement logiciels

    Informations forums :
    Inscription : Décembre 2003
    Messages : 3 549
    Points : 4 625
    Points
    4 625
    Par défaut
    Citation Envoyé par Miles
    Citation Envoyé par loufoque
    par exemple si N=10:

    on aura jamais 7,8,9!
    Euh si, quand même.
    Euh... non. Si rand() retourne un nombre entre 0 et 6, il n'y a aucune chance pour qu'il retourne 7, 8 ou 9.
    Il parlait du code rand() % N.
    Si N vaut 10, comme il le dit, alors on peut effectivement avoir 7, 8 ou 9.
    Boost ftw

  13. #13
    Rédacteur

    Avatar de Matthieu Brucher
    Profil pro
    Développeur HPC
    Inscrit en
    Juillet 2005
    Messages
    9 810
    Détails du profil
    Informations personnelles :
    Âge : 42
    Localisation : France, Pyrénées Atlantiques (Aquitaine)

    Informations professionnelles :
    Activité : Développeur HPC
    Secteur : Industrie

    Informations forums :
    Inscription : Juillet 2005
    Messages : 9 810
    Points : 20 970
    Points
    20 970
    Par défaut
    Tu lis seulement la moitié des messages ?

+ Répondre à la discussion
Cette discussion est résolue.

Discussions similaires

  1. Pourquoi runat="server" n'est il pas implicite.
    Par aityahia dans le forum ASP.NET
    Réponses: 4
    Dernier message: 10/08/2008, 11h05
  2. Réponses: 3
    Dernier message: 04/03/2007, 10h34
  3. [C# 2.0] Pourquoi mon DataAdapter n'est pas instancié ?
    Par FraktaL dans le forum Services Web
    Réponses: 2
    Dernier message: 04/07/2006, 01h04
  4. [ADO.Net][VB.NET 2.0] Pourquoi ma bdd n'est pas modifiée ?
    Par olivier57b dans le forum Accès aux données
    Réponses: 5
    Dernier message: 30/04/2006, 22h51

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo