Algoritmo del cuadrado medio (PRNG)

Crea una clase que devuelva números pseudoaleatorios de 32 bits mediante el algoritmo del cuadrado medio.

Antecedentes

Las computadoras se diseñaron para ser deterministas, lo que significa que cada acción que realizan es 100% predecible. Sin embargo, en el caso de la generación de números aleatorios (RNG), esto dificulta producir números «aleatorios». Para evitarlo, muchas personas han ideado generadores de números pseudoaleatorios (PRNG), que generan números que parecen aleatorios, pero siguen siendo perfectamente predecibles si conoces cómo funciona el algoritmo. Uno de estos algoritmos se llama algoritmo del cuadrado medio.

Los PRNG normalmente reciben una «semilla» como su estado inicial. Luego, para generar un nuevo número aleatorio, realizas una serie de cálculos sobre ese estado y después estableces el estado en ese nuevo número. El algoritmo del cuadrado medio no es diferente: recibe una semilla y luego realiza una serie de cálculos para encontrar el siguiente número.

Supongamos que quieres generar números aleatorios de dos dígitos. Para generar un número nuevo, comienza con tu estado:

85

Elévalo al cuadrado:

85^2=7225

y toma los dos dígitos centrales:

22

... para obtener el siguiente número aleatorio.

Una vez que hayas obtenido el siguiente número, guárdalo en el estado para usarlo más adelante y luego devuélvelo. Puedes repetir este proceso tantas veces como quieras para generar tantos números «aleatorios» como necesites:

22
22^2=0484 (pad the number with zeroes)
48 <- next random number
48^2=2304
30 <- next random number
30^2=0900
90 <- next random number
90^2=8100
10 <- next random number
10^2=0100
10 <- next random number

Este número en particular es importante, ya que hasta ahora hemos generado dos veces el número 10. Debido a cómo funciona el algoritmo, esto significa que el generador comenzará a generar infinitamente el número diez.

Instrucciones

Para este desafío, en lugar de generar números decimales de dos dígitos, generaremos números binarios de 32 bits. Ejemplo:

00101000010100001010110110000010 (equal to 676,375,938)
0000011001011001010011111010010110000110110110001111011000000100 (equal to 457,484,409,505,379,844)
01001111101001011000011011011000 (digits 16-48; equal to 1,336,248,024) <- next random number

Tu tarea es crear una clase MiddleSquarePRNG con los siguientes métodos:

  • void seed(int newSeed) -- establece el estado en newSeed
  • int next() -- devuelve el siguiente número pseudoaleatorio

Ejemplos

MiddleSquarePRND rand = new MiddleSquarePRND();
rand.seed(6492);
assert rand.next() == 643;
assert rand.next() == 6;
assert rand.next() == 0;
assert rand.next() == 0;

Notas

  • Quizá te convenga almacenar el estado como un long en lugar de un int para poder elevarlo al cuadrado.
  • ¡Recuerda que el método next() devuelve un int, no un long!
  • Las operaciones de bits podrían ser útiles aquí.
  • No te preocupes por los signos — ninguno de los números será lo bastante grande como para necesitarlos.
  • He intentado organizar las pruebas para que sean más fáciles de leer a primera vista.
  • ¡Este no es un buen método para generar números pseudoaleatorios!