Mersenne Twister : générer des 0 ou 1

Bonjour à tous,

Je viens de m'inscrire sur votre forum, même si ça fait plusieurs années que je viens régulièrement y faire un tour ;)

Je fais appel à vous car je ne vois pas trop comment réaliser un générateur de nombre aléatoire à partir d'une implémentation Mersenne Twister (source ici) afin qu'il ne me génère que des 0 ou des 1 (représente des "bit").

Concrètement, je dois intégrer MT dans le cadre de calculs scientifiques et mon problème consiste à remplir des tableaux avec des 0 ou des 1 (ordre de taille d'un tableau : [200][10000]). Actuellement, j'utilise un simple rand()%2 mais la période est trop petite pour nos calculs.

J'ai donc récupérer l'implémentation, mais je n'ai pas trop d'idée sur la manière de générer ces nombres entiers proprements et surtout efficacement...

Comment feriez-vous ? Merci beaucoup pour votre aide :)

Bonjour et bienvenue,

Je n'ai fait que survoler la page derrière ton lien mais il semblerait que le code en question fournisse pas mal de chose intéressantes, comme par exemple :

Code:

---

1 2 3 4 5

/* generates a random number on [0, 2^64-1]-interval */ unsigned long long genrand64_int64(void) { … }

---

Si c'est bien le cas et que la probabilité est équilibrée et uniformément répartie, donc si chaque bit des 64 du long long a une chance sur deux de tomber sur 0 ou 1, alors il te suffit d'extraire un bit au hasard. En isolant le premier, tu obtiendras directement 0 ou 1 :

Code:

---

x = genrand64_int64() & 1;

---

Sinon, tu peux utiliser les générateurs de nombres aléatoires de ton système d'exploitation. Par exemple, /dev/random sous Unix et Linux s'appuie sur l'entropie du système pour générer ses nombres, entropie induite par l'activité utilisateur (souris, clavier…), les accès disques, etc.

L'ennui est que les sources d'activité aléatoires qu'il utilise sont limitées et qu'il s'arrête quand il se tarit, jusqu'à que l'activité reprenne suffisamment pour générer de nouveaux nombres.

Bonjour Obsidian,

Merci pour ta réponse.

J'avais pensé à récupérer un seul bit de cette fonction, mais je ne trouvais pas forcément terrible de générer 64 bits pour finalement en récupérer qu'un seul, sachant que j'en ai quelques milliers à générer. Mais je crois bien que je vais finir par faire comme cela, ça me parait être le plus simple.

Concernant urandom, je n'ai pas choisi cette possibilité car nos serveurs n'ont justement que peu d'activité utilisateur (très très peu d'écriture disque, pas de clavier, pas de souris, simplement une petite connexion ssh de temps en temps,...) et j'ai un peu peur que cette entropie soit faiblarde au vu de la taille des tableaux.

Sinon tu peux utiliser Park-Miller comme PNRG, il est plus imple et rapide que Mersenne Twister mais a une moins grande periode.

Ou sinon tu as une autre version de MT : SFMT
http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/SFMT/

Salut,

Citation:

---

Envoyé par kbu6789

je ne trouvais pas forcément terrible de générer 64 bits pour finalement en récupérer qu'un seul

---

Et pourquoi ne pas récupérer les 64 bits un à un au lieu de ne récupérer que le premier ?
Ça te ferait 64 nombres par tirages.

Merci pour vos remarques ! Je n'avais pas vu pour SFMT, je vais m'orienter vers cette solution du coup :)

Citation:

---

Envoyé par grim7reaper

Et pourquoi ne pas récupérer les 64 bits un à un au lieu de ne récupérer que le premier ?
Ça te ferait 64 nombres par tirages.

---

Euh oui je me suis mal exprimé :mrgreen:, je compte bien récupérer chaque bit du lot généré ;)

Merci à tous

Bien, j'ai fini d'implémenter SFMT et l'ensemble à l'air de très bien fonctionner.
Merci encore pour vos suggestions :)