Gerador congruencial linear - Linear congruential generator

Dois LCGs módulo-9 mostram como diferentes parâmetros levam a diferentes durações de ciclo. Cada linha mostra o estado evoluindo até que se repita. A linha superior mostra um gerador com m  = 9, a  = 2, c  = 0 e uma semente de 1, que produz um ciclo de comprimento 6. A segunda linha é o mesmo gerador com uma semente de 3, que produz um ciclo de comprimento 2. Usando a  = 4 ec  = 1 (linha inferior) dá um comprimento de ciclo de 9 com qualquer semente em [0, 8].

Um gerador congruencial linear ( LCG ) é um algoritmo que produz uma sequência de números pseudo-aleatórios calculados com uma equação linear descontínua por partes . O método representa um dos algoritmos geradores de números pseudo - aleatórios mais antigos e mais conhecidos . A teoria por trás deles é relativamente fácil de entender e são facilmente implementados e rápidos, especialmente em hardware de computador que pode fornecer aritmética modular por truncamento de bits de armazenamento.

O gerador é definido pela relação de recorrência :

onde está a sequência de valores pseudo-aleatórios, e

- o " módulo "
- o "multiplicador"
- o "incremento"
- a "semente" ou "valor inicial"

são constantes inteiras que especificam o gerador. Se c  = 0, o gerador é freqüentemente chamado de gerador congruencial multiplicativo (MCG) ou Lehmer RNG . Se c  ≠ 0, o método é denominado gerador congruencial misto .

Quando c  ≠ 0, um matemático chamaria a recorrência de transformação afim , não linear , mas o nome impróprio está bem estabelecido na ciência da computação.

História

O gerador Lehmer foi publicado em 1951 e o gerador congruencial Linear foi publicado em 1958 por WE Thomson e A. Rotenberg.

Duração do período

Um benefício dos LCGs é que, com a escolha apropriada de parâmetros, o período é conhecido e longo. Embora não seja o único critério, um período muito curto é uma falha fatal em um gerador de números pseudo-aleatórios.

Embora os LCGs sejam capazes de produzir números pseudo-aleatórios que podem passar nos testes formais de aleatoriedade , a qualidade da saída é extremamente sensível à escolha dos parâmetros m e a . Por exemplo, um  = 1 e c  = 1 produz um modulo- simples m contador, o qual tem um período longo, mas é, obviamente, não-aleatória.

Historicamente, escolhas ruins para um levaram a implementações ineficazes de LCGs. Um exemplo particularmente ilustrativo disso é RANDU , que foi amplamente usado no início dos anos 1970 e levou a muitos resultados que estão sendo questionados devido ao uso deste pobre LCG.

Existem três famílias comuns de escolha de parâmetro:

m primo, c = 0

Artigo principal: gerador de números aleatórios Lehmer

Esta é a construção original do Lehmer RNG. O período é m −1 se o multiplicador a for escolhido para ser um elemento primitivo do módulo de inteiros m . O estado inicial deve ser escolhido entre 1 e m −1.

Uma desvantagem de um módulo principal é que a redução modular requer um produto de largura dupla e uma etapa de redução explícita. Freqüentemente, um primo um pouco menor que uma potência de 2 é usado (os primos de Mersenne 2 31 −1 e 2 61 −1 são populares), de modo que o módulo de redução m  = 2 e  -  d pode ser calculado como ( ax  mod 2 e ) +  d  ⌊ ax / 2 e ⌋ . Isso deve ser seguido por uma subtração condicional de m se o resultado for muito grande, mas o número de subtrações é limitado a ad / m , que pode ser facilmente limitado a um se d for pequeno.

Se um produto de largura dupla não estiver disponível e o multiplicador for escolhido com cuidado, o método de Schrage pode ser usado. Para fazer isso, fator m  =  qa + r , ou seja, q = ⌊ m / a ⌋ e r = m mod a . Em seguida, calcule ax  mod  m = a ( x mod q ) - r ⌊ x / q ⌋ . Como x  mod  q < q ≤ m / a , o primeiro termo é estritamente menor que am / a  =  m . Se a for escolhido de forma que r  ≤  q (e, portanto, r / q  ≤ 1), então o segundo termo também é menor que m : r ⌊ x / q ⌋ ≤ rx / q = x ( r / q ) ≤ x < m . Assim, ambos os produtos podem ser calculados com um produto de largura única, e a diferença entre eles está no intervalo [1− m ,  m −1], então pode ser reduzido a [0,  m −1] com uma única adição condicional .

