# Xorshift

Os geradores de números aleatórios Xorshift, também chamados de geradores de registro de deslocamento, são uma classe de geradores de números pseudoaleatórios inventados por George Marsaglia. Eles são um subconjunto de registradores de deslocamento de feedback linear (RDFLs) que permitem uma implementação particularmente eficiente em software sem o uso excessivo de polinômios esparsos. O próximo número é gerado somando o ou exclusivo(XOR) do próprio valor deslocado um tanto de bits. Isso torna a execução extremamente eficiente em arquiteturas de computador modernas, mas não beneficia a eficiência em uma implementação de hardware. Como todos os RDFLs, os parâmetros devem ser escolhidos cuidadosamente para atingir um longo período.
Para execução em software, os geradores xorshift estão entre os geradores de números aleatórios não criptograficamente seguros mais rápidos, exigindo código e estado muito pequenos. No entanto, eles não passam em todos os testes estatísticos sem refinamento extra. Essa fraqueza é corrigida combinando-as com uma função não linear, conforme descrito no artigo original. Como os geradores xorshift simples (sem uma etapa não linear) falham em alguns testes estatísticos, eles foram acusados de não serem confiáveis.$^{:360}$

## Exemplo de implementação

A representação em C de três algoritmos xorshift$^{:4,5}$ são mostrados aqui. O primeiro tem um estado de 32 bits e período 2$^{32}$−1. O segundo tem um estado de 64 bits e período 2$^{64}$−1. O último tem um estado de 128 bits(representado por 4 valores de 32 bits) e período 2$^{128}$−1. O algoritmo de 128 bits passa nos testes-diehard. No entanto, ele falha nos testes MatrixRank e LinearComp do conjunto de testes BigCrush do framework TestU01.
Todos usam três deslocamentos binários e três a quatro operações XOR:

## Variações não lineares

Todos os geradores xorshift falham em alguns testes no conjunto de testes BigCrush. Isso vale para todos os geradores baseados em recorrências lineares, quinem o Mersenne Twister ou WELL. No entanto, é fácil embaralhar a saída de tais geradores para melhorar sua qualidade.
Os embaralhadores conhecidos como + e * ainda deixam fraqueza nos bits baixos, então eles são recomendados para o uso em pontos flutuantes, já que a conversão para ponto flutuante descarta os bits baixos. Para uso geral, o embaralhador ** (pronunciado starstar) faz com que os geradores RDFL passem com todos os bits.

### xorwow

Marsaglia sugeriu embaralhar a saída combinando-a com um simples contador aditivo módulo 2$^{32}$ (que ele chama de "sequência de Weyl" em homenagem ao teorema da equidistribuição de Weyl). Isso também aumenta o período por um fator de 2$^{32}$, para 2$^{192}$−2$^{32}$:
Isso funciona bem, mas falha em alguns testes no BigCrush. Este gerador é o padrão no kit de ferramentas CUDA da Nvidia.

### xorshift*

Um gerador xorshift* aplica uma multiplicação invertível (módulo do tamanho de 32-bits) como uma transformação não linear à saída de um gerador xorshift, conforme sugerido por Marsaglia. Todos os geradores xorshift* emitem uma sequência de valores que é equidistribuída na dimensão máxima possível (exceto que eles nunca produzirão zero para 16 chamadas, ou seja, 128 bytes, em uma linha).
O seguinte gerador de 64 bits tem um período máximo de 2$^{64}$−1.
O gerador falha apenas no teste MatrixRank do BigCrush, no entanto, se o gerador for modificado para retornar apenas os 32 bits altos, ele passa no BigCrush sem falhas.$^{:7}$ Na verdade, uma versão reduzida com apenas 40 bits de estado interno passa na suíte, sugerindo uma grande margem de segurança.$^{:19}$ Um gerador similar sugerido em Numerical Recipes como RanQ1 também falha no teste BirthdaySpacings.
Vigna sugere um gerador xorshift1024* com 1024 bits de estado e com um período máximo de 2$^{1024}$−1; no entanto, nem sempre passa no BigCrush. o que faz xoshiro256** portanto, uma opção muito melhor.

