Recentemente precisei gerar números aleatórios em um sistema escrito em linguagem legada, no caso, o velho e confiável COBOL.
O objetivo era usar esses valores na chave primária de uma tabela, pois tinhamos como requisito que essa chave contivesse números sem significado, sorteados de tal forma que não fossem de fácil adivinhação, descartando-se assim o uso de um simples campo numérico autoincremental.
No caso, como a aplicação não precisava de primor estatístico e nem segurança criptográfica – além da linguagem não dar suporte a operadores binários – optei por implementar um simples gerador baseado em congruencia linear.
Nesse tipo de gerador, temos a seguinte relação recorrente:
O problema foi como escolher os três parâmetros de geração a, c e m de forma que possam ser processados em inteiros de 18 digitos (limitação imposta pela linguagem) e que tenha um ciclo de repetição o mais longo possível, isto é, percorra todos os números do conjunto de inteiros previamente definido antes que ocorra repetição dos elementos gerados.
Para calcular tais parâmetros, fiz uso da dica constante na própria página da wikipedia que diz como escolher valores que resultem em períodos longos de geração sem repetição.
Assim, com base no método citado no artigo, construí o roteiro abaixo (que é uma versão simplificada do roteiro original que utilizei):
1) Escolha um número máximo esperado para o numero aleatorio (MAX);
2) Procure o primeiro número PRIMO antes de: MAX / (3*3*3*3*3*2);
3) Parametro M = (PRIMO*3*3*3*3*3*2):
4) Parametro A = (PRIMO*3*2+1)
5) Definir o parametro C como 7.
6) Teste se:
6.1) A e 1 são congruentes em relação ao primo?
6.2) A e 1 são congruentes em relação a 3?
6.3) A e 1 são congruentes em relação a 2?
Vamos então a um exemplo prático.
Digamos que desejamos gerar números entre 0 e 9999, sendo que os números só devem se repetir quando não houver mais inteiros “sorteados”.
Seguindo os passos do roteiro acima temos:
1) MAX = 9999;
2) 9999 / 486 ~= 20. Nesse caso, PRIMO = 19;
3) Parametro M = (19*486) = 9234:
4) Parametro A = (19*3*2+1) = 115
5) Definir o parametro C como 7.
6) Teste se:
6.1) A e 1 são congruentes em relação ao primo? 115 mod 19 = 1.
6.2) A e 1 são congruentes em relação a 3? 115 mod 3 = 1.
6.3) A e 1 são congruentes em relação a 2? 115 mod 2 = 1.
Em sequencia, supondo-se a existencia da função LCG(a, c, m, semente_inicial), vejamos os primeiros numeros gerados com base na semente “1″:
LCG(115, 7, 9234, 1) = {122, 4803, 7546, 9035, 4824, 727, 506, 2793, 7246, 2237…}
Para atestar se o período alcançado pelos parametros calculados foi o mais longo possível, desenvolvi um pequeno programa que gera números aleatórios com base na LCG até que um número já sorteado apareça novamente (para períodos curtos, como o do exemplo, pode-se verificar isso até mesmo no MS-Excel).
Em todos os testes que fiz da LCG acima, o período foi de 9234 números até que ocorra repetição (isto é, período = m) , servindo assim para a finalidade proposta.