Uma segunda desvantagem é que é difícil converter o valor 1 ≤  x  <  m em bits aleatórios uniformes. Se um primo um pouco menor que uma potência de 2 for usado, às vezes os valores ausentes são simplesmente ignorados.

m uma potência de 2, c = 0

Escolher m como uma potência de 2 , na maioria das vezes m = 2 32 ou m = 2 64 , produz um LCG particularmente eficiente, porque isso permite que a operação do módulo seja calculada simplesmente truncando a representação binária. Na verdade, os bits mais significativos geralmente não são computados. Existem, no entanto, desvantagens.

Esta forma tem período máximo m / 4, alcançado se a  ≡ 3 ou a  ≡ 5 (mod 8). O estado inicial X 0 deve ser ímpar e os três bits inferiores de X alternam entre dois estados e não são úteis. Pode-se mostrar que esta forma é equivalente a um gerador com um módulo de um quarto do tamanho e c ≠ 0.

Um problema mais sério com o uso de um módulo de potência de dois é que os bits baixos têm um período mais curto do que os bits altos. O bit de ordem mais baixa de X nunca muda ( X é sempre ímpar) e os próximos dois bits alternam entre dois estados. (Se a  ≡ 5 (mod 8), o bit 1 nunca muda e o bit 2 se alterna. Se a  ≡ 3 (mod 8), o bit 2 nunca muda e o bit 1 se alterna.) O bit 3 se repete com um período de 4, bit 4 tem um período de 8 e assim por diante. Apenas o bit mais significativo de X atinge o período completo.

c ≠ 0

Quando c ≠ 0, os parâmetros corretamente escolhidos permitem um período igual am , para todos os valores de sementes. Isso ocorrerá se e somente se :

  1. e são relativamente primos ,
  2. é divisível por todos os fatores principais de ,
  3. é divisível por 4 se for divisível por 4.

Esses três requisitos são chamados de Teorema de Hull-Dobell.

Essa forma pode ser usada com qualquer m , mas só funciona bem para m com muitos fatores primos repetidos, como uma potência de 2; usar o tamanho de palavra de um computador é a escolha mais comum. Se m fosse um número inteiro-quadrado livre , isto permitiria apenas um  ≡ 1 (mod  m ), o que faz com que uma muito pobre PRNG; uma seleção de possíveis multiplicadores de período completo só está disponível quando m tem fatores primos repetidos.

Embora o teorema de Hull-Dobell forneça o período máximo, não é suficiente para garantir um bom gerador. Por exemplo, é desejável que a  - 1 não seja mais divisível pelos fatores primos de m do que o necessário. Assim, se m é uma potência de 2, então a  - 1 deve ser divisível por 4, mas não divisível por 8, ou seja,  a  ≡ 5 (mod 8).

Na verdade, a maioria dos multiplicadores produz uma sequência que falha em um teste de não aleatoriedade ou em outro, e encontrar um multiplicador que seja satisfatório para todos os critérios aplicáveis ​​é bastante desafiador. O teste espectral é um dos testes mais importantes.

Observe que um módulo de potência de 2 compartilha o problema descrito acima para c  = 0: os bits k baixos formam um gerador com módulo 2 k e, portanto, se repetem com um período de 2 k ; apenas o bit mais significativo atinge o período completo. Se um número pseudo-aleatório menor que r for desejado, ⌊ rX / m ⌋ é um resultado de qualidade muito mais alta do que X mod r . Infelizmente, a maioria das linguagens de programação torna o último muito mais fácil de escrever ( X % r), por isso é a forma mais comumente usada.

O gerador não é sensível à escolha de c , contanto que seja relativamente primo ao módulo (por exemplo, se m é uma potência de 2, então c deve ser ímpar), então o valor c = 1 é comumente escolhido.

A série produzida por outras escolhas de c pode ser escrita como uma função simples da série quando c = 1. Especificamente, se Y é a série prototípica definida por Y 0 = 0 e Y n +1 =  aY n +1 mod m, então uma série geral X n +1 =  aX n + c mod  m pode ser escrita como uma função afim de Y :

Mais geralmente, quaisquer duas séries X e Z com o mesmo multiplicador e módulo são relacionadas por

