Discussion :

[gege2061]

Bonjour,
je travail sur les générateurs de nombres pseudo-aléatoires et j'ai lu que le générateur Berkeley UNIX génére des nombres dont les bits de poids faibles n'étaient pas fiables. J'aurai donc voulu savoir combien de bits il fallait supprimer pour obtenir quelque chose de correct (c'est dans un but éducatif donc je ne cherche pas la perfection).

Merci.

[DaZumba]

L'idee n'est pas de les supprimer, mais de ne pas leur donner d'importance.
En gros, et pour utiliser la notation C, pour avoir un nombre aleatoire compris entre 0 et N-1 il ne faut pas faire:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
 
rand() % N

mais

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
 
(int)((double)rand() / ((double)RAND_MAX + 1) * N)

Pour une discussion avancee de la bonne utilisation des generateurs lineaires congruentiels (tel que celui utilise par la librairie standard C), voir les Numerical Recipes, chapitre 7, section 1.

[gege2061]

L'idee n'est pas de les supprimer, mais de ne pas leur donner d'importance.

Le problème c'est que je part de ça :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

Xn+1 = ( 1103515245 * Xn + 12345 ) % 2147483647

Donc je recode les fonctions de la bibliothèque standard du C rand et srand. Comme les bits de poids faibles ne son pas réellement aléatoires à part les suppimer je peux en faire quoi ?

Pour une discussion avancee de la bonne utilisation des generateurs lineaires congruentiels (tel que celui utilise par la librairie standard C), voir les Numerical Recipes, chapitre 7, section 1.

Je l'ai lu mais ce que j'ai compris ne m'a pas plus avancé (le reste j'ai pas compris )

[DaZumba]

Le problème c'est que je part de ça :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

Xn+1 = ( 1103515245 * Xn + 12345 ) % 2147483647

Donc je recode les fonctions de la bibliothèque standard du C rand et srand. Comme les bites de poids faibles ne son pas réellement aléatoires à part les suppimer je peux en faire quoi?

Ah, je n'avais pas compris que tu te place comme créateur du générateur, et pas comme utilisateur. Le fait que les bits de poids faibles ne sont pas très aléatoires est un défaut des algorithmes linéaires congruentiels. En temps que créateur de la bibliothèque, tu ne fais rien, mais tu avertis l'utilisateur des limites du générateur, et tu conseilles la bonne utilisation. Sinon, tu peux implémenter des générateurs plus sophistiqués (cf. les sections suivantes du paragraphe 7 - c'est compréhensible si tu as un peu de maths derrière toi).

[Matthieu Brucher]

Les générateur aléatoires congruentiels génèrent un hasard faible, c'est pas génial, en fait. Avec cette formule, tu ne peux pas aller vers un hasard fort - qui serait obtenu par un bruit physique -. Il y a d'autres techniques pour diminuer la corrélation de ton bruit, à l'aide d'autres formules.

[Nemerle]

Quitte à réimplémenter un random générator, pourquoi ne pas choisir un Mersenne Twister?

C'est ce que j'ai implémenté dans ma boite.

[gege2061]

Quitte à réimplémenter un random générator, pourquoi ne pas choisir un Mersenne Twister?

Effectivement il semble assez bon comme générateur

Mais comme je l'ai dit plus haut c'est à but éducatif donc je ne vais pas présenter tous les types de générateurs possible ! Je suis parti sur les générateurs de type :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

Xn+1 = ( a * xn + b ) % c

Pour montrer que ce n'est pas si simple (si les valeurs de a, b et c ne sont pas choisies avec précaution c'est la catastrophe !).

[DrTopos]

Il y a un test simple qu'on peut faire pour trouver le meilleur générateur pseudo-aléatoire parmi plusieurs.

Utilise chaque générateur pour fabriquer un gros fichier d'une taille donnée (la même taille pour tous les générateurs), puis comprime ces fichiers avec les outils de compression habituels. Les fichiers qui sont les plus difficile à comprimer sont ceux qui sont fabriqués par les meilleurs générateurs. Ce sont ceux qui donnent les séquences les moins biaisées.

Personnellement, j'aime bien le générateur de RC4 qui est de bonne qualité et facile à coder.

[Matthieu Brucher]

gege > Ce genre de chose est expliqué sur Wikipedia...
Le test de DrTopos est assez simple à mettre en place et bien discriminant, ensuite, tu as des tests de corrélation à mettre en place si tu veux aller plus loin, ...

[gege2061]

gege > Ce genre de chose est expliqué sur Wikipedia...

Quoi dont ?

Le test de DrTopos est assez simple à mettre en place et bien discriminant, ensuite, tu as des tests de corrélation à mettre en place si tu veux aller plus loin, ...

Effectivement c'est une bonne idée !

[Matthieu Brucher]

Les générateurs aléatoires par congruence.