He hecho una clase llamada QuickRandom, y su trabajo es producir números aleatorios rápidamente. Es muy simple: sólo tiene que tomar el valor anterior, se multiplica por un double, y tomar la parte decimal.

Aquí está mi QuickRandom de la clase en su totalidad:

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

}

Y aquí está el código que escribí para la prueba:

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

Es un algoritmo muy sencillo que simplemente se multiplica el anterior doble por un «número mágico» de doble. Me tiró bastante rápido, así que probablemente podría hacer mejor, pero, extrañamente, parece estar funcionando bien.

Esto es muestra de la salida de la comentada líneas en el main método:

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. Bastante aleatorio. De hecho, que el trabajo para un generador de números aleatorios en un juego.

Aquí se muestra la salida de la no-comentarios de la parte:

5456313909
1427223941

Wow! Se realiza casi 4 veces más rápido que Math.random.

Recuerdo haber leído en algún lugar que Math.random utilizado System.nanoTime() y toneladas de loco módulo y la división de las cosas. Que es realmente necesario? Mi algoritmo realiza mucho más rápido y se parece bastante al azar.

Tengo dos preguntas:

  • Es mi algoritmo «suficientemente buena» (por, digamos, un juego, donde realmente números aleatorios no son demasiado importantes)?
  • ¿Por qué Math.random hacer mucho cuando lo que parece a simple multiplicación y el corte de la decimal será suficiente?
  • «parece bastante al azar»; debe generar un histograma y la ejecución de algunas de autocorrelación de la secuencia…
  • Yo… eh… ¿qué? No tengo idea de lo que acabas de decir 😛
  • Él se refiere a «parece bastante al azar», no es realmente una medida objetiva de la aleatoriedad y usted debe obtener algunas estadísticas reales.
  • El problema es que no tengo idea de cómo hacer eso. Es por eso que estoy pidiendo aquí.
  • En términos sencillos, se debe investigar si los números tienen un «plano» de la distribución entre 0 y 1, y ver si hay algún periódico/patrones repetitivos a lo largo del tiempo.
  • Ver comentario anterior 😛 También que no es necesario ser perfectamente azar, sólo «suficientemente bueno».
  • Lo que hace al azar significa para usted? Si cada valor en un intervalo se produce igual cantidad de veces después de una suficiente cantidad de pruebas que se ha hecho, se puede concluir que es aleatorio.
  • Usted podría comenzar aquí: en.wikipedia.org/wiki/Statistical_randomness
  • Yo no la necesitamos para ser realmente, realmente aleatorio. Sólo lo suficientemente bueno para tener un jugador humano creo que es lo suficientemente aleatorios.
  • También, Math.random utiliza Random.nextDouble, que realmente no es tan complejo como hacer. Echa un vistazo a su código fuente!
  • Gerencia de recursos humanos. Me han mentido toda mi vida 😛
  • Ok, pero eso no es realmente una pregunta que se puede responder aquí (¿cómo se define «lo suficientemente aleatorios»?). Pero usted sólo debe utilizar Random (o Math.random).
  • 1. Es más rápido, por eso creo que debo utilizar es de 2. Sólo quiero saber si hay algún problema o algo. 3. Hey, esto no es off topic 😛
  • A continuación, un aproximado a una cantidad igual. Ejecutar el resultado de un par de millones de veces, mantenga una matriz que representa cada valor que podría tener y el incremento de su valor en la matriz. Después de que usted puede dar salida a algunas estadísticas (max ocurrencia, min ocurrencia, rango, etc) para determinar si es o no es lo suficientemente aleatorios para usted.
  • Actualmente estoy tratando de buscar la periodicidad. Sigue funcionando, pero de lo que tengo ahora su > 10^9. Por comparación, el Mersenne Twister tiene una periodicidad de 10^6001.
  • Usted necesita para hacer una adecuada autocorrelación, como mínimo. Y probablemente también la necesidad de investigar las propiedades individuales de las posiciones de los bits así (pero esto es ir más allá de mi área de especialización 😉 )
  • Trate de new QuickRandom(0,5) o new QuickRandom(.5, 2). Aquellos que tanto repetidamente de salida 0 por su número.
  • Escribir su propio algoritmo de generación de números aleatorios es como escribir su propio algoritmo de cifrado. Hay mucho del estado de la técnica, por las personas que son hiper-calificado, que es inútil gastar su tiempo tratando de hacer lo correcto. No hay ninguna razón para no usar el Java funciones de la biblioteca, y si usted realmente desea escribir su propia por alguna razón, visita Wikipedia y buscar algoritmos como el Mersenne Twister.
  • Además, un generador de números aleatorios que ha inesperado patrones pueden hacer un juego menos divertido. Por ejemplo, si usted barajar un mazo de cartas y la distribución no es realmente aleatorio, el juego va a sufrir. Y en el Urbano Muertos en línea basado en la web del juego, el RNG es en realidad algo que los jugadores se quejan en los foros de discusión. (En las zonas Urbanas de Muertos, el juego hace las cosas en respuesta a los clics, y se espera que los porcentajes son conocidos, por lo que los jugadores realmente se puede obtener una idea de si el RNG es aleatorio o no!)
  • Yo no iría tan lejos como para afirmar que absolutamente no debe escribir su propia RNG si el uso es no tener mucha responsabilidad. Por supuesto, para cosas como crypto usted definitivamente no debe hacer sus propias implementaciones, como un montón de crypto se basa en el hecho de que los valores de la función se indisinguishable en un auténtico generador de números aleatorios. Todo el criptosistema que va hacia abajo, si el RNG falla en esto. Existen razones válidas para que necesitan gran ancho de banda de secuencias aleatorias para que la biblioteca de Java aplicación pueda ser inadecuada, que es cuando usted necesita para cortar un poco. 🙂
  • el punto que quiero decir es que otras personas han trabajado realmente duro para averiguar realmente buenos algoritmos, y los algoritmos son públicas. Dado que, lo más sensato es utilizar sólo el público algoritmos con sus buenas cualidades. Si alguien quiere jugar con RNG algoritmos, no tengo ninguna objeción. Pero creo que la biblioteca de Java RNG es poco probable que sea un verdadero cuello de botella en un juego, y si Picaporte de la puerta que de verdad necesita algo más rápido, recomiendo usar algo de: en.wikipedia.org/wiki/List_of_random_number_generators
  • Estoy de acuerdo con usted, con la única excepción de la curiosidad. Si uno está realmente interesado en la generación de números pseudo aleatorios, es recomendable intentar crear uno propio algoritmo (siempre que no se sale de la mesa de trabajo, por supuesto – es sólo por diversión). Pero si tu meta es conseguir un PRNG en marcha y funcionando, sí, no reinventar la rueda (obviamente).
  • También, una comparación contra de Matemáticas.azar no es justo. De matemáticas.azar tiene que ser de hilo de guarda, que está utilizando una gran cantidad de tiempo de ejecución, mientras que la clase no se subproceso de guardar. ThreadLocalRandom.getCurrent().nextFloat() es una versión que evita el hilo de problemas, y es por lo tanto mucho más comparables con los de su clase. Como ThreadLocalRandom es de aproximadamente dos a tres veces más rápido que el Azar también logra algo similar en tiempo de ejecución (aunque dando mayor aleatoriedad)
  • Voy a añadir que, incluso si un usuario no puede identificar con precisión lo que el no-aleatoriedad es, que puede ser detectado. Tengo un juego de Yahtzee que los rollos de azar-ishly, pero no son detectables secuencias donde una vez me he metido uno de los (cuatro de una clase, con la casa llena, larga recta) estoy mucho más probable conseguir los otros dos dentro de 2-3 más rollos. Es lo suficientemente previsible como que se mete conmigo cuando estoy jugando a un más aleatoria versión (como con los dados).
  • Usted tiene un error en el constructor por defecto. Math.random() * 10 produce un valor entre 0 y 10, no 1 y 10. Desea Math.random() * 9 + 1. Como está escrito, creo que obtendrá una excepción aproximadamente el 10% del tiempo…
  • Alguien tiene que hablar por aquellos que encontrar la escritura de compresión, PRNGs de cifrado y de diversión. Al igual que yo. Y, de hecho, probablemente como los investigadores que hacerlo para ganarse la vida, estoy seguro de que les resulta divertido, también. Nunca dejes que nadie te diga que no haga algo, porque 1) no son lo suficientemente buenas; o 2) todo ha sido hecho. Si te gusta lo que están haciendo, tanto en 1) y 2) son pura mierda. Y, de hecho, tan lejos como los algoritmos de ir, estos son bastante básicos y accesibles y v fresco. Más gente debería jugar con ellos, no menos. Un par de folk dijo una vez Heath Ledger, que él nunca lo haría como un actor.
  • Estoy de acuerdo. Pero, mantener lejos de código de producción.
  • Seguro, a menos que suceda para ganar una AES, la Wikipedia compresión reto, o en realidad sólo patadas culo como un PRNG. PRNGs son los más fáciles de hackear, solo tiene que probar correctamente : de compresión, y DIEHARD/NIST. Fabricante de la revolución!
  • De hecho la gente que escribe sus propios algoritmos es muy necesario — no te aconsejo que no lo hagan, el hecho de que la gente no sabe sobre él es la razón por la que muchas personas deben jugar y aprender acerca de él. Hay una gran falta de conciencia acerca de crypto y la aleatoriedad. Si más personas pueden escribir y jugar con sus propias cosas, más gente se va a aprender. Que sólo puede ser bueno. Un argumento podría ser que la «programación» es muy difícil, no es tanto el estado de la técnica, y para muchos expertos, no principiantes deben pensar siquiera que viene a la mesa. Claramente, este argumento es falso. Mismo para los nuevos langs/crypto
  • Permítanme repetir una parte de mi comentario: «Si alguien quiere jugar con RNG algoritmos, no tengo ninguna objeción.» Usted no puede convertirse en un maestro sin convertirse en un oficial de primera, y todo el mundo tiene que empezar en alguna parte, y no tengo ninguna objeción a que más gente trabajando en el problema de la RNG. Pero en este caso, Perilla quiere escribir un juego, y claramente no tiene una sólida formación en estadística o matemáticas como se relacionan con los generadores de números aleatorios. Creo que la Perilla de la puerta sería mejor servido por el uso de Java RNG o un conocido algoritmo generador de números aleatorios, y centrándonos en el juego real. O se olvidan que el juego y el estudio del generador de números aleatorios.
  • Mucho me recomiendan buscar una copia de Recetas Numérica por la Prensa, Teukolksy, Vetterling, y Flannery (asegúrese de que sea la tercera edición, ninguna otra edición será suficiente), y de leer la sección de generadores de números aleatorios. Además de la teoría, que dan una buena lección de historia acerca de cómo muchas personas que una vez se pensó que la manera en que lo hizo.
  • Creo que estamos todos de acuerdo entonces. Él también podría hacer tanto juego y RNG. Sin embargo, a veces se confunde con fallos llevar a cosas interesantes, una firma única de los juegos débilmente generador de números aleatorios.
  • «Sólo lo suficientemente bueno para tener un jugador humano creo que es lo suficientemente aleatorios.», puede ser más difícil de lo que piensas… Quoth el creador: «he utilizado las Matemáticas.al azar, Random.org y de otras fuentes, pero siempre han recibido numerosas quejas que los dados no son lo suficientemente aleatorios.» – Dados-O-Matic
  • Knuth también tiene cosas buenas sobre el Azar en el Arte de La Programación de computadoras. Voy a agregar mi voto que los generadores de números aleatorios son divertidos para jugar, sino que (a) usted necesita saber cómo ponerlos a prueba y (b) usted debe saber algo acerca del estado de la técnica.
  • «Se ve bastante aleatorio» es el diablo el que te hablaba. Los seres humanos son muy malas para determinar lo que es aleatorio. Existe una amplia literatura acerca de qué pruebas son buenas para evaluar un generador de números aleatorios. Knuth no es un mal lugar para empezar!
  • search.dilbert.com/comic/Random%20Nine

