Comment la fonction rand () / srand () est-elle implémentée dans C

Dupliquer possible:
Comment fonctionne rand ()? At-il certaines tendances? Y a-t-il quelque chose de mieux à utiliser?

Je sais comment le mettre en œuvre. Cependant, j’aimerais comprendre comment le rand se comporte en interne et pourquoi est-il nécessaire d’initialiser une valeur de «graine» pour la fonction rand.

Autrement dit – comment la fonction rand utilise-t-elle la valeur initiale pour générer des nombres aléatoires?

Les détails exacts de l’implémentation dépendent des implémenteurs. Mais la mise en oeuvre GNU (glibc) implémente rand () comme ceci: http://sourceware.org/git/?p=glibc.git;a=blob;f=stdlib/random_r.c;hb=glibc-2.15#l361

Le commentaire l’explique assez bien.

/* If we are using the sortingvial TYPE_0 RNG, just do the old linear congruential bit. Otherwise, we do our fancy sortingnomial stuff, which is the same in all the other cases due to all the global variables that have been set up. The basic operation is to add the number at the rear pointer into the one at the front pointer. Then both pointers are advanced to the next location cyclically in the table. The value returned is the sum generated, reduced to 31 bits by throwing away the "least random" low bit. Note: The code takes advantage of the fact that both the front and rear pointers can't wrap on the same call by not testing the rear pointer if the front one has wrapped. Returns a 31-bit random number. */ 

En ce qui concerne votre question, pourquoi vous avez toujours besoin d’ une valeur de départ: Il n’ya pas de nombres vraiment aléatoires en informatique. Les ordinateurs sont (en théorie du calcul) des machines complètement déterministes. Ils ne peuvent effectuer aucune opération dont le résultat dépend du hasard.

Il n’y a que des générateurs de nombres pseudo-aléatoires qui génèrent des stream de nombres d’apparence aléatoire, mais ils restnt les résultats de calculs déterministes. C’est pourquoi vous avez besoin d’une valeur de départ: chaque départ donne une séquence de nombres différente. Lorsque vous utilisez la même graine, vous obtenez la même séquence de nombres pseudo-aléatoires.

Le comportement selon lequel un générateur de ressources aléatoires retourne toujours la même séquence lors de l’obtention de la même graine peut être exploité: la simulation spatiale classique Elite , par exemple, était capable de stocker un univers immense avec des centaines de planètes dans un seul entier. Comment a-t-il fait ça? L’univers entier a été généré de manière aléatoire. Toutes les données nécessaires pour recréer l’univers étaient la valeur de départ, ce qui entraînait toujours la génération exacte du même univers.

Voir Wikipedia pour une explication plus détaillée.

Un générateur linéaire congruentiel (LCG) représente l’un des algorithmes les plus anciens et les plus connus du générateur de nombres pseudo-aléatoires. [1] La théorie qui les sous-tend est facile à comprendre, et elles sont faciles à mettre en œuvre et rapides.

Le générateur est défini par la relation de récurrence:

X_ {n + 1} = (a * X_n + c) mod m

La plupart des implémentations de rand sont des LCG , qui utilisent des mathématiques de base pour effectuer le mixage. Comme la plupart des PRNG, il faut que la graine randomisée supprime partiellement sa nature déterministe (à la fois bonne et mauvaise, dépend de son utilisation prévue) créée en utilisant des fonctions mathématiques fixes et prévisibles.

Si vous êtes intéressé par les algorithmes utilisés pour implémenter rand() dans la pratique, quels algorithmes communs sont utilisés pour les rand () de C? pourrait être d’intérêt. La mise en œuvre de glibc est disponible, ainsi que quelques liens vers des articles expliquant d’autres algorithmes.

En ce qui concerne la question de savoir pourquoi vous devez créer une graine, c’est la graine qui empêche le générateur de nombres aléatoires de produire la même séquence de nombres à chaque fois. Puisqu’il n’y a pas de véritables générateurs de nombres aléatoires, si vous appelez srand(constant) et rand() 5 fois, les 5 nombres “aléatoires” que vous récupérerez seront toujours les mêmes. Cependant, si vous spécifiez une valeur qui sera différente chaque fois que rand() est utilisé (la valeur par défaut est le temps en secondes depuis l’époque Unix, je pense), vous n’aurez pas ce problème.