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.[1]:360
Exemplo de implementação[editar | editar código-fonte]
A representação em C[a] de três algoritmos xorshift[2]:4,5 são mostrados aqui. O primeiro tem um estado de 32 bits e período 232−1. O segundo tem um estado de 64 bits e período 264−1. O último tem um estado de 128 bits(representado por 4 valores de 32 bits) e período 2128−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:
#include <stdint.h>
struct xorshift32_state {
uint32_t a;
};
/* O estado não deve ser inicializado com zero */
uint32_t xorshift32(struct xorshift32_state *state)
{
/* Algoritimo "xor" da p. 4 de Marsaglia, "Xorshift RNGs" */
uint32_t x = state->a;
x ^= x << 13;
x ^= x >> 17;
x ^= x << 5;
return state->a = x;
}
struct xorshift64_state {
uint64_t a;
};
uint64_t xorshift64(struct xorshift64_state *state)
{
uint64_t x = state->a;
x ^= x << 13;
x ^= x >> 7;
x ^= x << 17;
return state->a = x;
}
/* a struct do estado pode ser re-definida com um par de uint64_t
ou um uint128_t se suportado */
struct xorshift128_state {
uint32_t x[4];
};
/* O estado não deve ser inicializado com zero */
uint32_t xorshift128(struct xorshift128_state *state)
{
/* Algoritimo "xor128" da p. 5 de Marsaglia, "Xorshift RNGs" */
uint32_t t = state->x[3];
uint32_t s = state->x[0]; /* Shift de 32-bits simulado */
state->x[3] = state->x[2];
state->x[2] = state->x[1];
state->x[1] = s;
t ^= t << 11;
t ^= t >> 8;
return state->x[0] = t ^ s ^ (s >> 19);
}
Variações não lineares[editar | editar código-fonte]
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[editar | editar código-fonte]
Marsaglia sugeriu embaralhar a saída combinando-a com um simples contador aditivo módulo 232 (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 232, para 2192−232:
#include <stdint.h>
struct xorwow_state {
uint32_t x[5];
uint32_t counter;
};
/* Os primeiros 4 uint32_t nao devem ser zero */
uint32_t xorwow(struct xorwow_state *state)
{
/* Algoritimo "xorwow" da p. 5 de Marsaglia, "Xorshift RNGs" */
uint32_t t = state->x[4];
uint32_t s = state->x[0]; /* Shift de 32-bits simulado */
state->x[4] = state->x[3];
state->x[3] = state->x[2];
state->x[2] = state->x[1];
state->x[1] = s;
t ^= t >> 2;
t ^= t << 1;
t ^= s ^ (s << 4);
state->x[0] = t;
state->counter += 362437;
return t + state->counter;
}
Isso funciona bem, mas falha em alguns testes no BigCrush.[3] Este gerador é o padrão no kit de ferramentas CUDA da Nvidia.[4]
xorshift*[editar | editar código-fonte]
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 264−1.
#include <stdint.h>
/* xorshift64s, Variante A_1(12,25,27) usando um multiplicador M_32 da linha 3 tabela 5 */
uint64_t xorshift64star(void) {
static uint64_t x = 1; /* Semente inicial não deve ser zero */
x ^= x >> 12;
x ^= x << 25;
x ^= x >> 27;
return x * 0x2545F4914F6CDD1DULL;
}
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.[5]: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.[5]: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 21024−1; no entanto, nem sempre passa no BigCrush.[6] o que faz xoshiro256** portanto, uma opção muito melhor.
#include <stdint.h>
/* O estado deve ser semeado para que pelo menos um valor seja maior de 0 */
struct xorshift1024s_state {
uint64_t x[16];
int index;
};
uint64_t xorshift1024s(struct xorshift1024s_state *state)
{
int index = state->index;
uint64_t const s = state->x[index++];
uint64_t t = state->x[index &= 15];
t ^= t << 31; // a
t ^= t >> 11; // b -- Os valores aqui podem ser afinados.
t ^= s ^ (s >> 30); // c
state->x[index] = t;
state->index = index;
return t * 1181783497276652981ULL;
}
xorshift+[editar | editar código-fonte]
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;[6] it passes BigCrush, but doesn't when the 32 lowest-order bits are used in reverse order from each 64-bit word.[6] 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 2128−1.
#include <stdint.h>
struct xorshift128p_state {
uint64_t x[2];
};
/* O estado dever ser semeado para que não seja zero */
uint64_t xorshift128p(struct xorshift128p_state *state)
{
uint64_t t = state->x[0];
uint64_t const s = state->x[1];
state->x[0] = s;
t ^= t << 23; // a
t ^= t >> 18; // b -- Os shifts e os multiplicadores podem ser afinados
t ^= s ^ (s >> 5); // c
state->x[1] = t;
return t + s;
}
xoshiro[editar | editar código-fonte]
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. [7][8]
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.[9]
xoshiro256**[editar | editar código-fonte]
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.[10]
/* Adaptado do codigo incluido no site de Sebastiano Vigna */
#include <stdint.h>
uint64_t rol64(uint64_t x, int k)
{
return (x << k) | (x >> (64 - k));
}
struct xoshiro256ss_state {
uint64_t s[4];
};
uint64_t xoshiro256ss(struct xoshiro256ss_state *state)
{
uint64_t *s = state->s;
uint64_t const result = rol64(s[1] * 5, 7) * 9;
uint64_t const t = s[1] << 17;
s[2] ^= s[0];
s[3] ^= s[1];
s[1] ^= s[2];
s[0] ^= s[3];
s[2] ^= t;
s[3] = rol64(s[3], 45);
return result;
}
xoshiro256+[editar | editar código-fonte]
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.
#include <stdint.h>
uint64_t rol64(uint64_t x, int k)
{
return (x << k) | (x >> (64 - k));
}
struct xoshiro256p_state {
uint64_t s[4];
};
uint64_t xoshiro256p(struct xoshiro256p_state *state)
{
uint64_t* s = state->s;
uint64_t const result = s[0] + s[3];
uint64_t const t = s[1] << 17;
s[2] ^= s[0];
s[3] ^= s[1];
s[1] ^= s[2];
s[0] ^= s[3];
s[2] ^= t;
s[3] = rol64(s[3], 45);
return result;
}
xoroshiro[editar | editar código-fonte]
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 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[editar | editar código-fonte]
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:
#include <stdint.h>
struct splitmix64_state {
uint64_t s;
};
uint64_t splitmix64(struct splitmix64_state *state) {
uint64_t result = (state->s += 0x9E3779B97f4A7C15);
result = (result ^ (result >> 30)) * 0xBF58476D1CE4E5B9;
result = (result ^ (result >> 27)) * 0x94D049BB133111EB;
return result ^ (result >> 31);
}
struct xorshift128_state {
uint32_t x[4];
};
// Isso pode ser replicado para todos geradores.
void xorshift128_init(struct xorshift128_state *state, uint64_t seed) {
struct splitmix64_state smstate = {seed};
uint64_t tmp = splitmix64(&smstate);
state->x[0] = (uint32_t)tmp;
state->x[1] = (uint32_t)(tmp >> 32);
tmp = splitmix64(&smstate);
state->x[2] = (uint32_t)tmp;
state->x[3] = (uint32_t)(tmp >> 32);
}
Referências[editar | editar código-fonte]
- ↑ Panneton, François; L'Ecuyer, Pierre (outubro de 2005). «On the xorshift random number generators» (PDF). ACM Transactions on Modeling and Computer Simulation. 15 (4): 346–361. doi:10.1145/1113316.1113319
- ↑ Marsaglia, George (julho de 2003). «Xorshift RNGs». Journal of Statistical Software. 8 (14). doi:10.18637/jss.v008.i14
- ↑ Le Floc'h, Fabien (12 de janeiro de 2011). «XORWOW L'ecuyer TestU01 Results». Chase The Devil (blog). Consultado em 2 de novembro de 2017
- ↑ «cuRAND Testing». Nvidia. Consultado em 2 de novembro de 2017
- ↑ a b O'Neill, Melissa E. (5 de setembro de 2014). PCG: A Family of Simple Fast Space-Efficient Statistically Good Algorithms for Random Number Generation (PDF) (Relatório técnico). Harvey Mudd College. pp. 6–8. HMC-CS-2014-0905
- ↑ a b c Lemire, Daniel; O’Neill, Melissa E. (abril de 2019). «Xorshift1024*, Xorshift1024+, Xorshift128+ and Xoroshiro128+ Fail Statistical Tests for Linearity». Computational and Applied Mathematics. 350: 139–142. arXiv:1810.05313. doi:10.1016/j.cam.2018.10.019.
We report that these scrambled generators systematically fail Big Crush—specifically the linear-complexity and matrix-rank tests that detect linearity—when taking the 32 lowest-order bits in reverse order from each 64-bit word.
- ↑ Vigna, Sebastiano. «xoshiro/xoroshiro generators and the PRNG shootout». Consultado em 7 de julho de 2019
- ↑ Blackman, David; Vigna, Sebastiano (2018). «Scrambled Linear Pseudorandom Number Generators». arXiv:1805.01407
- ↑ «xoshiro/xoroshiro generators and the PRNG shootout». prng.di.unimi.it. Consultado em 5 de janeiro de 2023
- ↑ https://prng.di.unimi.it
Erro de citação: Elemento <ref> com nome "brent" definido em <references> não é utilizado no texto da página.
Erro de citação: Elemento <ref> com nome "NR" definido em <references> não é utilizado no texto da página.
Erro de citação: Elemento <ref> com nome "shootout" definido em <references> não é utilizado no texto da página.
Erro de citação: Elemento <ref> com nome "vigna" definido em <references> não é utilizado no texto da página.
Erro de citação: Elemento <ref> com nome "vigna2" definido em <references> não é utilizado no texto da página.
Erro de citação: Elemento <ref> com nome "xsadd" definido em <references> não é utilizado no texto da página.
<ref> com nome "initialization" definido em <references> não é utilizado no texto da página.Leitura adicional[editar | editar código-fonte]
- Brent, Richard P. (julho de 2006). «Some long-period random number generators using shifts and xors». ANZIAM Journal. 48: C188–C202 Lists generators of various sizes with four shifts (two per feedback word).
Erro de citação: Existem etiquetas <ref> para um grupo chamado "lower-alpha", mas não foi encontrada nenhuma etiqueta <references group="lower-alpha"/> correspondente