Fuente original del algoritmo aleatorio `(seed * 9301 + 49297)% 233280`?

9

Si busca ejemplos de cómo crear un generador de números aleatorios (pseudo), se encontrará con cosas como esta (ejemplo específico http://indiegamr.com/generate-repeatable-random-numbers-in-js/ ):

// the initial seed
Math.seed = 6;

// in order to work 'Math.seed' must NOT be undefined,
// so in any case, you HAVE to provide a Math.seed
Math.seededRandom = function(max, min) {
    max = max || 1;
    min = min || 0;

    Math.seed = (Math.seed * 9301 + 49297) % 233280;
    var rnd = Math.seed / 233280;

    return min + rnd * (max - min);
}

Esos números específicos (9301, 49297, 233280) y el algoritmo se usan una y otra vez, pero nadie parece tener una referencia definitiva para esto. ¿Quién inventó este algoritmo y probó la distribución? ¿Hay un papel o algo para citar?

jlarson
fuente
55
que es un generador congruente lineal pero con una bastante pequeño periodo (sólo 233K mientras que un int 32 bits permite tener un período de 4 mil millones
monstruo de trinquete
1
La gente a menudo copia el código directamente de los libros, por lo que probablemente sea de un libro antiguo en algún lugar y se haya copiado varias veces. También parece ser un caso limitante. Posiblemente útil: heydari.persiangig.com/Ebooks/Applied_Crypto-Ch11-ch20.pdf/… ict.griffith.edu.au/anthony/info/C/RandomNumbers
barrycarter
2
Cualquiera sea el origen, esos son valores terribles para usar para calcular una semilla.
3
@jlarson un comentario no es lo suficientemente largo, pero hay dos problemas a la mano. Primero, como aludía al trinquete, el módulo es el período máximo : número de números únicos antes de que el generador se repita. El período real puede ser menor. En segundo lugar, los otros dos números (principalmente el multiplicando) deben ser relativamente primos al número de módulo para garantizar un período más largo. Idealmente, el número de módulo es el primo más grande menor que el número entero positivo máximo que cabe en el tipo de datos, y los otros dos números también son números primos grandes.
1
Esa es la versión corta y corta de por qué esos números son terribles, dado que esta es una discusión paralela y agregar una respuesta real no es apropiado para esta pregunta. Recomiendo rebotar en Wikipedia y quizás en Matemáticas o Ciencias de la Computación para obtener más información, aunque técnicamente los algoritmos de números pseudoaleatorios también están en el tema en los Programadores.

Respuestas:

7

Una búsqueda rápida en Google Books muestra que estos números (9301, 49297, 233280) se han utilizado en varias referencias:

  • Recetas Numéricas en FORTRAN 77
  • Una introducción a los métodos numéricos en C ++
  • Recurso del desarrollador de CGI: programación web en TCL y PERL
  • Efectivo Fortran 77 para ingenieros y científicos
  • Desarrollo de JavaScript
  • Todo en C
  • Ejemplos de Java en una cáscara de nuez
  • Algoritmos seminuméricos
  • Una introducción a la mecánica

El más antiguo es el método informático de 1977 para cálculos matemáticos de George Elmer Forsythe, Michael A. Malcolm, Cleve B. Moler (Prentice-Hall), aunque Google no muestra dónde se utilizó el texto en el libro, por lo que no se puede verificar.

La primera muestra del texto es Recetas numéricas en Pascal (primera edición): El arte de la computación científica , Volumen 1 de Press, Teukolsky, Vetterling y Flannery en una tabla de página completa de "Constantes para generadores portátiles de números aleatorios". Estos números particulares se dan con un desbordamiento en 2 ^ 31.

La serie de libros Numerical Recipes es muy popular y se ha impreso desde 1986.

Hugo
fuente
1
Wow, si la respuesta no está aquí, no sé dónde estaría. Gracias ... // Esperaba poder señalar algunas investigaciones específicas sobre por qué estos números son especiales, pero esto es suficiente. 9301 es un producto de dos números primos (71x131), 49297 es un número primo, instintivamente siento que debe ser relevante. 233280 no es primo, es igual a 2x2x2x2x2x2x3x3x3x3x3x3x5 (o 2 ^ 6 * 3 ^ 5 * 5)
jlarson