Quelle est la qualité de java.util.Random?

Deux questions:

Vais-je obtenir différentes séquences de nombres pour chaque graine que je lui ai mise?

Y a-t-il des graines “mortes”? (Ceux qui produisent des zéros ou se répètent très rapidement.)

Au fait, quels autres PRGN, le cas échéant, devrais-je utiliser?

Solution: Étant donné que je vais utiliser le PRNG pour créer un jeu, je n’ai pas besoin que ce soit sécurisé sur le plan cryptographique. Je vais avec le Mersenne Twister, à la fois pour sa rapidité et son énorme période.

Dans une certaine mesure, les générateurs de nombres aléatoires sont des chevaux pour les cours. La classe Random implémente un LCG avec des parameters 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 )
  • ne générera qu’une petite fraction de combinaisons de valeurs (le fameux problème de ” tomber dans les avions “)

Si ces choses ne vous importent pas, Random a la particularité 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 est le générateur XORShift , 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 peu coûteuses, cela a une période de 2 ^ 64-1 (zéro n'est pas autorisé) et est suffisamment simple pour être inséré lorsque vous générez des valeurs à plusieurs resockets. Différentes valeurs de changement 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 des nombres générés comme étant également aléatoires. L'une des principales faiblesses réside dans le fait que, de temps en temps, il entrera dans une «ornière» où peu de bits sont définis dans le nombre, puis il faudra quelques générations pour sortir de cette ornière.

Les autres possibilités sont les suivantes:

  • combiner différents générateurs (par exemple, alimenter un LCG en sortie d'un générateur XORShift, puis append le résultat à la sortie d'un générateur XORShift avec différents parameters): cela permet généralement de "lisser" les faiblesses des différentes méthodes, et peut accorder une période plus longue si les périodes des générateurs combinés sont soigneusement choisies
  • append un "lag" (pour donner une période plus longue): essentiellement, lorsqu'un générateur transformerait normalement le dernier nombre généré, stockez un "tampon historique" et transformez, par exemple, le (n-1023) ème.

Je dirais d'éviter les générateurs qui utilisent une quantité stupide de mémoire pour vous donner une période plus longue que celle dont vous avez réellement besoin (certains ont une période supérieure au nombre d'atomes dans l'univers - vous n'en avez pas vraiment besoin). 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 le dit zvrba, JavaDoc explique la mise en œuvre normale. La page Wikipedia sur les générateurs de nombres pseudo-aléatoires contient une quantité importante d’informations et mentionne le twister de Mersenne , qui n’est pas considéré comme sécurisé sur le plan cryptographique, mais est très rapide et comporte 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 sécurisée par cryptographie, lisez la page Wikipedia – plusieurs options sont disponibles.

Au fur et à mesure que les GNA disparaissent, l’implémentation de Sun n’est certainement pas d’actualité , mais elle est suffisante dans la plupart des cas. Si vous avez besoin de nombres aléatoires à des fins de cryptographie, il y a java.security.SecureRandom , si vous voulez juste quelque chose de plus rapide et meilleur que java.util.random, il est facile de trouver des implémentations Java de Mersenne Twister sur le net.

Ceci est décrit dans la documentation . Les générateurs de congruence linéaire sont théoriquement bien compris et beaucoup de documents y sont disponibles dans la littérature et sur Internet. Générateur de congruence linéaire avec les mêmes parameters produit toujours la même séquence périodique, et la seule chose que la graine 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 sur mon 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, par exemple 2 ^ 64). Cela peut être directement généralisé à 2 ^ k – investissez autant de bits d’état que vous le souhaitez et vous obtenez la période maximale. 2Mersenne Twister a en fait une très courte période, comparativement (voir les commentaires dans ledit article).

–Oops. Aléatoire se limite à 48 bits, au lieu d’utiliser les 64 bits complets d’un long, sa période est donc 2 ^ 48 après tout, pas 2 ^ 64.

Si la qualité du GNA vous importe vraiment, je vous recommande d’utiliser votre propre GNA. Peut-être que java.util.Random est tout simplement génial, dans cette version, sur votre système d’exploitation, etc. C’est probablement le cas. Mais cela pourrait changer. C’est arrivé avant qu’un écrivain de bibliothèque ne fasse qu’empirer les choses dans une version ultérieure.

Il est très simple d’écrire le vôtre et vous savez exactement ce qui se passe. Il ne changera pas lors de la mise à niveau, etc. Voici un générateur que vous pourriez porter sur Java en 10 minutes. Et si vous commencez à écrire dans une nouvelle langue dans une semaine, vous pouvez la porter à nouveau.

Si vous n’implémentez pas le vôtre, vous pouvez récupérer le code d’un RNG bien connu auprès d’une source fiable et l’utiliser dans vos projets. Alors personne ne changera votre générateur sous vous.

(Je ne préconise pas que les gens proposent leurs propres algorithmes , mais uniquement leur propre implémentation . La plupart des gens, y compris moi-même, ne développent pas leur propre algorithme. Il est facile d’écrire un mauvais générateur besoin de poser des questions comme celle-ci, se demandant quelle est la qualité du générateur de bibliothèque.L’algorithme dans le générateur que j’ai référencé a été perçu par beaucoup de pairs.