InformationsquelleAutor Doorknob | 2013-01-24

14 Comentarios

  1. 351

    Su QuickRandom aplicación no ha realmente una distribución uniforme. Las frecuencias son generalmente superiores a los valores más bajos, mientras que Math.random() tiene una distribución más uniforme. He aquí un SSCCE que muestra que:

    La media de los resultados se parece a esto:

    Si repetir la prueba, verás que el QR distribución varía mucho, dependiendo de la inicial de las semillas, mientras que el SEÑOR de distribución es estable. A veces llega el deseado distribución uniforme, pero más a menudo que no. He aquí uno de los ejemplos más extremos, es incluso más allá de las fronteras de la gráfica:

    • +1 para los datos numéricos – aunque mirando en números brutos puede ser engañoso, ya que no quiere decir que tengan diferencia estadísticamente significativa.
    • Estos resultados varían fuertemente con la inicial de las semillas pasan a QuickRandom. A veces, es casi uniforme, a veces es por tanto peor que este.
    • Esto es suficiente para que el globo ocular no-aleatoriedad. 10,000 por bin implica una espera sqrt{varianza} de 100, y estos compartimientos son repetidas ocasiones que.
    • -1 Estos resultados dependen en gran medida de que el valor de magicNumber
    • Cualquier PRNG donde la calidad de los resultados depende en gran medida en el valor inicial de la semilla(s) (en contraposición a la interna constantes) parece roto a mí.
    • Primera regla de estadísticas: graficar los datos. Su análisis es irregular, pero trazando un histograma muestra esta mucho más rápido. 😉 (Y se trata de dos líneas en R.)
    • mejor ahora?
    • Absolutamente. No puedo upvote dos veces por desgracia. 😉
    • Si consideramos este como un LCG (que es), magicNumber no se considera, de hecho, parte de la semilla…
    • +1 para SSCCE.org
    • El simple hecho es que el valor inicial para magicNumber se establece cuando el generador está construido (ya sea pasando como parámetro, o generados de forma aleatoria). Si como dices la calidad de los resultados depende en gran medida de ese valor, debe ser cuidadosamente seleccionado constante (o, posiblemente, seleccionados a partir de un conjunto de estas constantes), no es un valor aleatorio. Así que, ya sea o no que llamamos el valor inicial para magicNumber una «semilla» es realmente nimio; la parte importante es que se libera una enorme carga para el usuario de la PRNG en la buena forma de las constantes de la selección.
    • Sí, debe de ser cuidadosamente elaborados constante, no un valor aleatorio o elegida por el usuario.. cual es la razón de esta «prueba» es un absurdo! Ese es mi punto!
    • hice algunas imágenes para mostrar de esta manera aquí
    • Obligatoria cita: «toda persona que considere aritmética de los métodos de producción de dígitos al azar es, por supuesto, en un estado de pecado.» – John von Neumann (1951) «quien no haya visto la anterior cita en al menos 100 lugares no es probablemente muy antiguo.» – D. V. Pryor (1993) «generadores de números Aleatorios no debe ser elegido al azar.» – Donald Knuth (1986)
    • No me importa acerca de los generadores de números aleatorios, pero he aprendido acerca de sscce.org que me ayudará la próxima vez que desee publicar un problema aquí. Útil post.

  2. 133

    Lo que está describiendo es un tipo de generador de números aleatorios llamado lineal congruential generador. El generador funciona de la siguiente manera:

    • Empezar con un valor de la semilla y el multiplicador.
    • Para generar un número aleatorio:
      • Multiplicar la semilla por el multiplicador.
      • Conjunto de la semilla igual a este valor.
      • Devolver este valor.

    Este generador tiene muchas buenas propiedades, pero tiene problemas importantes como una buena fuente aleatoria. El artículo de la Wikipedia vinculado anteriormente se describen algunas de las fortalezas y debilidades. En resumen, si usted necesita un buen valores aleatorios, esto probablemente no es una aproximación muy buena.

    Espero que esto ayude!

    • Es allí cualquier aleatoriedad en la aritmética de punto flotante errores?
    • Realmente no es «aleatorio» per se. Los resultados serán determinista. Dicho esto, yo no pensaba en que al escribir mi respuesta; tal vez alguien puede aclarar ese detalle?
    • Aritmética de punto flotante son los errores de la aplicación diseñada. Hasta donde yo sé, son coherentes para una determinada plataforma, pero pueden diferir por ejemplo, entre diferentes teléfonos móviles y entre arquitecturas de PC. Aunque hay extra ‘de la guardia de bits que a veces se añade al hacer una serie de cálculos de punto flotante en una fila, y la presencia o ausencia de estas guardia de bits puede hacer un cálculo sutilmente diferentes en el resultado. (guardia de bits, por ejemplo, la expansión de 64 bits de doble 80 bits)
    • También, tenga en cuenta que la teoría detrás de LCRNGs asume que usted está trabajando con enteros! Tirar los números de punto flotante de lo que no el rendimiento de la misma calidad de resultados.
    • estás en lo correcto. Pero si el hardware de punto flotante no seguir las reglas de la sana, hacer esto es lo mismo que hacer el modulo es el tamaño de la mantisa, y la teoría se aplica. Sólo necesitan un cuidado especial en lo que está haciendo.
  3. 113

    Su número aleatorio función es pobre, ya que tiene muy poca estado interno — el número de la salida de la función en cualquier paso dado es totalmente dependiente en el número anterior. Por ejemplo, si asumimos que magicNumber es de 2 (por ejemplo), entonces la secuencia:

    está fuertemente reflejado por secuencias similares:

    En muchos casos, esto generará un notable correlaciones en su juego, por ejemplo, si usted hace llamadas sucesivas a la función para generar coordenadas X e y de los objetos, los objetos se forma clara diagonal patrones.

    Menos que tenga una buena razón para creer que el generador de números aleatorios es el retraso de su aplicación (y esto es MUY raro), no hay ninguna buena razón para probar y escribir su propio.

    • +1 para la respuesta práctica … el uso de este en un shoot em up y respawn de enemigos a lo largo de las diagonales epic con varios disparos en la cabeza? 😀
    • usted no necesita un PRNG si desea que tales patrones.
  4. 110

    El verdadero problema con esto es que la salida de histograma depende de la inicial de la semilla lejos mucho – mucho del tiempo que va a terminar con una cerca de uniforme de salida, pero un montón de tiempo tendrá claramente de la onu-uniforme de salida.

    Inspirado por este artículo acerca de cómo el malo de php rand() función es, he hecho algunas matriz aleatoria de imágenes utilizando QuickRandom y System.Random. Este recorrido muestra cómo, a veces, la semilla puede tener un mal efecto (en este caso favoreciendo números más bajos), donde como System.Random es bastante uniforme.

    QuickRandom

    Es este un

    System.Random

    Es este un

    Incluso Peor

    Si queremos inicializar QuickRandom como new QuickRandom(0.01, 1.03) tenemos esta imagen:

    Es este un

    El Código

    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;
    }
    }
    }
    • Buen código. Sí, eso es genial. Yo solía hacer eso también, a veces, es difícil obtener una medida cuantificable de ella, pero es otra buena manera de ver la secuencia. Y si quería echar un vistazo a las secuencias de más de anchura*altura que podría xor la siguiente imagen con este un píxel por píxel. Creo que el QuickRandom imagen es mucho más estético, aunque, por ser de textura como una alfombra de algas.
    • El estéticamente agradable es la forma de la secuencia tiende a aumentar a medida que usted vaya a lo largo de cada fila (y, a continuación, volver a empezar de nuevo) como el magicNumber multiplicación produce un número similar a prevNum, que muestra la falta de aleatoriedad. Si usamos las semillas new QuickRandom(0.01, 1.03) entonces tenemos este i.imgur.com/Q1Yunbe.png!
    • Sí, gran análisis. Ya que sólo se multiplica mod 1 por una constante claramente antes de ajuste se produce allí será el aumento que usted describe. Parece que esto se podría evitar si tomamos el menos significativo decimal de clasificación por decir multiplicando por 1 mil millones de dólares, a continuación, la reducción de la mod de una paleta de 256 colores.
    • Me puedes decir qué utilizas para generar esas imágenes de salida? Matlab?
    • Echa un vistazo a el código de C# y System.Drawing.Bitmap.
    • Bueno gracias! no se percataron de los espacios de nombres 😉
    • Es una buena manera para crear 3d picos, aunque!

  5. 37

    Un problema con el generador de números aleatorios es que no hay un «estado oculto’ – si yo sé qué número aleatorio que regresó en la última llamada, sé que cada número aleatorio usted podrá enviar hasta el final de los tiempos, ya que sólo hay un posible resultado siguiente, y así sucesivamente y así sucesivamente.

    Otra cosa a considerar es el ‘periodo’ de su generador de números aleatorios. Obviamente con un número finito de tamaño del estado, igual a la mantisa parte de un doble, por lo que sólo será capaz de volver a lo más 2^52 valores antes de un bucle. Pero eso es en el mejor de los casos – se puede demostrar que no existen bucles de período 1, 2, 3, 4…? Si los hay, su generador de números aleatorios se han horrible, degenerados comportamiento en esos casos.

    Además, su generación de números aleatorios tienen una distribución uniforme para todos los puntos de partida? Si no lo hace, entonces su RNG estará sesgada o, peor aún, parcial en diferentes formas, dependiendo de la partida de semillas.

    Si usted puede responder a todas estas preguntas, impresionante. Si usted no puede, entonces usted sabe por qué la mayoría de la gente no re-inventar la rueda, y el uso de una probada generador de números aleatorios 😉

    (Por cierto, un buen refrán es: La forma más rápida de código es un código que no se ejecuta. Usted podría hacer el más rápido aleatorio() en el mundo, pero no es bueno si no es muy aleatorio)

    • Hay al menos un loop de este generador de todas las semillas: 0 -> 0. Dependiendo de la semilla, puede haber otros muchos. (Por ejemplo, con una semilla de 3.0, 0.5 -> 0.5, 0.25 -> 0.75 -> 0.25, 0.2 -> 0.6 -> 0.8 -> 0.4 -> 0.2, etc.)
  6. 36

    Una prueba común, siempre lo hice cuando el desarrollo de PRNGs fue :

    1. Convertir la salida a char valores
    2. Escribir caracteres de valor a un archivo
    3. Comprimir el archivo

    Esto me permite iterar rápidamente en las ideas que eran «lo suficientemente bueno» PRNGs para las secuencias de alrededor de 1 a 20 megabytes. Asimismo, se entregó una mejor arriba a abajo de la imagen que acaba de inspección por los ojos, como cualquier «lo suficientemente bueno» PRNG con la mitad de-una-palabra de estado podría exceder rápidamente sus ojos capacidad de ver el ciclo de punto.

    Si yo era realmente exigente, yo podría tomar lo bueno de los algoritmos y ejecutar el INTRANSIGENTE/NIST pruebas en ellos, para obtener más de una idea y, a continuación, volver atrás y ajustar algunas más.

    La ventaja de la prueba de compresión, en contraposición a una frecuencia de análisis es que, trivialmente es fácil construir una buena distribución : simplemente una salida de 256 bloque de longitud que contiene todos los caracteres de valores de 0 a 255, y hacer esto de 100.000 veces. Pero esta secuencia tiene un ciclo de longitud 256.

    Una distribución sesgada, incluso por un pequeño margen, debe ser recogido por un algoritmo de compresión, especialmente si le das suficiente (por ejemplo, 1 megabyte) de la secuencia para trabajar con. Si algunos de los personajes, o dígrafos, o n-gramas se producen con más frecuencia, un algoritmo de compresión que se puede codificar esta distribución de sesgar a los códigos que favorecen las frecuentes apariciones con breves palabras de código, y obtener un delta de compresión.

    Ya que la mayoría de los algoritmos de compresión son rápidos y no requieren de la implementación (como OSs tienen ellos por ahí), la prueba de compresión es muy útil para la rápida clasificación de pasa/falla para un PRNG usted podría estar en desarrollo.

    Buena suerte con tus experimentos!

    Oh, he realizado esta prueba en el rng tienes arriba, utilizando el siguiente pequeño mod de tu código :

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

    Los resultados fueron :

    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

    Que yo consideraría un PRNG bueno si el archivo de salida no podía ser comprimidos en todo.
    Para ser honesto, yo no creo que su PRNG haría tan bien, sólo el 16% en ~20 Megas es bastante impresionante para una construcción simple. Pero todavía me considero un error.

    • +1, Que es una forma muy útil de la medición de la entropía!
    • Imágenes o no, tengo la misma idea con la postal de años atrás, cuando puedo probar mi aleatoria de los generadores.
    • +1 para la nueva forma de medir la aleatoriedad!
    • Gracias @Alexandre C. y Aristos y aidan. Yo creo que usted.
    • ustedes son geniales!
  7. 33

    El más rápido del generador de números aleatorios se podría implementar es este:

    Es este un

    XD, bromas aparte, además de todo lo dicho aquí, me gustaría contribuir, citando
    que las pruebas de secuencias aleatorias «es una tarea muy difícil» [ 1 ], y hay varias pruebas
    que comprobar ciertas propiedades de los números pseudo-aleatorios, usted puede encontrar un montón de ellos
    aquí: http://www.random.org/analysis/#2005

    Una manera simple de evaluar el generador de números aleatorios «calidad» es la antigua prueba de la Chi Cuadrado.

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

    Citando [ 1 ]

    La idea de la prueba χ2 es comprobar si los números son producidos
    propagación razonablemente. Si generamos N números positivos menos de r, tendríamos
    esperar para obtener acerca de N /r números de cada valor. Pero—y esta es la esencia de la
    la materia—las frecuencias de ocurrencia de todos los valores no debe ser exactamente
    el mismo: que no iba a ser al azar!

    Simplemente calculamos la suma de los cuadrados de las frecuencies de ocurrencia de
    cada valor, escala por la frecuencia esperada, y luego restar fuera del tamaño de la
    de la secuencia. Este número, la «estadística χ2,» puede ser expresado matemáticamente como

    Es este un

    Si la estadística χ2 está cerca de r, entonces los números son aleatorios; si está demasiado lejos,
    entonces ellos no están. Las nociones de «cerca» y «lejos» puede ser más precisa
    definido: existen tablas que indican exactamente cómo se relacionan la estadística a las propiedades de
    las secuencias aleatorias. Por la sencilla prueba que se está realizando, la estadística debe
    estar dentro de 2√r

    El uso de esta teoría y el siguiente código:

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

    Me dieron el siguiente resultado:

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

    Que, para QuickRandom, está muy lejos de r (fuera de r ± 2 * sqrt(r))

    Que se ha dicho, QuickRandom podría ser rápido, pero (como se dice en otra de las respuestas) no es bueno como un generador de números aleatorios


    [ 1 ] ROBERT SEDGEWICK, Algoritmos en C, Addinson Wesley Publishing Company, 1990, páginas 516 y 518

    • +1 para xkcd que es un increíble wobsite (ah, y la gran respuesta) 😛
    • Gracias, y sí de xkcd bastidores! XD
    • La teoría está bien, pero la ejecución es pobre: el código es susceptible de desbordamiento de enteros. En java todos los int[] se inicializan a cero, así que no hay necesidad de esta parte. Casting para flotar es inútil cuando el trabajo w/ dobles. Último: llamar a los métodos nombres random1 y random2 es muy gracioso.
    • Gracias por las observaciones! He hecho una traducción directa desde el código C y no presta mucha atención a ella =(. He hecho algunas modificaciones y actualizada de la respuesta. Agradecería cualquier sugerencia adicional
  8. 14

    Puse un rápido boceto de su algoritmo en JavaScript para evaluar los resultados. Se genera 100,000 enteros aleatorios entre 0 y 99 y pistas de la instancia de cada número entero.

    La primera cosa que noto es que usted es más probable conseguir un número bajo de un número alto. Ves esta más cuando seed1 es alta y seed2 es baja. En un par de instancias, tengo sólo 3 números.

    En el mejor de su algoritmo de las necesidades de algunos de refinación.

  9. 8

    Si el Math.Random() llamadas de función del sistema operativo para obtener la hora del día, entonces usted no puede comparar a su función. Su función es la de un PRNG, mientras que la función está buscando verdaderos números aleatorios. Las manzanas y las naranjas.

    Su PRNG puede ser rápido, pero no tiene suficiente información de estado para lograr un largo período antes de que se repite (y su lógica no es lo suficientemente sofisticados como para siquiera lograr los períodos que son posibles con esa cantidad de información de estado).

    Período es la longitud de la secuencia antes de su PRNG comienza a repetirse. Esto ocurre tan pronto como el PRNG máquina hace una transición de estado a un estado que es idéntica a la de un pasado de estado. A partir de allí, se volverá a repetir las transiciones que se inició en ese estado. Otro problema con el PRNG puede ser un bajo número de secuencias únicas, así como degenerados convergencia en una secuencia que se repite. También puede ser indeseable patrones. Por ejemplo, supongamos que un PRNG parece bastante aleatorio cuando los números están impresos en decimal, pero una inspección de los valores en binario muestra que el bit 4 es simplemente alternar entre 0 y 1 en cada llamada. Oops!

    Echar un vistazo a la Mersenne Twister y otros algoritmos. Hay maneras de lograr un equilibrio entre la duración del periodo y ciclos de CPU. Un enfoque básico (utilizado en el Mersenne Twister) es el ciclo de alrededor en el estado de vectores. Es decir, cuando un número se genera, no se basa en todo el estado, sólo en un par de palabras a partir de la matriz de estado sujetos a un par de bits de operaciones. Pero en cada paso, el algoritmo también se mueve alrededor de la matriz, la codificación de los contenidos un poco a la vez.

    • Que en su mayoría están de acuerdo, excepto con su primer párrafo. El built-in llamadas al azar (y /dev/random en sistemas tipo Unix) son también PRNGs. Me gustaría llamar a cualquier cosa que produce números aleatorios algorítmicamente un PRNG, incluso si la semilla es algo que es difícil de predecir. Hay un par de «verdadero» generadores de números aleatorios que el uso de la desintegración radiactiva, atmosférica, ruido, etc, pero estos a menudo generan relativamente pocos bits/segundo.
    • En las cajas de Linux, /dev/random es una fuente de aleatoriedad real obtenido a partir de los controladores de dispositivos, y no un PRNG. Bloquea cuando no hay suficientes bits están disponibles. La hermana dispositivo /dev/urandom también no cuadra, pero aún no es exactamente un PRNG, ya que se actualiza con bits aleatorios cuando están disponibles.
    • Si las Matemáticas.Aleatorio() llamadas a funciones del sistema operativo para obtener la hora del día — esto es absolutamente falso. (en cualquiera de java sabores/versiones que yo sepa)
    • Esto es a partir de la pregunta original: yo recuerdo haber leído en alguna parte que las Matemáticas.al azar se utiliza el Sistema.nanoTime(). Su conocimiento puede ser vale la pena agregar que hay o en su respuesta. Yo lo he utilizado de forma condicional con un si. 🙂
    • Kaz, tanto nanoTime()+contador/hash se utiliza para el valor predeterminado de la semilla de java.util.Random de oracle/OpenJDK. Eso es para la semilla sólo entonces es un estándar de la LCG. En efecto, el OP generador tarda de 2 números aleatorios para semilla, que está bien así que no hay diferencia de java.util.Random. System.currentTimeMillis() fue la semilla por defecto en JDK1.4-
  10. 7

    Hay muchos, muchos generadores de números pseudoaleatorios por ahí. Por ejemplo Knuth del ranarray, el Mersenne twister, o buscar LFSR generadores. Knuth monumental «Seminumerical algoritmos» analiza el área, y propone algunas lineal congruential generadores (fácil de aplicar, rápido).

    Pero yo sugeriría que usted sólo se adhieren a java.util.Random o Math.random, rápido y en menos de ACEPTAR para el uso ocasional (es decir, los juegos y tal). Si usted es paranoico sobre la distribución (algunos de Monte Carlo programa, o de un algoritmo genético), echa un vistazo a su implementación (fuente está disponible en algún sitio), y la semilla de ellas con algunos verdaderamente aleatorio, ya sea de su sistema operativo o de random.org. Si esto es necesario para algunas aplicaciones donde la seguridad es crítica, usted tendrá que cavar a ti mismo. Y como en el caso de que usted no debe creer lo que algunos cuadrado de color con partes faltantes de los surtidores de aquí, me voy a callar ahora.

  11. 7

    Es muy poco probable que la generación de números aleatorios de los resultados sería un problema para cualquier caso de uso que se le ocurrieron a menos que tenga acceso a un único Random instancia de múltiples hilos (porque Random es synchronized).

    Sin embargo, si que realmente es el caso y usted necesita un montón de números aleatorios rápido, la solución es demasiado poco fiable. A veces da buenos resultados, a veces da horrible resultados (basados en la configuración inicial).

    Si quieres los mismos números que el al Azar clase le da, sólo es más rápido, usted podría deshacerse de la sincronización de allí:

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

    Simplemente tomé la java.util.Al azar código y eliminado la sincronización que se traduce en dos veces el rendimiento en comparación con el original en mi Oráculo de la JVM HotSpot 7u9. Es aún más lento que el QuickRandom, pero da mucho más consistente de los resultados. Para ser más precisos, para el mismo seed valores y de un solo subproceso aplicaciones, da el mismo números pseudo-aleatorios como el original Random clase.


    Este código está basado en el actual java.util.Al azar en OpenJDK 7 que está licenciado bajo GNU GPL v2.


    EDITAR 10 meses más tarde:

    Acabo de descubrir que usted incluso no tiene que usar mi código de arriba para obtener una desincronización Random instancia. Hay una en el JDK, demasiado!

    Vistazo a Java 7 ThreadLocalRandom clase. El código en su interior es casi idéntico a mi código de arriba. La clase es simplemente un local-hilo-aislado Random versión adecuada para la generación de números aleatorios rápidamente. La única pega que puedo pensar es que usted no puede fijar su seed manualmente.

    Ejemplo de uso:

    Random random = ThreadLocalRandom.current();
    • Hmm, me puede comparar QR, Matemáticas.al azar, y ThreadLocalRandom en algún momento, cuando yo no soy demasiado perezoso :) Que interesante, gracias!
    • 1. Usted puede ganar algo más de velocidad al caer la máscara como la más alta de 16 bits no influyen en la usa bits. 2. Usted puede utilizar estos bits, guardar una resta y obtener un mejor generador (más grande del estado; los bits más significativos de un producto son más bien distribuidos, pero algunos de evaluación sería necesario). 3. El Sol chicos simplemente implementar un arcaico RNG por Knuth y se añade la sincronización. 🙁
  12. 3

    ‘Al azar’ es más que acerca de la introducción de los números…. lo que tienes es pseudo-aleatorio

    Si pseudo-aleatorio es lo suficientemente bueno para sus fines, seguro, es la manera más rápida (y XOR+Bitshift será más rápido de lo que usted tiene)

    Rolf

    Edición:

    ACEPTAR, después de ser demasiado apresurado en esta respuesta, permítanme responder a la verdadera razón por la que el código es más rápido:

    Desde el JavaDoc de las Matemáticas.Aleatorio()

    Este método está correctamente sincronizado para permitir el correcto uso por más de un hilo. Sin embargo, si muchos hilos necesidad de generar números pseudo aleatorios a gran velocidad, se puede reducir la contención para cada hilo tiene su propia pseudoaleatoria-generador de número.

    Este es probablemente por qué el código es más rápido.

    • Random es también pseudo-aleatorio…
    • Casi cualquier cosa que no se trata de un hardware generador de ruido o una línea directa hacia el SO de e/s de cosas, va a ser pseudo-aleatorios. Genuino aleatoriedad no puede ser generada por un algoritmo solo; necesita el ruido de algún lugar. (Algunos sistemas operativos’ RNGs conseguir su entrada mediante la medición de cosas como ¿cómo y cuando se mueva el ratón, tipo de material, etc. Se mide en una escala de microsegundos a nanosegundos, que puede ser muy impredecible.)
    • de hecho, hasta donde yo sé la única verdadera valores aleatorios se encuentran el uso de ruidos atmosféricos.
    • El ruido térmico (por ejemplo, en los diodos/resistencias) es bastante aleatorio…
    • estúpido para responder a toda prisa. El De Matemáticas.azar es pseudoaleatoria, y también, es sincronizados.
    • La sincronización podría muy bien explicar por qué Math.random() es más lento. Me gustaría tener para sincronizar o crear una nueva Random cada vez, y ni uno muy atractivo performancewise. Si me importaba rendimiento, me gustaría crear mi propio new Random y sólo use. 😛
    • la desintegración radiactiva es demasiado aleatorios.

  13. 3

    java.util.Azar no es muy diferente, un básico de la LCG descrito por Knuth. Sin embargo, se ha principal 2 principales ventajas y diferencias:

    • thread safe – cada actualización es un CAS que es más caro que un simple escribir y necesidades de una rama (aunque perfectamente predicho de un solo subproceso). Dependiendo de la CPU podría ser una diferencia significativa.
    • no divulgada estado interno – esto es muy importante para cualquier cosa no trivial. Usted desea que los números aleatorios no ser predecible.

    A continuación es la rutina principal la generación de ‘azar’ enteros en java.util.Azar.

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

    Si se quita la AtomicLong y el no divulgada estado (es decir, con todos los bits de la long), se podría obtener un mayor rendimiento de la doble multiplicación/modulo.

    Última nota: Math.random no debe ser utilizado para cualquier cosa, pero las pruebas simples, es propenso a la contención y si aún tienes un par de hilos de llamadas que al mismo tiempo es el rendimiento se degrada. Uno histórico poco conocido característica es la introducción de CAS en java – para batir a un infame de referencia (primero por IBM a través de las características intrínsecas y, a continuación, Sol «CAS de Java»)

  14. 0

    Esta es la función random, yo uso para mis juegos. Es bastante rápido y tiene buena (bastante) de distribución.

    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));
    }
    }
    • Esto no proporciona una respuesta a la pregunta. Para la crítica o la solicitud de aclaración de un autor, deja un comentario debajo de su post.
    • Me parece que ya estaba establecido que el algoritmo original no es lo suficientemente bueno? Tal vez un ejemplo de lo que es suficientemente bueno puede conducir a la inspiración sobre cómo mejorarla?
    • Sí, tal vez, pero que no responde a la pregunta y no hay datos que apoyen su algoritmo en realidad es «lo suficientemente bueno». En general, el número aleatorio algoritms y estrechamente relacionados con los algoritmos de cifrado nunca son tan buenas como las de los expertos que las han implementado en un lenguaje de programación. Por lo tanto, si usted puede apoyar su reclamación y elaborar sobre por qué es mejor que el algoritmo en la Pregunta sería, al menos, responder a una pregunta.
    • Bueno… los Expertos que las han implementado en un lenguaje de programación objetivo de «perfecto» de la distribución, mientras que en un juego, usted nunca tendrá que. Quieres velocidad, y «lo suficientemente bueno» de la distribución. Este código ofrece este. Si es inapropiado aquí, me voy a borrar la respuesta, no hay problema.
    • Sobre el multithreading, el uso de la variable local es una no-op, ya que sin volatile, el compilador es libre de eliminar (o introducir) variables locales a voluntad.

Dejar respuesta

Please enter your comment!
Please enter your name here