Parâmetros de uso comum

A tabela a seguir lista os parâmetros de LCGs em uso comum, incluindo funções rand () integradas em bibliotecas de tempo de execução de vários compiladores . Esta tabela é para mostrar a popularidade, não exemplos para emular; muitos desses parâmetros são ruins. Tabelas de bons parâmetros estão disponíveis.

Fonte módulo
m 		multiplicador
a   		 incremento
c 		bits de saída de semente em rand () ou Random (L)
ZX81 2 16 + 1 75 74
Receitas Numéricas 2 32 1664525 1013904223
Borland C / C ++ 2 32 22695477 1 bits 30..16 em rand () , 30..0 em lrand ()
glibc (usado pelo GCC ) 2 31 1103515245 12345 bits 30..0
ANSI C : Watcom , Digital Mars , CodeWarrior , IBM VisualAge C / C ++
C90 , C99 , C11 : Sugestão na ISO / IEC 9899, C18 		2 31 1103515245 12345 bits 30..16
Borland Delphi , Virtual Pascal 2 32 134775813 1 bits 63..32 de (semente × L)
Turbo Pascal 2 32 134775813 (8088405 16 ) 1
Microsoft Visual / Quick C / C ++ 2 32 214013 (343FD 16 ) 2531011 (269EC3 16 ) bits 30..16
Microsoft Visual Basic (6 e anteriores) 2 24 1140671485 (43FD43FD 16 ) 12820163 (C39EC3 16 )
RtlUniform da API nativa 2 31 - 1 2147483629 (7FFFFFED 16 ) 2147483587 (7FFFFFC3 16 )
Apple CarbonLib , C ++ 11 'sminstd_rand0 2 31 - 1 16807 0 veja MINSTD
C ++ 11 'sminstd_rand 2 31 - 1 48271 0 veja MINSTD
MMIX por Donald Knuth 2 64 6364136223846793005 1442695040888963407
Newlib , Musl 2 64 6364136223846793005 1 bits 63..32
VMS 's MTH $ RANDOM , versões antigas do glibc 2 32 69069 (10DCD 16 ) 1
Java 's java.util.Random, POSIX [ln] rand48, glibc [ln] rand48 [_r] 2 48 25214903917 (5DEECE66D 16 ) 11 bits 47..16

random0

134456 = 2 3 7 5 8121 28411
POSIX [jm] rand48, glibc [mj] rand48 [_r] 2 48 25214903917 (5DEECE66D 16 ) 11 bits 47..15
POSIX [de] rand48, glibc [de] rand48 [_r] 2 48 25214903917 (5DEECE66D 16 ) 11 bits 47..0
cc65 2 23 65793 (10101 16 ) 4282663 (415927 16 ) bits 22..8
cc65 2 32 16843009 (1010101 16 ) 826366247 (31415927 16 ) bits 31..16
Anteriormente comum: RANDU 2 31 65539 0

Conforme mostrado acima, os LCGs nem sempre usam todos os bits nos valores que produzem. Por exemplo, a implementação Java opera com valores de 48 bits em cada iteração, mas retorna apenas seus 32 bits mais significativos. Isso ocorre porque os bits de ordem superior têm períodos mais longos do que os bits de ordem inferior (veja abaixo). LCGs que usam essa técnica de truncamento produzem valores estatisticamente melhores do que aqueles que não usam. Isso é especialmente perceptível em scripts que usam a operação mod para reduzir o alcance; modificar o número aleatório mod 2 levará à alternância de 0 e 1 sem truncamento.

Vantagens e desvantagens

LCGs são rápidos e requerem memória mínimo (um modulo- m número, frequentemente de 32 ou 64 bits) para reter estado. Isso os torna valiosos para simular vários fluxos independentes. LCGs não se destinam e não devem ser usados ​​para aplicações criptográficas; use um gerador de números pseudo-aleatórios criptograficamente seguro para tais aplicativos.

Hiperplanos de um gerador congruencial linear em três dimensões. Essa estrutura é o que o teste espectral mede.

Embora os LCGs tenham alguns pontos fracos específicos, muitas de suas falhas vêm de um estado muito pequeno. O fato de que as pessoas foram induzidas por tantos anos a usá-los com módulos tão pequenos pode ser visto como uma prova da força da técnica. Um LCG com estado grande o suficiente pode passar até mesmo em testes estatísticos rigorosos; um LCG módulo-2 que retorna os 32 bits altos passa pelo conjunto SmallCrush do TestU01, e um LCG de 96 bits passa pelo conjunto BigCrush mais rigoroso.

