Algoritmo do quadrado do meio (PRNG)

Crie uma classe que retorne números pseudoaleatórios de 32 bits usando o algoritmo do quadrado do meio.

Contexto

Os computadores foram projetados para ser determinísticos, o que significa que toda ação que executam é 100% previsível. No entanto, no caso da geração de números aleatórios (RNG), isso dificulta criar números «aleatórios». Para contornar isso, muitas pessoas criaram geradores de números pseudoaleatórios (PRNG), que geram números que parecem aleatórios, mas continuam perfeitamente previsíveis se você souber como o algoritmo funciona. Um desses algoritmos é chamado de algoritmo do quadrado do meio.

Os PRNGs normalmente recebem uma «semente» como seu estado inicial. Em seguida, para gerar um novo número aleatório, você realiza uma série de cálculos sobre esse estado e então define o estado como esse novo número. O algoritmo do quadrado do meio não é diferente: ele recebe uma semente e realiza uma série de cálculos para encontrar o próximo número.

Suponha que você queira gerar números aleatórios de dois dígitos. Para gerar um novo número, comece com seu estado:

85

Eleve-o ao quadrado:

85^2=7225

e pegue os dois dígitos centrais:

22

... para obter o próximo número aleatório.

Depois de obter o próximo número, armazene-o no estado para usá-lo mais tarde e então retorne-o. Você pode repetir esse processo quantas vezes quiser para gerar quantos números «aleatórios» forem necessários:

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

Esse número específico é importante, pois já geramos o número 10 duas vezes. Devido à forma como o algoritmo funciona, isso significa que o gerador começará a gerar infinitamente o número dez.

Instruções

Para este desafio, em vez de gerar números decimais de dois dígitos, vamos gerar números binários de 32 bits. Exemplo:

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

Sua tarefa é criar uma classe MiddleSquarePRNG com os seguintes métodos:

  • void seed(int newSeed) -- define o estado como newSeed
  • int next() -- retorna o próximo número pseudoaleatório

Exemplos

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

Observações

  • Talvez seja uma boa ideia armazenar o estado como um long em vez de um int para poder elevá-lo ao quadrado.
  • Lembre-se de que o método next() retorna um int, e não um long!
  • Operações com bits podem ajudar aqui.
  • Não se preocupe com sinais — nenhum dos números será grande o bastante para precisar deles.
  • Tentei organizar os testes para que fossem mais fáceis de ler rapidamente.
  • Este não é um bom método para gerar números pseudoaleatórios!