Generador de números aleatorios JavaScript verificables

149

La Math.random()función de JavaScript devuelve un valor aleatorio entre 0 y 1, sembrado automáticamente en función de la hora actual (similar a Java, creo). Sin embargo, no creo que haya ninguna forma de establecer su propia semilla para ello.

¿Cómo puedo hacer un generador de números aleatorios para el que pueda proporcionar mi propio valor inicial, de modo que pueda hacer que produzca una secuencia repetible de números (pseudo) aleatorios?

scunliffe
fuente
1
Nota: En aras de mantener esta pregunta breve y centrada, he dividido el código que estaba en la pregunta anterior a una respuesta de Wiki de la comunidad a continuación.
Ilmari Karonen
1
Ver también stackoverflow.com/questions/521295
Palimondo

Respuestas:

123

Una opción es http://davidbau.com/seedrandom, que es un reemplazo directo de Math.random () basado en RC4 visible con buenas propiedades.

David Bau
fuente
18
El seedrandom de David Bau se ha vuelto lo suficientemente popular como para mantenerlo aquí en Github . Es una lástima que ECMAScript haya sido tan retrovisor durante tanto tiempo que cosas como esta no están incluidas en el lenguaje. En serio, no sembrar !!!
Comer en Joes
2
@EatatJoes, Es a la vez la vergüenza y la gloria de JS que esto sea necesario y posible. Es genial que pueda incluir un archivo y obtener cambios compatibles con versiones anteriores realizados en el objeto Math. No está mal por 10 días de trabajo, Brendan Eich.
Bruno Bronosky
2
Para cualquiera que busque la página npm para este proyecto: npmjs.com/package/seedrandom
Kip
27

Si no necesita la capacidad de siembra, simplemente use Math.random()y cree funciones auxiliares a su alrededor (p. Ej. randRange(start, end)).

No estoy seguro de qué RNG está utilizando, pero es mejor saberlo y documentarlo para que conozca sus características y limitaciones.

Como dijo Starkii, Mersenne Twister es un buen PRNG, pero no es fácil de implementar. Si desea hacerlo usted mismo, intente implementar un LCG : es muy fácil, tiene cualidades de aleatoriedad decentes (no tan buenas como Mersenne Twister) y puede usar algunas de las constantes populares.

EDITAR: considere las excelentes opciones en esta respuesta para implementaciones de RNG visibles cortas, incluida una opción LCG.

function RNG(seed) {
  // LCG using GCC's constants
  this.m = 0x80000000; // 2**31;
  this.a = 1103515245;
  this.c = 12345;

  this.state = seed ? seed : Math.floor(Math.random() * (this.m - 1));
}
RNG.prototype.nextInt = function() {
  this.state = (this.a * this.state + this.c) % this.m;
  return this.state;
}
RNG.prototype.nextFloat = function() {
  // returns in range [0,1]
  return this.nextInt() / (this.m - 1);
}
RNG.prototype.nextRange = function(start, end) {
  // returns in range [start, end): including start, excluding end
  // can't modulu nextInt because of weak randomness in lower bits
  var rangeSize = end - start;
  var randomUnder1 = this.nextInt() / this.m;
  return start + Math.floor(randomUnder1 * rangeSize);
}
RNG.prototype.choice = function(array) {
  return array[this.nextRange(0, array.length)];
}

var rng = new RNG(20);
for (var i = 0; i < 10; i++)
  console.log(rng.nextRange(10, 50));

var digits = ['0', '1', '2', '3', '4', '5', '6', '7', '8', '9'];
for (var i = 0; i < 10; i++)
  console.log(rng.choice(digits));

orip
fuente
2
¿No debería ser el módulo 2 ^ 31? Leí este algoritmo de wiki .
Trantor Liu
3
Para que lo sepa, esto no es "correcto" en el sentido de que no genera lo que dicta la matemática. En otras palabras, un lenguaje que pueda manejar esos números grandes tendrá un resultado diferente. JS se ahoga con los números grandes y la precisión de las chuletas (después de todo, son flotantes).
DDS
44
-1 Esta implementación LCG rompe el límite para enteros exactos en JavaScript, ya que this.a * this.statees probable que resulte en un número mayor que 2 ^ 53. El resultado es un rango de producción limitado, y para algunas semillas posiblemente un período muy corto. Además, en general, el uso de una potencia de dos para mdar como resultado algunos patrones bastante obvios, cuando se está gastando una operación de módulo en lugar de un simple truncamiento de todos modos, no hay razón para no usar un cebado.
aaaaaaaaaaaa
22

