S'agit-il d'un algorithme aléatoire "suffisamment bon" ? Pourquoi ne l'utilise-t-on pas s'il est plus rapide ?

Question

J'ai créé une classe appelée QuickRandom et son rôle est de produire rapidement des nombres aléatoires. C'est très simple : il suffit de prendre l'ancienne valeur, de la multiplier par une valeur de double et prendre la partie décimale.

Voici mon QuickRandom dans son intégralité :

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;
    }

}

Et voici le code que j'ai écrit pour le tester :

public static void main(String[] args) {
        QuickRandom qr = new QuickRandom();

        /*for (int i = 0; i < 20; i ++) {
            System.out.println(qr.random());
        }*/

        //Warm up
        for (int i = 0; i < 10000000; i ++) {
            Math.random();
            qr.random();
            System.nanoTime();
        }

        long oldTime;

        oldTime = System.nanoTime();
        for (int i = 0; i < 100000000; i ++) {
            Math.random();
        }
        System.out.println(System.nanoTime() - oldTime);

        oldTime = System.nanoTime();
        for (int i = 0; i < 100000000; i ++) {
            qr.random();
        }
        System.out.println(System.nanoTime() - oldTime);
}

(Wow, je viens de remarquer que le code de test est plus long que celui de la QuickRandom code. Cela prouve simplement que c'est un algorithme si simple).

Il s'agit d'un algorithme très simple qui multiplie simplement le double précédent par un double "chiffre magique". Je l'ai mis au point assez rapidement, donc je pourrais probablement l'améliorer, mais bizarrement, il semble fonctionner correctement.

Voici un exemple de sortie des lignes commentées dans le fichier main méthode :

0.612201846732229
0.5823974655091941
0.31062451498865684
0.8324473610354004
0.5907187526770246
0.38650264675748947
0.5243464344127049
0.7812828761272188
0.12417247811074805
0.1322738256858378
0.20614642573072284
0.8797579436677381
0.022122999476108518
0.2017298328387873
0.8394849894162446
0.6548917685640614
0.971667953190428
0.8602096647696964
0.8438709031160894
0.694884972852229

Hm. Plutôt aléatoire. En fait, ça pourrait fonctionner pour un générateur de nombres aléatoires dans un jeu.

Voici un exemple de sortie de la partie non commentée :

5456313909
1427223941

Wow ! Il est presque 4 fois plus rapide que Math.random .

Je me souviens avoir lu quelque part que Math.random utilisé System.nanoTime() et des tonnes de trucs fous de modulation et de division. Est-ce vraiment nécessaire ? Mon algorithme est beaucoup plus rapide et semble assez aléatoire.

J'ai deux questions :

• Mon algorithme est-il "suffisamment bon" (pour, disons, un jeu, où vraiment les nombres aléatoires ne sont pas trop importants) ?
• Pourquoi est-ce que Math.random faire autant quand il semble qu'une simple multiplication et la suppression de la décimale suffisent ?

Answer 1

Votre QuickRandom n'a pas vraiment une distribution uniforme. Les fréquences sont généralement plus élevées aux valeurs les plus basses alors que Math.random() a une distribution plus uniforme. Voici une SSCCE ce qui montre que :

package com.stackoverflow.q14491966;

import java.util.Arrays;

public class Test {

    public static void main(String[] 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 distribution |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 distribution |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 distribution QR varie fortement, en fonction des graines initiales, alors que la distribution MR est stable. Parfois, elle atteint la distribution uniforme souhaitée, mais le plus souvent, elle ne l'atteint pas. Voici l'un des exemples les plus extrêmes, il dépasse même les limites du graphique :

QR distribution |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  :

Answer 2

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

• Commencez par une valeur de départ et un multiplicateur.
• Pour générer un numéro aléatoire :
  • Multipliez la graine par le multiplicateur.
  • Définir la graine égale à cette valeur.
  • Renvoyer cette valeur.

Ce générateur possède de nombreuses propriétés intéressantes, mais présente des problèmes importants en tant que bonne source aléatoire. L'article de Wikipedia lié ci-dessus décrit certaines de ses forces et 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 vous aidera !

Answer 3

Votre fonction de nombre aléatoire est médiocre, car elle a trop peu d'état interne -- le nombre produit par la fonction à n'importe quelle étape donnée dépend entièrement du nombre précédent. Par exemple, si nous supposons que magicNumber est égal à 2 (à titre d'exemple), alors la séquence :

0.10 -> 0.20

est fortement reflétée 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 faites des appels successifs à votre fonction pour générer les coordonnées X et Y des objets, les objets formeront des motifs diagonaux clairs.

À moins que vous n'ayez de bonnes raisons de croire que le générateur de nombres aléatoires ralentit votre application (ce qui est TRÈS peu probable), il n'y a aucune raison valable d'essayer d'écrire le vôtre.

Answer 4

Le vrai problème est que l'histogramme de sortie dépend beaucoup trop de la graine initiale - la plupart du temps, la sortie sera presque uniforme, mais la plupart du temps, elle ne le sera pas du tout.

Inspiré par cet article sur la mauvaise qualité de php rand() La fonction est J'ai créé des images matricielles aléatoires en utilisant QuickRandom y System.Random . Cette exécution montre que, parfois, la graine peut avoir un mauvais effet (dans ce cas, elle favorise les nombres les plus faibles), alors qu'à l'inverse, la graine peut avoir un effet négatif. System.Random est assez uniforme.

QuickRandom

System.Random

Encore pire

Si nous initialisons QuickRandom comme new QuickRandom(0.01, 1.03) on obtient 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<double> 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;
        }
    }
}

Answer 5

Un problème avec votre générateur de nombres aléatoires est qu'il n'y a pas d'"état caché" - si je sais quel nombre aléatoire vous avez renvoyé lors du dernier appel, je connais tous les nombres aléatoires que vous enverrez jusqu'à la fin du temps, puisqu'il n'y a qu'un seul résultat suivant possible, et ainsi de suite.

Un autre élément à prendre en compte est la "période" de votre générateur de nombres aléatoires. Évidemment, avec une taille d'état finie, égale à la partie mantisse d'un double, il ne pourra renvoyer que 2^52 valeurs au maximum avant de boucler. Mais c'est dans le meilleur des cas - pouvez-vous prouver qu'il n'y a pas de boucles de période 1, 2, 3, 4... ? Si c'est le cas, votre RNG aura un comportement horrible et dégénéré dans ces cas.

En outre, votre génération de nombres aléatoires aura-t-elle une distribution uniforme pour tous les points de départ ? Si ce n'est pas le cas, votre RNG sera faussé - ou pire, faussé de différentes manières en fonction du point de départ.

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

(Au fait, un bon adage est : Le code le plus rapide est celui qui ne s'exécute pas. Vous pouvez créer le random() le plus rapide du monde, mais il ne sert à rien s'il n'est pas très aléatoire).