Quelle est la qualité de java.util.Aléatoire?
Deux questions:
Vais-je obtenir différentes séquences de nombres pour chaque graine que j'y mets?
Y a-t-il des graines" mortes"? (Ceux qui produisent des zéros ou se répètent très rapidement.)
Au fait, lequel, le cas échéant, d'autres PRNG devrais-je utiliser?
Solution: Puisque je vais utiliser le PRNG pour créer un jeu, je n'en ai pas besoin pour être sécurisé cryptographiquement. Je pars avec le Mersenne Twister, à la fois pour sa vitesse et son énorme période.
6 answers
Dans une certaine mesure, les générateurs de nombres aléatoires sont des chevaux pour les cours. La classe Aléatoire implémente un LCG avec des paramètres raisonnablement choisis. Mais il présente toujours les caractéristiques suivantes:
- période assez courte (2^48)
- les bits ne sont pas également aléatoires (voir mon article sur le caractère aléatoire des positions des bits)
- va générer seulement une petite fraction de combinaisons de valeurs (le fameux problème de "tomber dans les avions")
Si ces les choses n'ont pas d'importance pour vous, alors Random a la caractéristique de rachat d'être fourni dans le cadre du JDK. C'est assez bon pour des choses comme les jeux occasionnels (mais pas ceux où l'argent est impliqué). Il n'y a pas de graines faibles en tant que telles.
Une autre alternative qui est le XORShift generator , qui peut être implémenté en Java comme suit:
public long randomLong() {
x ^= (x << 21);
x ^= (x >>> 35);
x ^= (x << 4);
return x;
}
Pour certaines opérations très bon marché, cela a une période de 2^64-1 (zéro n'est pas autorisé), et est assez simple pour être intégré lorsque vous êtes générer des valeurs à plusieurs reprises. Différentes valeurs de décalage sont possibles: voir l'article de George Marsaglia sur les générateurs XORShift pour plus de détails. Vous pouvez considérer les bits dans les nombres générés comme étant également aléatoires. Une faiblesse principale est que de temps en temps, il va entrer dans une "ornière" où peu de bits sont définis dans le nombre, puis il faut quelques générations pour sortir de cette ornière.
, d'Autres possibilités sont:
- combiner différents générateurs (par exemple, alimenter la sortie d'un XORShift dans un LCG, puis ajouter le résultat à la sortie d'un générateur XORShift avec différents paramètres): cela permet généralement de "lisser" les faiblesses des différentes méthodes, et peut donner une période plus longue si les périodes des générateurs combinés sont soigneusement choisies
- ajoutez un "décalage" (pour donner une période plus longue): essentiellement, où un générateur transformerait normalement le dernier nombre généré, stockerait un "tampon d'historique" et transformerait, disons, le (n-1023)th.
Je je dirais éviter les générateurs qui utilisent une quantité stupide de mémoire pour vous donner une période plus longue que ce dont vous avez vraiment besoin (certains ont une période supérieure au nombre d'atomes dans l'univers you vous n'avez vraiment pas besoin de cela). Et notez que "longue période "ne signifie pas nécessairement" générateur de haute qualité " (bien que 2^48 soit encore un peu faible!).
Comme l'a dit zvrba, JavaDoc explique l'implémentation normale. La page Wikipedia sur les générateurs de nombres pseudo-aléatoirescontient une bonne quantité d'informations et mentionne le Mersenne twister, qui n'est pas réputé cryptographiquement sécurisé, mais est très rapide et a diverses implémentations en Java. (Le dernier lien a deux implémentations-il y en a d'autres disponibles, je crois.)
Si vous avez besoin d'une génération cryptographiquement sécurisée, lisez la page Wikipedia - il existe différentes options disponibles.
Au fur et à mesure que les RNG vont, l'implémentation de Sun n'est certainement pas à l'état de l'art, mais est assez bonne pour la plupart des fins. Si vous avez besoin de nombres aléatoires à des fins de cryptographie, il existe java.sécurité.SecureRandom , si vous voulez juste quelque chose de plus rapide et meilleur que java.util.au hasard, il est facile de trouver des implémentations Java du Mersenne Twister sur le net.
Ceci est décrit dans la documentation . Les générateurs congruentiels linéaires sont théoriquement bien compris et beaucoup de matériel à leur sujet est disponible dans la littérature et sur Internet. Le générateur congruentiel linéaire avec les mêmes paramètres produit toujours la même séquence périodique, et la seule chose que seed décide est où la séquence commence. Donc la réponse à votre première question est "oui, si vous générez suffisamment de nombres aléatoires."
Voir la réponse dans mon article de blog:
Http://code-o-matic.blogspot.com/2010/12/how-long-is-period-of-random-numbers.html
Random a une période maximale pour son état (une période longue, c'est-à-dire 2^64). Cela peut être directement généralisé à 2^k - investir autant de bits d'état que vous le souhaitez, et vous obtenez la période maximale. 2Mersenne Twister a en fait un très court période, comparativement (voir les commentaires dans ledit article de blog).
O Oups. Restrictions aléatoires lui-même à 48 bits, au lieu d'utiliser les 64 bits complets d'un long, donc en conséquence, sa période est 2^48 après tout, pas 2^64.
Si la qualité RNG compte vraiment pour vous, je vous recommande d'utiliser votre propre RNG. Peut-être que java.util.Le hasard est tout simplement génial, dans cette version, votre système d'exploitation, etc. C'est probablement le cas. Mais cela pourrait changer. Il est déjà arrivé qu'un écrivain de bibliothèque aggrave les choses dans une version ultérieure.
C'est très simple d'écrire le vôtre, et ensuite vous savez exactement ce qui se passe. Il ne changera pas lors de la mise à niveau, etc. Voici un générateur que vous pouvez porter vers Java en 10 minutes. Et si vous commencez à écrire dans une nouvelle langue dans une semaine, vous pouvez le porter à nouveau.
Si vous n'implémentez pas le vôtre, vous pouvez récupérer du code pour un RNG bien connu à partir d'une source réputée et l'utiliser dans vos projets. Alors personne ne changera votre générateur sous vous.
(je ne préconise pas que les gens viennent avec leurs propres algorithmes , seulement leur propre implémentation . La plupart des gens, moi y compris, n'ont aucune entreprise développant leur propre algorithme. Il est facile d'écrire un mauvais générateur que vous pensez est merveilleux. C'est pourquoi les gens doivent poser des questions comme celle-ci, se demandant à quel point le générateur de bibliothèque est bon. L'algorithme dans le générateur que j'ai référencé a été à travers la sonnerie de beaucoup d'examen par les pairs.)