Discussion :

[zoonel]

Bonjour,
Voila le problème, à partir d'un générateur de nombre aléatoire qui produit un réel compris entre 0 et 1 (1 non compris, cad [0,1) ) je voudrais pouvoir générer un nombre compris entre 0 et x (x entier > 1).
Or en lisant vite fait un article sur wikipédia (http://en.wikipedia.org/wiki/Fisher-Yates_shuffle dans la section modulo bias), je lis que multiplier le nombre compris entre 0 et 1 par x et garder la partie entière provoque un biais. En anglais :

The problem here is that random floating-point numbers, however carefully generated, always have only finite precision. This means that there are only a finite number of possible floating point values in any given range, and if the range is divided into a number of segments that doesn't divide this number evenly, some segments will end up with more possible values than others. While the resulting bias will not show the same systematic downward trend as in the previous case, it will still be there.

En gros ca dit que le nombre généré a une précision finie et qu'entre le range [0,1) il n'y a qu'un nombre fini de réel représenté.Et que donc si on divise l' intervalle [0,1) en un nombre fini de segment (soit x ce nombre), alors il y a un probleme si x ne divise pas le nombre de réels effectivement représenté dans [0,1), certains intevalles contiendront en effet plus de nombres que d'autres. Bref si j'ai bien compris certains intervalles seront plus probables que d'autres, et donc au final certaines valeurs seront générées plus que d'autres d'où le biais :/

J'aimerais donc connaître un moyen afin de générer un nombre entier entre 0 et X sans biais à partir d'un nombre aléatoire compris entre 0 compris et 1 non-compris. Le générateur utilisé est le mersenne twister.
En fait si y'en a qui connaîssent bien le sujet, toutes les infos sont bienvenues

[Zavonen]

Est-il ABSOLUMENT indispensable de générer l'entier aléatoire à partir d'un float ?
En général on fait le contraire, on génère d'abord une suite d'entiers pseudo-aléatoire (par exemple par les congruences de Lehmer) puis à partir de là, des flottants (pseudo) aléatoires.

[Jean-Marc.Bourguet]

En utilisant le mersenne twister, j'ai beaucoup de mal a comprendre pourquoi tu passes par l'intermediaire des flottants. En partant d'entiers, pour eliminer tous les biais dont j'ai connaissance, voir la FAQ C ou plus detaille un petit article que j'ai ecrit sur le sujet.

[zoonel]

Merci pour ces réponses

En fait c'est vrai que passer par l'entier généré est plus simple, comme j'avais dans la tête la multiplication du réel [0,1) par un entier je suis resté bloqué dessus.
En plus si le site du Mersenne Twister n'avais pas été down y'a qques heures j'aurais eu la solution de suite

Mostly enough to use [0,1)-version, multiply the output by N, then take floor (round-off).
(Caution: do not use [0,1]-version. Appearance of 1.0 may cause the output of N. This occurs roughly once in 4.2 billion times).
In the rare case that the rounding-off error becomes a problem, obtain minimum integer n such that N<=2^n, generate integer random numbers, take the most significant n bits, and discard those more than or equal to N.

Solution que j'ai vue sur un site pour jouer au poker : http://www.bugsysclub.com/club/about/integrity.htm

[edfed]

generer de l'aleatoire:
tout un roman.

il faut une racine pour le generateur.
cette racine sert pour le feedback, elle doit etre la plus grande possible pour avoir la periode la plus grande possible. et selon le type d'algo, elle doit etre un nombre premier.

ensuite, des instructions purement logiques, telles que la rotation de bits, combinée avec un peu de xor, un echange de contenu, encore un peu de xor et de rotations, et un chouia d'additions donne de bon generateur pseudo_aleatoire, sans utiliser le moindre flottant.

il faut ensuite le voir, pour constater que c'est visiblement aleatoire.
un mauvais rnd, ça se voit, ça fait des lignes, des zones jamais ecrites, des zones tout le temps ecrites, et ça reboucle vite.

en asm, on apprend qu'il faut eviter de couper les etapes, et surtout, la representation de [0 à 1) convient parfaitement aux nombres entiers, car leurs plage peut etre vue comme un nombre a virgule fixe, dont la valeur max correspond justement à 1) et la valeur min est un ZERO pur.

[PRomu@ld]

En quoi ça répond au PO ? Et qu'est-ce que ça apporte de plus que ce qui a déjà été dit ?

[droggo]

Fie,

+1 sur PRomu@ld

A quoi j'ajoute:

...
il faut une racine pour le generateur.
cette racine sert pour le feedback, elle doit etre la plus grande possible pour avoir la periode la plus grande possible. et selon le type d'algo, elle doit etre un nombre premier...

Je crois que tu confonds les termes.
La période ne dépend pas de la racine, qui n'est là que pour initialiser le générateur. Cette racine n'a rien à voir non plus avec les nombres premiers.

[edfed]

là est une reponce, un terme nouveau dans la discution qui à tout a voir:

comme un nombre à virgule fixe

et toi tu joue sur les mots.
la racine est utilisée comme base à chaque iterations, et si on veu une periode la plus grande possible, il faut que la racine soit la plus grande possible, et parfois, il faut que se soit un nombre premier pour que la periode soit reelement grande.

voilà...
si tu preferes, pour faire de l'aleatoire, il existe des milliers de solutions.

[Zavonen]

Allez voir chez les pros:
http://fr.wikipedia.org/wiki/G%C3%A9...l%C3%A9atoires

[edfed]

et...

[Jean-Marc.Bourguet]

et...

On y trouve pas le mot racine par exemple. Le mot graine s'y trouve et si ta racine est leur graine, sa valeur n'a une influence sur la periode d'un generateur pseudo-aleatoire que pour les plus mauvais d'entre eux (ou pour un mauvais choix de parametres pour certains qui sont plus acceptables avec de meilleurs parametres).