Para um exemplo específico, espera-se que um gerador de número aleatório ideal com 32 bits de saída (pelo teorema do aniversário ) comece a duplicar as saídas anteriores após √ m ≈ 2 16 resultados. Qualquer PRNG cuja saída esteja em seu estado completo e não truncado não produzirá duplicatas até que seu período completo tenha decorrido, uma falha estatística facilmente detectável. Por razões relacionadas, qualquer PRNG deve ter um período maior do que o quadrado do número de saídas necessárias. Dadas as velocidades dos computadores modernos, isso significa um período de 2 64 para todos, exceto os aplicativos menos exigentes, e mais longo para simulações exigentes.

Uma falha específica dos LCGs é que, se usados ​​para escolher pontos em um espaço n-dimensional, os pontos ficarão em, no máximo, n √ n ! ⋅ m hiperplanos ( teorema de Marsaglia , desenvolvido por George Marsaglia ). Isso se deve à correlação serial entre valores sucessivos da sequência X n . Multiplicadores escolhidos de forma descuidada geralmente terão muito menos aviões bem espaçados, o que pode levar a problemas. O teste espectral , que é um teste simples da qualidade de um LCG, mede esse espaçamento e permite a escolha de um bom multiplicador.

O espaçamento do plano depende do módulo e do multiplicador. Um módulo grande o suficiente pode reduzir essa distância abaixo da resolução de números de precisão dupla. A escolha do multiplicador torna-se menos importante quando o módulo é grande. Ainda é necessário calcular o índice espectral e certificar-se de que o multiplicador não é ruim, mas puramente probabilisticamente, torna-se extremamente improvável encontrar um multiplicador ruim quando o módulo é maior do que cerca de 2 64 .

Outra falha específica dos LCGs é o curto período dos bits de ordem inferior quando m é escolhido para ser uma potência de 2. Isso pode ser mitigado usando um módulo maior do que a saída necessária e usando os bits mais significativos do estado.

No entanto, para algumas aplicações, os LCGs podem ser uma boa opção. Por exemplo, em um sistema embarcado, a quantidade de memória disponível costuma ser severamente limitada. Da mesma forma, em um ambiente como um console de videogame, pegar um pequeno número de bits de alta ordem de um LCG pode ser suficiente. (Os bits de ordem inferior dos LCGs quando m é uma potência de 2 nunca devem ser considerados para qualquer grau de aleatoriedade.) Os bits de ordem inferior passam por ciclos muito curtos. Em particular, qualquer LCG de ciclo completo, quando m é uma potência de 2, produzirá resultados alternadamente ímpares e pares.

LCGs devem ser avaliados com muito cuidado para adequação em aplicações não criptográficas onde a aleatoriedade de alta qualidade é crítica. Para simulações de Monte Carlo, um LCG deve usar um módulo maior e de preferência muito maior do que o cubo do número de amostras aleatórias que são necessárias. Isso significa, por exemplo, que um (bom) LCG de 32 bits pode ser usado para obter cerca de mil números aleatórios; um LCG de 64 bits é bom para cerca de 21 amostras aleatórias (um pouco mais de dois milhões), etc. Por esse motivo, na prática os LCGs não são adequados para simulações de Monte Carlo em grande escala.

Código de amostra

Código Python

A seguir está uma implementação de um LCG em Python , na forma de um gerador : 

from typing import Generator

def lcg(modulus: int, a: int, c: int, seed: int) -> Generator[int, None, None]:
    """Linear congruential generator."""
    while True:
        seed = (a * seed + c) % modulus
        yield seed

Pascal grátis

O Free Pascal usa um Mersenne Twister como seu gerador de números pseudo-aleatórios padrão, enquanto o Delphi usa um LCG. Aqui está um exemplo compatível com Delphi em Free Pascal baseado nas informações da tabela acima. Dado o mesmo valor RandSeed, ele gera a mesma sequência de números aleatórios que o Delphi. 

unit lcg_random;
{$ifdef fpc}{$mode delphi}{$endif}
interface

function LCGRandom: extended; overload; inline;
function LCGRandom(const range:longint): longint; overload; inline;

