Algorithmes de génération de nombres pseudo-aléatoires

12

Quels algorithmes sont utilisés dans les générateurs de nombres aléatoires modernes et de bonne qualité?

algorithms random-variable random-generation Mehper C. Palavuzlar
la source
1
"Variable aléatoire" redéfini à "variable aléatoire" pour la cohérence avec des questions similaires.
whuber

Réponses:

10

Dans R, le paramètre par défaut pour la génération de nombres aléatoires est:

  1. Pour U (0,1), utilisez l'algorithme de Mersenne-Twister
  2. Pour les nombres guassiens, utilisez l'inversion numérique de la fonction de distribution normale standard.

Vous pouvez facilement vérifier cela, à savoir.

> RNGkind()
[1] "Mersenne-Twister" "Inversion"

Il est possible de remplacer le générateur par défaut par d'autres PRNG, tels que Super-Duper, Wichmann-Hill, Marsaglia-Multicarry ou même un PRNG fourni par l'utilisateur. Voir le? RNGkind pour plus de détails. Je n'ai jamais eu besoin de changer le PRNG par défaut.

La bibliothèque C GSL utilise également le Mersenne-Twister par défaut.

csgillespie
la source
Êtes-vous sûr de votre deuxième point, générer des variables aléatoires normales en inversant le CDF? L'inverse du CDF normal est une fonction assez coûteuse à évaluer. J'imagine que la méthode de Box-Muller serait plus rapide. Plus rapide encore serait la méthode en ziggourat de Marsaglia pour générer des normales.
John D. Cook
Je trouve également cela suspect. Ziggurat de Marsaglia est la valeur par défaut dans Matlab, et je ne peux pas imaginer que Matlab soit meilleur que R dans le domaine de la génération de nombres aléatoires.
shabbychef
@John En effet, la méthode polaire est disponible en R, voir le package setRNG.
chl
3

Le Xorshift PNG conçu par George Marsaglia. Sa période (2 ^ 128-1) est beaucoup plus courte que celle de Mersenne-Twister mais l'algorithme est très simple à mettre en œuvre et se prête à la parallélisation. Fonctionne bien sur les architectures à plusieurs cœurs telles que les puces DSP et Tesla de Nvidia.

brotchie
la source
Serait-ce bon pour l'implémentation sur des GPU? Lien vers les détails, les références?
DarenW
2
Thomas, Howes, Luk - 2009 - Une comparaison des processeurs, des GPU, des FPGA et des matrices de processeurs massivement parallèles pour la génération de nombres aléatoires. doi.acm.org/10.1145/1508128.1508139 . Discussion + benchmarks d'un ensemble de fichiers PNG exécutés sur CPU, GPU, FPGA et matrices de processeurs massivement parallèles.
brotchie
Peut-être aussi le RNG de L'Ecuyer avec plusieurs flux ( j.mp/bzJSlm )?
chl
3

À http://prng.di.unimi.it/ vous pouvez trouver une fusillade de plusieurs générateurs de nombres aléatoires testés à l'aide de TestU01, la suite de tests moderne pour les générateurs de nombres pseudo-aléatoires qui ont remplacé diehard et dieharder. Vous pouvez choisir.

seba
la source