### xorshift+

O gerador xorshift+ pode ter muito menos falhas do que Mersenne Twister ou WELL. Uma implementação C nativa de um gerador xorshift+ que passa em todos os testes do conjunto BigCrush pode normalmente gerar um número aleatório em menos de 10 ciclos de clock em x86, graças ao processo de pipelining de instrução.
Em vez de usar a multiplicação, é possível usar a adição como uma transformação não linear mais rápida. A ideia foi proposta pela primeira vez por Saito e Matsumoto (também responsáveis pelo Mersenne Twister) no gerador XSadd, que adiciona duas saídas consecutivas de um gerador xorshift subjacente baseado em deslocamentos de 32 bits. No entanto, uma desvantagem de adicionar saídas consecutivas é que, enquanto o gerador xorshift128 subjacente é 2-dimensionalmente equidistribuído, porem o gerador xorshift128+ é apenas 1-dimensionalmente equidistribuído.
XSadd tem fraquezas nos bits baixos de sua saída; it fails several BigCrush tests when the output words are bit-reversed. To correct this problem, Vigna introduced the xorshift+ family, based on 64-bit shifts. xorshift+ generators, even as large as xorshift1024+, exhibit some detectable linearity in the low-order bits of their output; it passes BigCrush, but doesn't when the 32 lowest-order bits are used in reverse order from each 64-bit word. This generator is one of the fastest generators passing BigCrush.
O seguinte gerador xorshift128+ usa 128 bits de estado e tem um período máximo de 2$^{128}$−1.

## xoshiro

xoshiro e xoroshiro usam rotações além de turnos. De acordo com Vigna, eles são mais rápidos e produzem uma saída com melhor qualidade do que o xorshift.
Esta classe de geradores possui variantes para íntegros de 32 bits, 64 bits, e saída de ponto flutuante; para ponto flutuante, são considerados os 53 bits superiores (para binary64) ou os 23 bits superiores (para binary32), pois os bits superiores são de melhor qualidade do que os bits inferiores nos geradores de ponto flutuante. Os algoritmos também incluem uma função de jump, que define o estado em alguns passos – geralmente uma potência de dois que permite que muitos threads de execução comecem em estados iniciais distintos.
Para saída de 32 bits, xoshiro128** e xoshiro128+ são exatamente equivalentes a xoshiro256** e xoshiro256+, com um uint32_t no lugar de um uint64_t e com diferentes constantes de deslocamento/rotação.
Mais recentemente, os geradores xoshiro++ foram feitos como uma alternativa aos geradores xoshiro**. Eles são usados em Java e Julia.

### xoshiro256**

xoshiro256** é uma família de geradores de números aleatórios para 64 bits de uso geral. Ele é usado em Lua e no .NET Framework.

### xoshiro256+

xoshiro256+ é aproximadamente 15% mais rápido que xoshiro256**, mas os três bits mais baixos têm pouca complexidade linear; portanto, ele deve ser usado apenas para resultados de ponto flutuante, extraindo os 53 bits superiores.

### xoroshiro

Se o espaço for escasso, xoroshiro128** e xoroshiro128+ são equivalentes a xoshiro256** e xoshiro256+. Estes têm estados de tamanho menor e, portanto, são menos úteis para programas massivamente paralelos. xoroshiro128+ também exibe uma leve dependência na contagem da população, gerando uma falha após 7000500000000000000♠5 TB de saída. Os autores não acreditam que isso possa ser detectado em programas do mundo real.
xoroshiro64** e xoroshiro64* são equivalentes a xoroshiro128** e xoroshiro128+. Ao contrário dos geradores xoshiro, eles não são replicas diretas de suas contrapartes com alta precisão.

## Inicialização

No documento sobre xoshiro, recomenda-se inicializar o estado dos geradores usando um gerador radicalmente diferente dos geradores inicializados, bem como um que nunca dará um estado "totalmente zero"; para geradores de registro de deslocamento, é impossível escapar desse estado. Os autores recomendam especificamente o uso do gerador SplitMix64, com uma semente de 64 bits, da seguinte forma: