Votre implémentation QuickRandom n’a pas vraiment une dissortingbution uniforme. Les fréquences sont généralement plus élevées aux valeurs les plus basses tandis que Math.random() a une dissortingbution plus uniforme. Voici un SSCCE qui montre que:

 package com.stackoverflow.q14491966; import java.util.Arrays; public class Test { public static void main(Ssortingng[] args) throws Exception { QuickRandom qr = new QuickRandom(); int[] frequencies = new int[10]; for (int i = 0; i < 100000; i++) { frequencies[(int) (qr.random() * 10)]++; } printDistribution("QR", frequencies); frequencies = new int[10]; for (int i = 0; i < 100000; i++) { frequencies[(int) (Math.random() * 10)]++; } printDistribution("MR", frequencies); } public static void printDistribution(String name, int[] frequencies) { System.out.printf("%n%s distribution |8000 |9000 |10000 |11000 |12000%n", name); for (int i = 0; i < 10; i++) { char[] bar = " ".toCharArray(); // 50 chars. Arrays.fill(bar, 0, Math.max(0, Math.min(50, frequencies[i] / 100 - 80)), '#'); System.out.printf("0.%dxxx: %6d :%s%n", i, frequencies[i], new String(bar)); } } } 

Le résultat moyen ressemble à ceci:

 QR dissortingbution |8000 |9000 |10000 |11000 |12000 0.0xxx: 11376 :################################# 0.1xxx: 11178 :############################### 0.2xxx: 11312 :################################# 0.3xxx: 10809 :############################ 0.4xxx: 10242 :###################### 0.5xxx: 8860 :######## 0.6xxx: 9004 :########## 0.7xxx: 8987 :######### 0.8xxx: 9075 :########## 0.9xxx: 9157 :########### MR dissortingbution |8000 |9000 |10000 |11000 |12000 0.0xxx: 10097 :#################### 0.1xxx: 9901 :################### 0.2xxx: 10018 :#################### 0.3xxx: 9956 :################### 0.4xxx: 9974 :################### 0.5xxx: 10007 :#################### 0.6xxx: 10136 :##################### 0.7xxx: 9937 :################### 0.8xxx: 10029 :#################### 0.9xxx: 9945 :################### 

Si vous répétez le test, vous verrez que la dissortingbution QR varie considérablement en fonction des valeurs initiales, tandis que la dissortingbution MR est stable. Parfois, il atteint la dissortingbution uniforme souhaitée, mais plus que souvent, il ne le fait pas. Voici l'un des exemples les plus extrêmes, même au-delà des limites du graphique:

 QR dissortingbution |8000 |9000 |10000 |11000 |12000 0.0xxx: 41788 :################################################## 0.1xxx: 17495 :################################################## 0.2xxx: 10285 :###################### 0.3xxx: 7273 : 0.4xxx: 5643 : 0.5xxx: 4608 : 0.6xxx: 3907 : 0.7xxx: 3350 : 0.8xxx: 2999 : 0.9xxx: 2652 : 

Ce que vous décrivez est un type de générateur aléatoire appelé générateur congruentiel linéaire . Le générateur fonctionne comme suit:

• Commencez avec une valeur de départ et un multiplicateur.
• Pour générer un nombre aléatoire:
  • Multipliez la graine par le multiplicateur.
  • Définissez la graine égale à cette valeur.
  • Renvoie cette valeur.

Ce générateur possède de nombreuses propriétés intéressantes, mais pose de gros problèmes en tant que source aléatoire. L’article de Wikipedia lié ci-dessus décrit certaines des forces et des faiblesses. En bref, si vous avez besoin de bonnes valeurs aléatoires, ce n’est probablement pas une très bonne approche.

J’espère que cela t’aides!

Votre fonction de nombre aléatoire est médiocre car son état interne est trop faible – le nombre fourni par la fonction à une étape donnée dépend entièrement du numéro précédent. Par exemple, si nous supposons que magicNumber est 2 (à titre d’exemple), alors la séquence:

 0.10 -> 0.20 

est fortement reflété par des séquences similaires:

 0.09 -> 0.18 0.11 -> 0.22 

Dans de nombreux cas, cela générera des corrélations notables dans votre jeu. Par exemple, si vous appelez plusieurs fois votre fonction pour générer des coordonnées X et Y pour des objects, les objects formeront des motifs diagonaux clairs.

À moins d’avoir de bonnes raisons de croire que le générateur de nombres aléatoires ralentit votre application (et cela est TRÈS improbable), il n’y a aucune raison d’essayer d’écrire le vôtre.

Le vrai problème est que son histogramme de sortie dépend beaucoup de la graine initiale – la plupart du temps, la sortie sera presque uniforme, mais la plupart du temps, la sortie sera nettement non uniforme.

Inspiré par cet article sur la qualité de la fonction rand() de php , j’ai créé des images masortingcielles aléatoires à l’aide de QuickRandom et System.Random . Cette exécution montre comment parfois la graine peut avoir un effet négatif (dans ce cas en privilégiant des nombres inférieurs) où comme System.Random est assez uniforme.

QuickRandom

System.Random

Encore pire

Si nous initialisons QuickRandom tant que new QuickRandom(0.01, 1.03) nous obtenons cette image:

Le code

 using System; using System.Drawing; using System.Drawing.Imaging; namespace QuickRandomTest { public class QuickRandom { private double prevNum; private readonly double magicNumber; private static readonly Random rand = new Random(); public QuickRandom(double seed1, double seed2) { if (seed1 >= 1 || seed1 < 0) throw new ArgumentException("Seed 1 must be >= 0 and < 1, not " + seed1); prevNum = seed1; if (seed2 <= 1 || seed2 > 10) throw new ArgumentException("Seed 2 must be > 1 and <= 10, not " + seed2); magicNumber = seed2; } public QuickRandom() : this(rand.NextDouble(), rand.NextDouble() * 10) { } public double Random() { return prevNum = (prevNum * magicNumber) % 1; } } class Program { static void Main(string[] args) { var rand = new Random(); var qrand = new QuickRandom(); int w = 600; int h = 600; CreateMatrix(w, h, rand.NextDouble).Save("System.Random.png", ImageFormat.Png); CreateMatrix(w, h, qrand.Random).Save("QuickRandom.png", ImageFormat.Png); } private static Image CreateMatrix(int width, int height, Func f) { var bitmap = new Bitmap(width, height); for (int y = 0; y < height; y++) { for (int x = 0; x < width; x++) { var c = (int) (f()*255); bitmap.SetPixel(x, y, Color.FromArgb(c,c,c)); } } return bitmap; } } } 

Un problème avec votre générateur de nombres aléatoires est qu’il n’ya pas «d’état caché» – si je connais le nombre aléatoire que vous avez renvoyé lors du dernier appel, je connais tous les nombres aléatoires que vous enverrez jusqu’à la fin des temps. possible prochain résultat, et ainsi de suite.

Une autre chose à considérer est la «période» de votre générateur de nombres aléatoires. Evidemment, avec une taille à états finis égale à la portion de mantisse d’un double, elle ne pourra renvoyer que 2 ^ 52 valeurs au maximum avant le bouclage. Mais c’est dans le meilleur des cas – pouvez-vous prouver qu’il n’y a pas de boucles de la période 1, 2, 3, 4 …? Si tel est le cas, votre GNA aura un comportement affreux et dégénéré dans ces cas.

De plus, votre génération de nombres aléatoires aura-t-elle une dissortingbution uniforme pour tous les points de départ? Si ce n’est pas le cas, votre GNA sera biaisé – ou pire, faussé de différentes manières en fonction de la graine de départ.

Si vous pouvez répondre à toutes ces questions, génial. Si vous ne pouvez pas, alors vous savez pourquoi la plupart des gens ne réinventent pas la roue et utilisent un générateur de nombres aléatoires éprouvé;)

(En passant, un bon adage est le suivant: le code le plus rapide est le code qui ne s’exécute pas. Vous pourriez faire le plus aléatoire possible au monde, mais ce n’est pas bon si ce n’est pas très aléatoire)

Un test commun que j’ai toujours fait lors du développement de PRNG était de:

1. Convertir la sortie en valeurs de caractère
2. Ecrire des caractères dans un fichier
3. Compresser le fichier

Cela me permet de parcourir rapidement des idées qui étaient «assez bonnes» pour les séquences d’environ 1 à 20 mégaoctets. Il a également donné une meilleure image de haut en bas que de l’inspecter simplement à l’œil nu, tout PRNG «assez bon» avec un demi-mot d’état pouvant rapidement dépasser vos yeux pour voir le sharepoint cycle.

Si j’étais vraiment pointilleux, je pourrais prendre les bons algorithmes et exécuter les tests DIEHARD / NIST sur eux, pour avoir un meilleur aperçu, puis revenir en arrière et en peaufiner un peu plus.

L’avantage du test de compression, par opposition à une parsing de fréquence, est que, sortingvialement, il est facile de construire une bonne dissortingbution: produisez simplement un bloc de 256 longueurs contenant tous les caractères de 0 à 255, et faites-le 100 000 fois. Mais cette séquence a un cycle de longueur 256.

Une dissortingbution asymésortingque, même avec une petite marge, devrait être captée par un algorithme de compression, en particulier si vous lui donnez suffisamment (disons 1 Mo) de la séquence avec laquelle vous voulez travailler. Si certains caractères, ou bigrammes, ou n-grammes apparaissent plus fréquemment, un algorithme de compression peut encoder cette dissortingbution en codes qui favorisent les occurrences fréquentes avec des mots de code plus courts, et vous obtenez un delta de compression.

Comme la plupart des algorithmes de compression sont rapides et ne requièrent aucune implémentation (comme les systèmes d’exploitation les traînent), le test de compression est très utile pour évaluer rapidement la réussite / échec d’un PRNG en cours de développement.

Bonne chance dans vos expériences!

Oh, j’ai effectué ce test sur le rng que vous avez ci-dessus, en utilisant le petit mod suivant de votre code:

 import java.io.*; public class QuickRandom { private double prevNum; private double magicNumber; public QuickRandom(double seed1, double seed2) { if (seed1 >= 1 || seed1 < 0) throw new IllegalArgumentException("Seed 1 must be >= 0 and < 1, not " + seed1); prevNum = seed1; if (seed2 <= 1 || seed2 > 10) throw new IllegalArgumentException("Seed 2 must be > 1 and <= 10, not " + seed2); magicNumber = seed2; } public QuickRandom() { this(Math.random(), Math.random() * 10); } public double random() { return prevNum = (prevNum*magicNumber)%1; } public static void main(String[] args) throws Exception { QuickRandom qr = new QuickRandom(); FileOutputStream fout = new FileOutputStream("qr20M.bin"); for (int i = 0; i < 20000000; i ++) { fout.write((char)(qr.random()*256)); } } } 

Les résultats ont été:

 Cris-Mac-Book-2:rt cris$ zip -9 qr20M.zip qr20M.bin2 adding: qr20M.bin2 (deflated 16%) Cris-Mac-Book-2:rt cris$ ls -al total 104400 drwxr-xr-x 8 cris staff 272 Jan 25 05:09 . drwxr-xr-x+ 48 cris staff 1632 Jan 25 05:04 .. -rw-r--r-- 1 cris staff 1243 Jan 25 04:54 QuickRandom.class -rw-r--r-- 1 cris staff 883 Jan 25 05:04 QuickRandom.java -rw-r--r-- 1 cris staff 16717260 Jan 25 04:55 qr20M.bin.gz -rw-r--r-- 1 cris staff 20000000 Jan 25 05:07 qr20M.bin2 -rw-r--r-- 1 cris staff 16717402 Jan 25 05:09 qr20M.zip 

Je considérerais un bon PRNG si le fichier de sortie ne peut pas être compressé du tout. Pour être honnête, je ne pensais pas que votre PRNG irait si bien, seulement 16% sur 20 Mega est assez impressionnant pour une construction aussi simple. Mais je le considère toujours comme un échec.

Le générateur aléatoire le plus rapide que vous puissiez implémenter est le suivant:

XD, blague à part, en plus de tout ce qui est dit ici, je voudrais consortingbuer en citant que tester des séquences aléatoires “est une tâche difficile” [1], et il y a plusieurs tests qui vérifient certaines propriétés de nombres pseudo-aléatoires, vous pouvez trouver un beaucoup d’entre eux ici: http://www.random.org/analysis/#2005

Une méthode simple pour évaluer la “qualité” des générateurs aléatoires est l’ancien test du chi carré.

 static double chisquare(int numberCount, int maxRandomNumber) { long[] f = new long[maxRandomNumber]; for (long i = 0; i < numberCount; i++) { f[randomint(maxRandomNumber)]++; } long t = 0; for (int i = 0; i < maxRandomNumber; i++) { t += f[i] * f[i]; } return (((double) maxRandomNumber * t) / numberCount) - (double) (numberCount); } 

Citant [1]

L'idée du test χ² est de vérifier si les nombres produits sont étalés ou non. Si nous générons N nombres positifs inférieurs à r , nous nous attendons à obtenir environ N / r numéros de chaque valeur. Mais - et c'est l'essence de la matière - les fréquences d'occurrence de toutes les valeurs ne devraient pas être exactement les mêmes: cela ne serait pas aléatoire!

Nous calculons simplement la sum des carrés des fréquences d'occurrence de chaque valeur, mis à l'échelle par la fréquence attendue, puis soustrayons la taille de la séquence. Ce nombre, la "statistique χ²", peut être exprimé mathématiquement comme suit:

Si la statistique χ² est proche de r , alors les nombres sont aléatoires; si c'est trop loin, alors ils ne le sont pas. Les notions de "fermer" et de "loin" peuvent être définies avec plus de précision: il existe des tableaux qui indiquent exactement comment établir un lien entre la statistique et les propriétés de séquences aléatoires. Pour le test simple que nous effectuons, la statistique doit être comprise entre 2

En utilisant cette théorie et le code suivant:

 abstract class RandomFunction { public abstract int randomint(int range); } public class test { static QuickRandom qr = new QuickRandom(); static double chisquare(int numberCount, int maxRandomNumber, RandomFunction function) { long[] f = new long[maxRandomNumber]; for (long i = 0; i < numberCount; i++) { f[function.randomint(maxRandomNumber)]++; } long t = 0; for (int i = 0; i < maxRandomNumber; i++) { t += f[i] * f[i]; } return (((double) maxRandomNumber * t) / numberCount) - (double) (numberCount); } public static void main(String[] args) { final int ITERATION_COUNT = 1000; final int N = 5000000; final int R = 100000; double total = 0.0; RandomFunction qrRandomInt = new RandomFunction() { @Override public int randomint(int range) { return (int) (qr.random() * range); } }; for (int i = 0; i < ITERATION_COUNT; i++) { total += chisquare(N, R, qrRandomInt); } System.out.printf("Ave Chi2 for QR: %f \n", total / ITERATION_COUNT); total = 0.0; RandomFunction mathRandomInt = new RandomFunction() { @Override public int randomint(int range) { return (int) (Math.random() * range); } }; for (int i = 0; i < ITERATION_COUNT; i++) { total += chisquare(N, R, mathRandomInt); } System.out.printf("Ave Chi2 for Math.random: %f \n", total / ITERATION_COUNT); } } 

J'ai eu le résultat suivant:

 Ave Chi2 for QR: 108965,078640 Ave Chi2 for Math.random: 99988,629040 

Qui, pour QuickRandom, est loin de r (en dehors de r ± 2 * sqrt(r) )

Cela a été dit, QuickRandom pourrait être rapide mais (comme indiqué dans une autre réponse) n'est pas bon comme générateur de nombres aléatoires

[1] SEDGEWICK ROBERT, Algorithmes en C , Addinson Wesley Publishing Company, 1990, pages 516 à 518.

J’ai mis en place une maquette rapide de votre algorithme en JavaScript pour évaluer les résultats. Il génère 100 000 entiers aléatoires de 0 à 99 et suit l’instance de chaque entier.

La première chose que je remarque est que vous êtes plus susceptible d’obtenir un faible nombre qu’un nombre élevé. Vous voyez ceci le plus lorsque la seed1 est haute et que la seed2 est basse. Dans quelques cas, j’ai seulement 3 chiffres.

Au mieux, votre algorithme doit être affiné.

Si la fonction Math.Random() appelle le système d’exploitation pour obtenir l’heure du jour, vous ne pouvez pas le comparer à votre fonction. Votre fonction est un PRNG, alors que cette fonction recherche des nombres aléatoires réels. Pommes et oranges

Votre PRNG peut être rapide, mais il ne dispose pas d’assez d’informations sur l’état pour atteindre une longue période avant de se répéter (et sa logique n’est pas assez sophistiquée pour atteindre les périodes possibles avec autant d’informations d’état).

La période est la durée de la séquence avant que votre PRNG commence à se répéter. Cela se produit dès que la machine PRNG effectue une transition d’état vers un état identique à un état passé. De là, il va répéter les transitions qui ont commencé dans cet état. Un autre problème avec les PRNG peut être un faible nombre de séquences uniques, ainsi qu’une convergence dégénérée sur une séquence particulière qui se répète. Il peut également y avoir des motifs indésirables. Par exemple, supposons qu’un PRNG semble assez aléatoire lorsque les nombres sont imprimés en décimal, mais une inspection des valeurs en binary montre que le bit 4 bascule simplement entre 0 et 1 à chaque appel. Oops!

Jetez un coup d’oeil à la Mersenne Twister et à d’autres algorithmes. Il existe des moyens de trouver un équilibre entre la durée de la période et les cycles de la CPU. Une approche de base (utilisée dans le Mersenne Twister) consiste à contourner le vecteur d’état. C’est-à-dire que lorsqu’un nombre est généré, il n’est pas basé sur l’état complet, mais sur quelques mots du tableau d’états soumis à des opérations sur quelques bits. Mais à chaque étape, l’algorithme se déplace également dans le tableau, brouillant le contenu un peu à la fois.

Il existe de nombreux générateurs de nombres pseudo-aléatoires. Par exemple le ranarray de Knuth, le twister de Mersenne , ou recherchez des générateurs de LFSR. Les “algorithmes Seminumerical” monumentaux de Knuth parsingnt la zone et proposent des générateurs linéaires congruents (simples à mettre en œuvre, rapides).

Mais je suggère que vous vous en Math.random à java.util.Random ou Math.random , ils sont rapides et au moins OK pour une utilisation occasionnelle (c.-à-jeux et autres). Si vous êtes juste paranoïaque sur la dissortingbution (un programme de Monte Carlo ou un algorithme génétique), vérifiez leur implémentation (la source est disponible quelque part), et dissortingbuez-les avec un nombre vraiment aléatoire, de votre système d’exploitation ou de random.org . Si cela est nécessaire pour certaines applications où la sécurité est essentielle, vous devrez vous creuser. Et comme dans ce cas, vous ne devriez pas croire ce que des carrés colorés avec des bits manquants jaillissent ici, je vais me taire maintenant.

Il est très improbable que les performances de génération de nombres aléatoires soient un problème pour tous les cas d’utilisation que vous avez rencontrés à moins d’accéder à une seule instance Random partir de plusieurs threads (car Random est synchronized ).

Cependant, si c’est vraiment le cas et que vous avez besoin de beaucoup de nombres aléatoires rapidement, votre solution est beaucoup trop peu fiable. Parfois, cela donne de bons résultats, parfois cela donne des résultats horribles (basés sur les parameters initiaux).

Si vous voulez les mêmes nombres que la classe Random vous donne, seulement plus rapidement, vous pourriez vous débarrasser de la synchronisation:

 public class QuickRandom { private long seed; private static final long MULTIPLIER = 0x5DEECE66DL; private static final long ADDEND = 0xBL; private static final long MASK = (1L << 48) - 1; public QuickRandom() { this((8682522807148012L * 181783497276652981L) ^ System.nanoTime()); } public QuickRandom(long seed) { this.seed = (seed ^ MULTIPLIER) & MASK; } public double nextDouble() { return (((long)(next(26)) << 27) + next(27)) / (double)(1L << 53); } private int next(int bits) { seed = (seed * MULTIPLIER + ADDEND) & MASK; return (int)(seed >>> (48 - bits)); } } 

J’ai simplement pris le code java.util.Random et supprimé la synchronisation, ce qui se traduit par deux fois plus de performances que l’original sur ma machine virtuelle Java HotSpot JVM 7u9. Il est encore plus lent que votre QuickRandom , mais il donne des résultats beaucoup plus cohérents. Pour être précis, pour les mêmes valeurs de départ et applications à thread unique, cela donne les mêmes nombres pseudo-aléatoires que la classe Random originale.

_{Ce code est basé sur le fichier java.util.Random dans OpenJDK 7u sous licence GNU GPL v2 .}

EDIT 10 mois plus tard:

Je viens de découvrir que vous n’avez même pas besoin d’utiliser mon code ci-dessus pour obtenir une instance Random non synchronisée. Il y en a un dans le JDK aussi!

Regardez la classe ThreadLocalRandom Java 7. Le code à l’intérieur est presque identique à mon code ci-dessus. La classe est simplement une version Random isolée au niveau du thread local permettant de générer rapidement des nombres aléatoires. Le seul inconvénient auquel je peux penser est que vous ne pouvez pas définir sa seed manuellement.

Exemple d’utilisation:

 Random random = ThreadLocalRandom.current(); 

«Aléatoire» ne se limite pas à obtenir des chiffres… ce que vous avez est pseudo-aléatoire

Si pseudo-aléatoire est assez bon pour vos besoins, alors bien sûr, c’est beaucoup plus rapide (et Xits + Bitshift sera plus rapide que ce que vous avez)

Rolf

Modifier:

OK, after being too hasty in this answer, let me answer the real reason why your code is faster:

From the JavaDoc for Math.Random()

This method is properly synchronized to allow correct use by more than one thread. However, if many threads need to generate pseudorandom numbers at a great rate, it may reduce contention for each thread to have its own pseudorandom-number generator.

This is likely why your code is faster.

java.util.Random is not much different, a basic LCG described by Knuth. However it has main 2 main advantages/differences:

• thread safe – each update is a CAS which is more expensive than a simple write and needs a branch (even if perfectly predicted single threaded). Depending on the CPU it could be significant difference.
• undisclosed internal state – this is very important for anything non-sortingvial. You wish the random numbers not to be predictable.

Below it’s the main routine generating ‘random’ integers in java.util.Random.

 protected int next(int bits) { long oldseed, nextseed; AtomicLong seed = this.seed; do { oldseed = seed.get(); nextseed = (oldseed * multiplier + addend) & mask; } while (!seed.compareAndSet(oldseed, nextseed)); return (int)(nextseed >>> (48 - bits)); } 

If you remove the AtomicLong and the undisclosed sate (ie using all bits of the long ), you’d get more performance than the double multiplication/modulo.

Last note: Math.random should not be used for anything but simple tests, it’s prone to contention and if you have even a couple of threads calling it concurrently the performance degrades. One little known historical feature of it is the introduction of CAS in java – to beat an infamous benchmark (first by IBM via insortingnsics and then Sun made “CAS from Java”)

This is the random function I use for my games. It’s pretty fast, and has good (enough) dissortingbution.

 public class FastRandom { public static int randSeed; public static final int random() { // this makes a 'nod' to being potentially called from multiple threads int seed = randSeed; seed *= 1103515245; seed += 12345; randSeed = seed; return seed; } public static final int random(int range) { return ((random()>>>15) * range) >>> 17; } public static final boolean randomBoolean() { return random() > 0; } public static final float randomFloat() { return (random()>>>8) * (1.f/(1<<24)); } public static final double randomDouble() { return (random()>>>8) * (1.0/(1<<24)); } }