Si desea poder especificar la semilla, solo necesita reemplazar las llamadas a getSeconds()y getMinutes(). Puede pasar un int y usar la mitad del mod 60 para el valor de segundos y la otra mitad del módulo 60 para obtener la otra parte.

Dicho esto, este método parece basura. Hacer la generación adecuada de números aleatorios es muy difícil. El problema obvio con esto es que el valor inicial aleatorio se basa en segundos y minutos. Para adivinar la semilla y recrear su flujo de números aleatorios solo requiere probar 3600 combinaciones diferentes de segundos y minutos. También significa que solo hay 3600 semillas diferentes posibles. Esto es corregible, pero sospecharía de este RNG desde el principio.

Si quieres usar un mejor RNG, prueba el Mersenne Twister . Es un RNG bien probado y bastante robusto con una órbita enorme y un rendimiento excelente.

EDITAR: Realmente debería ser correcto y referirme a esto como un generador de números pseudoaleatorios o PRNG.

"Cualquiera que use métodos aritméticos para producir números aleatorios está en un estado de pecado".
                                                                                                                                                          --- John von Neumann

Starkii
fuente
1
Un enlace a las implementaciones JS de Mersenne Twister: math.sci.hiroshima-u.ac.jp/~m-mat/MT/VERSIONS/JAVASCRIPT/…
orip
1
@orip ¿Tiene una fuente para los 3600 estados iniciales? Mersenne Twister se siembra con un número de 32 bits, por lo que el PRNG debería tener 4 mil millones de estados iniciales, solo si la semilla inicial es verdaderamente aleatoria.
Tobias P.
2
@TobiasP. Me refería a la sugerencia de inicializar con una combinación de getSeconds () y getMinutes (), 60 * 60 == 3600 posibles estados iniciales. No me refería a Mersenne Twister.
orip
3
@orip Ok, no estaba claro. Estaba hablando de Mersenne Twister y en la siguiente oración sobre estados iniciales;)
Tobias P.
2
El autor de la pregunta no menciona que necesitan una generación de números aleatorios "adecuada" para cualquier tipo de aplicación criptográficamente sensible. Si bien toda la respuesta es verdadera, solo el primer párrafo es realmente relevante para la pregunta formulada. Quizás agregue un fragmento de código de la solución sugerida.
V. Rubinetti
12

Utilizo un puerto JavaScript del Mersenne Twister: https://gist.github.com/300494 Le permite configurar la semilla manualmente. Además, como se menciona en otras respuestas, el Mersenne Twister es un PRNG realmente bueno.

Christoph Henkelmann
fuente
8

El código que enumeró se parece a un Lehmer RNG . Si este es el caso, entonces 2147483647es el entero con signo más grande de 32 bits, 2147483647es el primo más grande de 32 bits y 48271es un multiplicador de período completo que se utiliza para generar los números.

Si esto es cierto, puede modificar RandomNumberGeneratorpara incluir un parámetro adicional seedy luego configurarlo this.seeden seed; pero debe tener cuidado para asegurarse de que la semilla dé como resultado una buena distribución de números aleatorios (Lehmer puede ser así de extraño), pero la mayoría de las semillas estarán bien.

mipadi
fuente
7

El siguiente es un PRNG que puede alimentarse con una semilla personalizada. Llamar SeedRandomdevolverá una función de generador aleatorio. SeedRandompuede invocarse sin argumentos para inicializar la función aleatoria devuelta con la hora actual, o puede invocarse con 1 o 2 inters no negativos como argumentos para inicializar con esos enteros. Debido a la precisión de coma flotante, la siembra con solo 1 valor solo permitirá que el generador se inicie en uno de 2 ^ 53 estados diferentes.

La función generadora aleatoria devuelta toma 1 argumento entero llamado limit, el límite debe estar en el rango de 1 a 4294965886, la función devolverá un número en el rango 0 al límite-1.

function SeedRandom(state1,state2){
    var mod1=4294967087
    var mul1=65539
    var mod2=4294965887
    var mul2=65537
    if(typeof state1!="number"){
        state1=+new Date()
    }
    if(typeof state2!="number"){
        state2=state1
    }
    state1=state1%(mod1-1)+1
    state2=state2%(mod2-1)+1
    function random(limit){
        state1=(state1*mul1)%mod1
        state2=(state2*mul2)%mod2
        if(state1<limit && state2<limit && state1<mod1%limit && state2<mod2%limit){
            return random(limit)
        }
        return (state1+state2)%limit
    }
    return random
}

