/dev/blah

things i want to remember, things i want to share

Développeur Python et adepte Linux depuis 2005, Core développeur Kivy, passionné par beaucoup trop de choses.
Profil Github gpg signature bitcoin address

Entries tagged “programmation”

Pourquoi ne pas utiliser de modulo pour les fonctions aléatoires.

written by tshirtman, on 5/9/12 6:37 PM.

Beaucoup de tutoriaux de développements conseillent d’utiliser l’opération modulo (%) pour tirer un nombre entre 0 et n.

C’est une aberration, et il n’est pas difficile de faire mieux.

Le problème de la génération de nombres aléatoires en informatique est complexe, en effet, si on veut pouvoir avoir n’importe quel nombre entre 0 et n, on veut aussi (edit: en général, oui grim :))  que tous aient une probablilité égale de sortir, on appelle ça une distribution uniforme. Les gens ont passé beaucoup de temps à travailler des formules permettant à de sortir des nombres bien distribués, alors ce serait dommage de casser tout ce beau travail bêtement (en effet, la génération de nombre aléatoire est une chose trop sérieuse pour être laissée au hasard).

En C, la fonction rand() fournis un nombre entier entre 0 et RAND_MAX, certains vous conseillerons donc de faire:

	x = rand() % n

ce qui  vous fournis effectivement un nombre entre 0 et n.

Mais, car il y a un mais, il faut bien comprendre quel est le résultat de cette opération, en effet, la fonction modulo, renvoit le reste de la division euclidienne par n:

supposons N entre 0 et RAND_MAX

	0<------------------------------------N------------->RAND_MAX

Après application de % N au résultat, on obtiens la distribution suivante:

	0<------------------------------------N
	------------->RAND_MAX % N

Que constate t’on ? que les nombres entre 0 et RAND_MAX % N ont deux fois plus de chances de sortir que les nombres entre RAND_MAX % N et N. Imaginez que vous avez décidé que vos enemies seront placés sur le tableau par une telle opération, et vous avez statistiquement (bon, pas vraiment, les matheux vont me taper) deux fois plus d’entre eux dans le premier tiers du tableau que dans le reste, ça fait quand même tâche non?

Donc, la solution, si votre N n’est pas trop grand, est de multiplier rand() par N puis de diviser par RAND_MAX, vous obtiendrez bien une distribution uniforme.

	x = (rand() * N)/RAND_MAX

On multiplie notre nombre aléatoire par N pour obtenir un nombre entre 0 et RAND_MAX * N, et l’on divise par RAND_MAX, on obtiens bien un entier entre 0 et N.

Cependant si N * RAND_MAX est supérieur à MAX_INT, vous risquez l’integer overflow, et votre distribution est à nouveau toute cassée (pour la même raison, MAX_INT faisant office de modulo), on peut alors faire:

	x = int((float rand()) / RAND_MAX) * N

On convertis notre nombre aléatoire en flottant et on le divise par RAND_MAX, pour obtenir un nombre entre 0 et 1, et on multiplie par N pour obtenir un nombre entre 0 et N.

ce qui est probablement plus couteux, mais plus sécurisé.

Voilà voilà. En espérant que ça serve un peu, beaucoup de débutants semblent tomber dans ce piège, très répendus dans les tutoriaux qui leurs sont destinés.

Tip me if you like this :)

Tags

#FIXME 3G absurd ad_sense alterway aléatoire android animation anonymity atheism bach backlog bash bitcoins blog blogging boldness book books boulot bricolage bépo C canvas captcha captures carte SD censure christianity chroot CLI cli cloudwatt code colors comfort zone command line community company life conferences contest copwatch copwatchnord-idf core-devs cours ct705 culture deb debian debug deformation dehors dessin dev distribute distribution débutant déploiement développement ebooks eeepad eeepc effect ego empty en escher event firefly flappy bird flask fosdem foss fr fun game garden gdb geek culture git github goals graphics grrr gödel hack hackathon hacked hacking hooks i3 images IMAP inspirational install isync java jeu jeu video jinja2 jni keyboard keynav kivy kv lame learning lib libre life linux lol macosx magnet mail mailing-list mails maths mbsync meetings memory leak mesh meta mint mirroir MIT module motivational mouse museomix mutt nexus7 no-mouse notmuch nottoomuch offlineimap onycroit opencourseware osc packaging paris passphrase password patch pentacatyl people perte de données ping pip planning plugin positioning pr procrastination programmation progress project projet property proudhon proxy psf publisher/consumer pull-down pygame pyjnius pypi python pythonar qtile raid rapsberry pi reading recorder references release religion responsive review reviews réseau réseaux sociaux résurection salon screenshots script self service shows shutil shyness sizing solib sortie sousous!!! spam spritz stash status systeme système templating terminal texture texture coordinates Thomas Paine thread thème tiling time time management. tip tips tools transformer tutorial tv twitter typematrix typing ubuntu ubuntu-fr ultimate-smash-friends unity upload images useless usf utils value VDM video vie/mort vim virtualenv visite widget windows wm wmii work workflow workflow. zine études