implementation
function IM: cardinal; inline;
begin
  RandSeed := RandSeed * 134775813 + 1;
  Result := RandSeed;
end;

function LCGRandom: extended; overload; inline;
begin
  Result := IM * 2.32830643653870e-10;
end;

function LCGRandom(const range: longint): longint; overload; inline;
begin
  Result := IM * range shr 32;
end;

Como todos os geradores de números pseudo-aleatórios, um LCG precisa armazenar o estado e alterá-lo cada vez que gera um novo número. Vários threads podem acessar este estado simultaneamente causando uma condição de corrida. As implementações devem usar estados diferentes, cada um com inicialização exclusiva para threads diferentes, para evitar sequências iguais de números aleatórios em threads em execução simultânea.

Derivados LCG

Existem vários geradores que são geradores congruenciais lineares em uma forma diferente e, portanto, as técnicas usadas para analisar LCGs podem ser aplicadas a eles.

Um método de produzir um período mais longo é somar as saídas de vários LCGs de diferentes períodos tendo um grande mínimo múltiplo comum ; o gerador Wichmann-Hill é um exemplo dessa forma. ( Preferiríamos que fossem completamente coprimos , mas um módulo primo implica um período par, então deve haver um fator comum de 2, pelo menos.) Isso pode ser mostrado como equivalente a um único LCG com um módulo igual ao produto dos módulos LCG do componente.

Os PRNGs adicionar-com-transportar e subtrair-com-emprestar de Marsaglia com um tamanho de palavra de b = 2 w e atrasos r e s ( r  >  s ) são equivalentes aos LCGs com um módulo de b r  ±  b s  ± 1.

PRNGs multiplique com transporte com um multiplicador de a são equivalentes a LCGs com um grande módulo primo de ab r -1 e um multiplicador de potência de 2 b .

Um gerador congruencial permutado começa com um LCG de potência de 2 módulos e aplica uma transformação de saída para eliminar o problema de período curto nos bits de ordem inferior.

Comparação com outros PRNGs

A outra primitiva amplamente usada para obter sequências pseudo-aleatórias de longo período é a construção de registro de deslocamento de feedback linear , que é baseada na aritmética em GF (2) [ x ], o anel polinomial sobre GF (2) . Ao invés de adição e multiplicação inteiro, as operações básicas são ou-exclusivo e reporte menos multiplicação , o qual é geralmente implementada como uma sequência de deslocamentos lógicos . Eles têm a vantagem de que todos os seus bits são de período completo; eles não sofrem com a fraqueza nos bits de ordem inferior que atormentam o módulo aritmético 2 k .

Exemplos desta família incluem geradores xorshift e o twister Mersenne . O último fornece um período muito longo (2 19937 -1) e uniformidade variável, mas falha em alguns testes estatísticos. Os geradores Fibonacci retardados também se enquadram nesta categoria; embora usem adição aritmética, seu período é garantido por um LFSR entre os bits menos significativos.

É fácil detectar a estrutura de um registro de mudança de feedback linear com testes apropriados, como o teste de complexidade linear implementado no conjunto TestU01 ; uma matriz circulante booleana inicializada a partir de bits consecutivos de um LFSR nunca terá classificação maior que o grau do polinômio. Adicionar uma função de mistura de saída não linear (como no xoshiro256 ** e nas construções de gerador congruencial permutado ) pode melhorar muito o desempenho em testes estatísticos.

Outra estrutura para um PRNG é uma função de recorrência muito simples combinada com uma poderosa função de mixagem de saída. Isso inclui cifras de bloco de modo contador e geradores não criptográficos, como SplitMix64 .

Uma estrutura semelhante a LCGs, mas não equivalente, é o gerador recursivo múltiplo: X n  = ( a 1 X n −1  + a 2 X n −2  + ··· + a k X n - k ) mod  m para k  ≥ 2. Com um módulo primo, isso pode gerar períodos de até m k −1, portanto, é uma extensão útil da estrutura LCG para períodos maiores.

Uma técnica poderosa para gerar números pseudo-aleatórios de alta qualidade é combinar dois ou mais PRNGs de estrutura diferente; a soma de um LFSR e um LCG (como nas construções KISS ou xorwow ) pode funcionar muito bem com algum custo em velocidade.

Veja também

Notas

Referências

links externos