Ejemplo de uso:

var generator1=SeedRandom() //Seed with current time
var randomVariable=generator1(7) //Generate one of the numbers [0,1,2,3,4,5,6]
var generator2=SeedRandom(42) //Seed with a specific seed
var fixedVariable=generator2(7) //First value of this generator will always be
                                //1 because of the specific seed.

Este generador exhibe las siguientes propiedades:

  • Tiene aproximadamente 2 ^ 64 diferentes estados internos posibles.
  • Tiene un período de aproximadamente 2 ^ 63, mucho más de lo que cualquier persona necesitará de manera realista en un programa de JavaScript.
  • Debido a que los modvalores son primos, no hay un patrón simple en la salida, sin importar el límite elegido. Esto es diferente a algunos PRNG más simples que exhiben algunos patrones bastante sistemáticos.
  • Descarta algunos resultados para obtener una distribución perfecta sin importar el límite.
  • Es relativamente lento, funciona alrededor de 10 000 000 de veces por segundo en mi máquina.
aaaaaaaaaaaa
fuente
2
¿Por qué esto produce un patrón? for (var i = 0; i < 400; i++) { console.log("input: (" + i * 245 + ", " + i * 553 + ") | output: " + SeedRandom(i * 245, i * 553)(20)); }
Timothy Kanski
@TimothyKanski Porque lo estás usando mal. No soy un experto, pero esto ocurre porque está inicializando el generador en cada iteración, solo ve su primer valor basado en la semilla y NO itera en los números posteriores del generador. Creo que esto sucederá en cualquier PRNG que no divida la semilla en el intervalo especificado.
bryc
5

Si programa en mecanografiado, adapté la implementación de Mersenne Twister que fue presentada en la respuesta de Christoph Henkelmann a este hilo como una clase mecanografiada:

/**
 * copied almost directly from Mersenne Twister implementation found in https://gist.github.com/banksean/300494
 * all rights reserved to him.
 */
export class Random {
    static N = 624;
    static M = 397;
    static MATRIX_A = 0x9908b0df;
    /* constant vector a */
    static UPPER_MASK = 0x80000000;
    /* most significant w-r bits */
    static LOWER_MASK = 0x7fffffff;
    /* least significant r bits */

    mt = new Array(Random.N);
    /* the array for the state vector */
    mti = Random.N + 1;
    /* mti==N+1 means mt[N] is not initialized */

    constructor(seed:number = null) {
        if (seed == null) {
            seed = new Date().getTime();
        }

        this.init_genrand(seed);
    }

    private init_genrand(s:number) {
        this.mt[0] = s >>> 0;
        for (this.mti = 1; this.mti < Random.N; this.mti++) {
            var s = this.mt[this.mti - 1] ^ (this.mt[this.mti - 1] >>> 30);
            this.mt[this.mti] = (((((s & 0xffff0000) >>> 16) * 1812433253) << 16) + (s & 0x0000ffff) * 1812433253)
                + this.mti;
            /* See Knuth TAOCP Vol2. 3rd Ed. P.106 for multiplier. */
            /* In the previous versions, MSBs of the seed affect   */
            /* only MSBs of the array mt[].                        */
            /* 2002/01/09 modified by Makoto Matsumoto             */
            this.mt[this.mti] >>>= 0;
            /* for >32 bit machines */
        }
    }

    /**
     * generates a random number on [0,0xffffffff]-interval
     * @private
     */
    private _nextInt32():number {
        var y:number;
        var mag01 = new Array(0x0, Random.MATRIX_A);
        /* mag01[x] = x * MATRIX_A  for x=0,1 */

        if (this.mti >= Random.N) { /* generate N words at one time */
            var kk:number;

            if (this.mti == Random.N + 1)   /* if init_genrand() has not been called, */
                this.init_genrand(5489);
            /* a default initial seed is used */

            for (kk = 0; kk < Random.N - Random.M; kk++) {
                y = (this.mt[kk] & Random.UPPER_MASK) | (this.mt[kk + 1] & Random.LOWER_MASK);
                this.mt[kk] = this.mt[kk + Random.M] ^ (y >>> 1) ^ mag01[y & 0x1];
            }
            for (; kk < Random.N - 1; kk++) {
                y = (this.mt[kk] & Random.UPPER_MASK) | (this.mt[kk + 1] & Random.LOWER_MASK);
                this.mt[kk] = this.mt[kk + (Random.M - Random.N)] ^ (y >>> 1) ^ mag01[y & 0x1];
            }
            y = (this.mt[Random.N - 1] & Random.UPPER_MASK) | (this.mt[0] & Random.LOWER_MASK);
            this.mt[Random.N - 1] = this.mt[Random.M - 1] ^ (y >>> 1) ^ mag01[y & 0x1];

            this.mti = 0;
        }

        y = this.mt[this.mti++];

        /* Tempering */
        y ^= (y >>> 11);
        y ^= (y << 7) & 0x9d2c5680;
        y ^= (y << 15) & 0xefc60000;
        y ^= (y >>> 18);

        return y >>> 0;
    }

