Génération d'un bit aléatoire - manque d'aléa en C rand()

Question

J'utilise rand() pour générer soit 0 soit 1 ( rand() % 2 ). Je l'ensemence en utilisant l'heure actuelle ( srand(time(NULL)) ).

Après beaucoup de débogage, je me suis rendu compte que rand() ne renvoie jamais un nombre pair (impair) 16 fois de suite ou plus.

Est-ce un problème connu ? Existe-t-il un meilleur PRNG fourni avec C ?

Je fonctionne sous Windows 7 avec Visual Studio 2010.

Answer 1

Au lieu d'utiliser rand()%2 essayez. rand()>(RAND_MAX/2) . Vous ne pouvez que supposer rand() pour être uniforme sur l'intervalle [0, RAND_MAX] .

Edita: C'est ce qu'a suggéré Shahbaz dans les commentaires, ce que je n'ai remarqué qu'après avoir posté cette réponse.

Edita: ArjunShankar m'a appelé sur ma précédente formulation : "rand() est seulement spécifié pour être uniforme sur l'intervalle [0, RAND_MAX]"

De la norme C99 :

La fonction rand calcule une séquence d'entiers pseudo-aléatoires dans la plage de 0 à RAND_MAX.

Techniquement, l'uniformité (ou equidistribué ) n'est pas spécifié, mais c'est la norme de facto utilisée pour les implémentations des PRNG les plus courants (par exemple Mersenne Twister). Ceci afin de permettre à un programmeur de créer facilement un PRNG personnalisé avec une distribution non uniforme. Sans cette propriété, un programmeur est obligé d'implémenter un PRNG personnalisé à partir de zéro.

Answer 2

Je suggère d'utiliser un meilleur RNG. Vous êtes sous Windows donc vous pouvez utiliser rand_s : Il s'agit d'une extension de Microsoft qui utilise le RNG cryptographique de Windows.

Answer 3

rand() est bien connu pour sucer. random() est un peu mieux (parfois), mais drand48() et sa famille sont bien meilleurs.

Si vous avez besoin de mieux que ça, regardez du côté de mersene twister ou d'autres bibliothèques PRNG. Ou consultez /dev/random si cela peut fournir suffisamment de données pour vos besoins.

Answer 4

Vous pouvez utiliser les algorithmes de Mersenne Twister ou WELL. Le code de WELL se trouve ici (je n'ai pas assez de réputation). http://i.stack.imgur.com/q6VPL.png