Hispanopedia Wiki
En matemáticas e informática , el método del cuadrado medio es un método para generar números pseudoaleatorios . En la práctica, es un método con muchas deficiencias para diversos fines, ya que su período suele ser muy corto y presenta graves debilidades; si se repite suficientes veces, el método del cuadrado medio comenzará a generar repetidamente el mismo número o volverá a un número anterior de la secuencia y entrará en un bucle indefinido.
Historia
En matemáticas
El método fue inventado por John von Neumann y fue descrito por él en una conferencia en 1949. [ 1 ]
En la charla de 1949, Von Neumann bromeó diciendo que «cualquiera que considere métodos aritméticos para producir dígitos aleatorios está, por supuesto, en estado de pecado». Lo que quería decir, explicó, era que no existían verdaderos «números aleatorios», solo medios para producirlos, y que «un procedimiento aritmético estricto», como el método del cuadrado medio, «no es tal método». Sin embargo, descubrió que estos métodos eran cientos de veces más rápidos que leer números «verdaderamente» aleatorios de tarjetas perforadas , lo cual tenía importancia práctica para su trabajo en ENIAC . Descubrió que la «destrucción» de las secuencias del cuadrado medio era un factor a su favor, porque podía detectarse fácilmente: «uno siempre teme la aparición de ciclos cortos no detectados». [ 1 ] Nicholas Metropolis informó de secuencias de 750.000 dígitos antes de la «destrucción» mediante el uso de números de 38 bits con el método del «cuadrado medio». [ 2 ]
El libro Los dados rotos de Ivar Ekeland ofrece un relato extenso de cómo el método fue inventado por un fraile franciscano conocido solo como el hermano Edvin en algún momento entre 1240 y 1250. [ 3 ] Supuestamente, el manuscrito ahora está perdido, pero Jorge Luis Borges le envió a Ekeland una copia que hizo en la Biblioteca Vaticana .
Modificar el algoritmo del cuadrado medio con una secuencia de Weyl mejora el período y la aleatoriedad. [ 4 ] [ 5 ]
El método
Para generar una secuencia de números pseudoaleatorios de n dígitos, se crea un valor inicial de n dígitos y se eleva al cuadrado, obteniendo un número de 2n dígitos. Si el resultado tiene menos de 2n dígitos , se añaden ceros a la izquierda para compensar. Los n dígitos centrales del resultado conformarán el siguiente número de la secuencia y se devolverán como resultado. Este proceso se repite para generar más números.
El valor de n debe ser par para que el método funcione ; si el valor de n es impar, no necesariamente habrá un conjunto único de " n dígitos centrales" entre los que elegir. Consideremos lo siguiente: si un número de 3 dígitos se eleva al cuadrado, puede dar como resultado un número de 6 dígitos (por ejemplo, 540² = 291600). Si hubiera 3 dígitos centrales, quedarían 6 − 3 = 3 dígitos para distribuir a la izquierda y a la derecha del dígito central. Es imposible distribuir estos dígitos de manera uniforme a ambos lados del número central, por lo que no existen "dígitos centrales". Es aceptable rellenar los dígitos iniciales con ceros a la izquierda para crear un número de n dígitos par (por ejemplo, 540 → 0540).
Para un generador de números de n dígitos, el período no puede ser mayor que 8n . Si los n dígitos centrales son todos ceros, el generador emitirá ceros indefinidamente. Si la primera mitad de un número en la secuencia son ceros, los números subsiguientes irán disminuyendo hasta cero. Si bien estas secuencias de ceros son fáciles de detectar, ocurren con demasiada frecuencia como para que este método sea práctico. El método del cuadrado central también puede quedarse atascado en un número distinto de cero. Para n = 4, esto ocurre con los valores 0100, 2500, 3792 y 7600. Otros valores de semilla forman ciclos repetitivos muy cortos, por ejemplo, 0540 → 2916 → 5030 → 3009. Estos fenómenos son aún más evidentes cuando n = 2, ya que ninguna de las 100 semillas posibles genera más de 14 iteraciones sin volver a 0, 10, 50, 60 o un bucle de 24 ↔ 57.
Ejemplo de implementación
Aquí, el algoritmo se muestra en Python 3.12 .
seed_number = int ( input ( "Por favor, introduzca un número de cuatro dígitos: \n [####] " )) number = seed_number already_seen = set () counter = 0mientras number no esté en already_seen : counter += 1 already_seen.add ( number ) number = int ( str ( number * number ) .zfill ( 8 )[ 2 : 6 ] ) # zfill agrega relleno de ceros print ( f "# { counter } : { number } " )print ( f "Comenzamos con { seed_number } y" f "nos hemos repetido después de { counter } pasos" f "con { number } ." )Véase también
Referencias
- 1 2 Los artículos de 1949 no se reimprimieron hasta 1951. John von Neumann, “Varias técnicas utilizadas en relación con dígitos aleatorios”, en A. S. Householder, G. E. Forsythe y H. H. Germond, eds., Método de Monte Carlo, Serie de Matemáticas Aplicadas de la Oficina Nacional de Estándares , vol. 12 (Washington, DC: Oficina de Imprenta del Gobierno de EE. UU., 1951): págs. 36–38.
- ↑ Donald E. Knuth, El arte de la programación de computadoras, Vol. 2, Algoritmos seminuméricos , 2.ª ed. (Reading, Mass.: Addison-Wesley, 1981), cap. 3, sección 3.1.
- ↑ Ivar Ekeland (15 de junio de 1996). Los dados rotos y otros relatos matemáticos del azar . University of Chicago Press. ISBN 978-0-226-19992-4.
- ↑ Kneusel, Ron (2018). Números aleatorios y computadoras (1.ª ed.). Springer. pp. 13–14 .
- ↑ Widynski, Bernard (abril de 2017). "Middle-Square Weyl Sequence RNG". arXiv : 1704.00358 [ cs.CR ].
- Generadores de números pseudoaleatorios
- Juan von Neumann