    /**
     * generates an int32 pseudo random number
     * @param range: an optional [from, to] range, if not specified the result will be in range [0,0xffffffff]
     * @return {number}
     */
    nextInt32(range:[number, number] = null):number {
        var result = this._nextInt32();
        if (range == null) {
            return result;
        }

        return (result % (range[1] - range[0])) + range[0];
    }

    /**
     * generates a random number on [0,0x7fffffff]-interval
     */
    nextInt31():number {
        return (this._nextInt32() >>> 1);
    }

    /**
     * generates a random number on [0,1]-real-interval
     */
    nextNumber():number {
        return this._nextInt32() * (1.0 / 4294967295.0);
    }

    /**
     * generates a random number on [0,1) with 53-bit resolution
     */
    nextNumber53():number {
        var a = this._nextInt32() >>> 5, b = this._nextInt32() >>> 6;
        return (a * 67108864.0 + b) * (1.0 / 9007199254740992.0);
    }
}

puede usarlo de la siguiente manera:

var random = new Random(132);
random.nextInt32(); //return a pseudo random int32 number
random.nextInt32([10,20]); //return a pseudo random int in range [10,20]
random.nextNumber(); //return a a pseudo random number in range [0,1]

verifique la fuente para más métodos.

bennilo
fuente
0

Nota: Este código se incluyó originalmente en la pregunta anterior. En aras de mantener la pregunta breve y centrada, la he trasladado a esta respuesta de Wiki de la comunidad.

Encontré este código dando vueltas y parece funcionar bien para obtener un número aleatorio y luego usar la semilla después, pero no estoy muy seguro de cómo funciona la lógica (por ejemplo, de dónde provienen los números 2345678901, 48271 y 2147483647).

function nextRandomNumber(){
  var hi = this.seed / this.Q;
  var lo = this.seed % this.Q;
  var test = this.A * lo - this.R * hi;
  if(test > 0){
    this.seed = test;
  } else {
    this.seed = test + this.M;
  }
  return (this.seed * this.oneOverM);
}

function RandomNumberGenerator(){
  var d = new Date();
  this.seed = 2345678901 + (d.getSeconds() * 0xFFFFFF) + (d.getMinutes() * 0xFFFF);
  this.A = 48271;
  this.M = 2147483647;
  this.Q = this.M / this.A;
  this.R = this.M % this.A;
  this.oneOverM = 1.0 / this.M;
  this.next = nextRandomNumber;
  return this;
}

function createRandomNumber(Min, Max){
  var rand = new RandomNumberGenerator();
  return Math.round((Max-Min) * rand.next() + Min);
}

//Thus I can now do:
var letters = ['a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'];
var numbers = ['1','2','3','4','5','6','7','8','9','10'];
var colors = ['red','orange','yellow','green','blue','indigo','violet'];
var first = letters[createRandomNumber(0, letters.length)];
var second = numbers[createRandomNumber(0, numbers.length)];
var third = colors[createRandomNumber(0, colors.length)];

alert("Today's show was brought to you by the letter: " + first + ", the number " + second + ", and the color " + third + "!");

/*
  If I could pass my own seed into the createRandomNumber(min, max, seed);
  function then I could reproduce a random output later if desired.
*/
revs Ilmari Karonen
fuente
3
Wow, las funciones RandomNumberGeneratory nextRandomNumberrealmente datan de 1996. Se supone que es un Lehmer / LCG RNG. Utiliza algunas matemáticas inteligentes para realizar módulos aritméticos en enteros de 32 bits que de otra forma serían demasiado pequeños para contener algunos valores intermedios. La cuestión es que JavaScript no implementa enteros de 32 bits, sino más bien flotantes de 64 bits, y dado que la división no es una división entera, como este código supone que el resultado no es un generador de Lehmer. Produce algún resultado que parece aleatorio, pero las garantías de un generador Lehmer no se aplican.
aaaaaaaaaaaa
1
La createRandomNumberfunción es una adición posterior, hace casi todo mal, más notablemente crea una instancia de un nuevo RNG cada vez que se llama, lo que significa que las llamadas en sucesión rápida usarán el mismo flotante. En el código dado, es casi imposible 'a'emparejarse con cualquier cosa que no sea '1'y 'red'.
aaaaaaaaaaaa
-2

OK, aquí está la solución que decidí.

Primero crea un valor semilla utilizando la función "newseed ()". Luego pasa el valor semilla a la función "srandom ()". Por último, la función "srandom ()" devuelve un valor pseudoaleatorio entre 0 y 1.

El bit crucial es que el valor semilla se almacena dentro de una matriz. Si se tratara simplemente de un entero o flotante, el valor se sobrescribiría cada vez que se llamara a la función, ya que los valores de enteros, flotantes, cadenas, etc. se almacenan directamente en la pila en lugar de solo los punteros como en el caso de las matrices y otros objetos Por lo tanto, es posible que el valor de la semilla permanezca persistente.

Finalmente, es posible definir la función "srandom ()" de tal manera que sea un método del objeto "Math", pero lo dejaré a usted para que lo descubra. ;)

¡Buena suerte!

JavaScript:

// Global variables used for the seeded random functions, below.
var seedobja = 1103515245
var seedobjc = 12345
var seedobjm = 4294967295 //0x100000000

// Creates a new seed for seeded functions such as srandom().
function newseed(seednum)
{
    return [seednum]
}

// Works like Math.random(), except you provide your own seed as the first argument.
function srandom(seedobj)
{
    seedobj[0] = (seedobj[0] * seedobja + seedobjc) % seedobjm
    return seedobj[0] / (seedobjm - 1)
}

// Store some test values in variables.
var my_seed_value = newseed(230951)
var my_random_value_1 = srandom(my_seed_value)
var my_random_value_2 = srandom(my_seed_value)
var my_random_value_3 = srandom(my_seed_value)

// Print the values to console. Replace "WScript.Echo()" with "alert()" if inside a Web browser.
WScript.Echo(my_random_value_1)
WScript.Echo(my_random_value_2)
WScript.Echo(my_random_value_3)

Lua 4 (mi entorno objetivo personal):

-- Global variables used for the seeded random functions, below.
seedobja = 1103515.245
seedobjc = 12345
seedobjm = 4294967.295 --0x100000000

-- Creates a new seed for seeded functions such as srandom().
function newseed(seednum)
    return {seednum}
end

-- Works like random(), except you provide your own seed as the first argument.
function srandom(seedobj)
    seedobj[1] = mod(seedobj[1] * seedobja + seedobjc, seedobjm)
    return seedobj[1] / (seedobjm - 1)
end

-- Store some test values in variables.
my_seed_value = newseed(230951)
my_random_value_1 = srandom(my_seed_value)
my_random_value_2 = srandom(my_seed_value)
my_random_value_3 = srandom(my_seed_value)

-- Print the values to console.
print(my_random_value_1)
print(my_random_value_2)
print(my_random_value_3)
posfan12
fuente
PD: todavía no estoy tan familiarizado con Stack Overflow, pero ¿por qué las publicaciones no están en orden cronológico?
posfan12
Hola @ posfan12: las respuestas a las preguntas generalmente se enumeran en orden de "votos a favor", de modo que la "crema sube a la cima". Sin embargo, para garantizar una visualización justa de las respuestas con la misma puntuación, se muestran en orden aleatorio. Dado que esta fue mi pregunta originalmente ;-) Sin duda me aseguraré de revisarla en breve. Si a mí (u otros) les parece útil esta respuesta, la votaremos a favor, y si considero que es la respuesta "correcta", también verá una marca de verificación verde agregada a esta respuesta. - Bienvenido a StackOverflow!
scunliffe
2
-1 Esta implementación LCG rompe el límite para enteros exactos en JavaScript, ya que seedobj[0] * seedobjaes probable que resulte en un número mayor que 2 ^ 53. El resultado es un rango de producción limitado, y para algunas semillas posiblemente un período muy corto.
aaaaaaaaaaaa