Existe um gerador de números pseudo-aleatórios acessíveis aleatoriamente acessível? (de preferência de código aberto)

https://stackoverflow.com/questions/3019169

26-09-2019
|

Pergunta

Primeiro, existe um gerador de números aleatórios de acesso aleatório, onde você não só poderia gerar sequencialmente números aleatórios como todos nós estamos acostumados, assumindo que o rand100 () sempre gera um valor de 0-100:

for (int i=0;i<5;i++)
   print rand100()

output: 
14
75
36
22
67

mas também acesse aleatoriamente qualquer valor aleatório como:

Rand100 (0) emitiria 14 desde que você não mudasse a semente

Rand100 (3) sempre emitiria 22

Rand100 (4) sempre emitiria 67

e assim por diante...

Na verdade, encontrei um algoritmo de gerador de código aberto que faz isso, mas você não pode alterar a semente. Eu sei que a pseudorandomidão é um campo complexo; Eu não saberia como alterá -lo para adicionar essa funcionalidade.

Existe um gerador de números aleatórios de acesso aleatório semeável, de preferência de código aberto? Ou existe um termo melhor para isso, posso pesquisar no Google para obter mais informações?

Caso contrário, a Parte 2 da minha pergunta seria, existe algum gerador de número de número de números de pseudo -mandoandom semeado e semeado de código aberto de forma confiável para que eu pudesse portá -lo para várias plataformas/idiomas, mantendo uma sequência consistente de valores para cada plataforma para qualquer semente?

Solução

o Família PCG Dos geradores de números PSUDO-Random podem pular para frente e para trás no tempo logarítmico (ou seja, os números de 1000 requer operações O (log (1000))), o que provavelmente é bom o suficiente para ser considerado acesso aleatório. As implementações de referência C e C ++ suportam esse recurso.

A tabela na primeira página do site PCG indica que vários outros geradores podem suportar o salto, mas eu não o vi em nenhuma implementação.

Outras dicas

Eu não ouvi falar de nada assim, mas parece -me que você pode usar um hash decente e escrever uma função de invólucro que assume um valor de semente e seu 'índice' e os executa através da função de hash. Não tenho certeza da aleatoriedade da produção de bits por várias funções de hash criptográfico, mas imagino que alguém tenha dado uma olhada nisso.

Blum Blum Shub é um gerador de números pseudo -aleatórios com uma semente e acesso aleatório a qualquer valor que gera.

Obrigado por todas as respostas e, também, para quem pode acontecer com isso fazendo uma pergunta semelhante, encontrei uma solução que não é exatamente o que pedi, mas encaixa a conta para meus propósitos.

É um ruído perlin classe que pode ser encontrada aqui. Não tenho certeza de quão computacionalmente complexo isso é relativo a um gerador de números aleatórios convencional, o que é uma preocupação, já que uma das plataformas planejadas é o Android. Além disso, o ruído de Perlin não é a mesma coisa que a pseudorandomidão, mas pelo que posso dizer, um alto valor de oitava e/ou frequência deve fornecer aleatoriedade adequada para fins não cristãos, onde o nível estatístico de verdadeira aleatoriedade não é tão importante como a mera aparência de aleatoriedade.

Esta solução permite a semeadura e também permite a amostragem de um conjunto aleatório de qualquer ponto, em outras palavras, aleatoriedade de acesso aleatório.

Aqui está um exemplo de conjunto de aleatoriedade C ++ regular (Rand %200) na coluna esquerda para comparação e ruído de perlin (com o equivalente a %200) à direita:

Ambos foram semeados para 0

Os parâmetros para o ruído de perlin foram

octaves = 8
amplitude = 100 
frequency = 9999
width/height = 10000,100

A ordem de amostragem seqüencial para o ruído de perlin foi simplesmente

for (int i=0;i<24;i++)
    floor(Get(i,i)+100);
//amplitude 100 generates noise between -100 and 100, 
//so adding 100 generates between 0 and 200

Depois de ler um post muito bom de um cara que trabalhava no Google, que respondeu a uma pergunta muito semelhante à sua.

Em resumo, a resposta foi usar uma cifra de bloco com um número aleatório como chave de criptografia e o índice do número que você deseja na sequência como os dados a serem criptografados. Ele mencionou uma cifra que pode funcionar em blocos de qualquer tamanho (em bits), o que é conveniente - eu teria que procurar o blog para encontrar o nome da cifra.

Por exemplo: diga que você deseja um rebaixamento aleatório de números inteiros de 0 a (2^32) -1. Você pode conseguir isso usando uma cifra de bloco que pega 4 bytes de entrada e retorna 4 bytes criptografados. Para iterar sobre a série, primeiro "criptografar" um bloco de valor 0, depois 1, depois 2, etc. Se você deseja apenas o 1 milhão de itens na sequência embaralhada, apenas criptografa o número 1.000.000.

As "seqüências aleatórias" que você usará uma cifra são diferentes do que você obteria usando uma função de hash (como @Michaelburr sugeriu). Usando uma cifra, você pode obter um Permutação aleatória de uma variedade de números inteiros e provar qualquer item nessa permutação em tempo constante. Em outras palavras, os "números aleatórios" não se repetem. Se você usar uma função de hash, os números na sequência podem repetir.

Dito tudo isso, a solução de @Michaelburr é mais apropriada para sua situação, e eu recomendaria que você a use.

Uma maneira de conseguir isso é sintetizar uma quantidade maior de dados aleatórios de um conjunto menor. Uma maneira de fazer isso é ter três matrizes de dados aleatórios pré-gerados. Cada matriz deve ter um número privilegiado de diretores.

Para produzir nossos números aleatórios, imaginamos cada uma dessas almofadas únicas a serem enroladas de forma inigualável e amostrada de forma incremental; Combinamos os dados em cada um deles usando o XOR.

#define PRIME1 7001
#define PRIME2 7013
#define PRIME3 7019

static int pad1[PRIME1];
static int pad2[PRIME2];
static int pad3[PRIME3];

static void random_no_init (void)
{
  static int initialized = 0;
  int i;
  if (initialized)
    return;
  for (i = 0; i < PRIME1; i++) pad1[i] = random ();
  for (i = 0; i < PRIME2; i++) pad2[i] = random ();
  for (i = 0; i < PRIME3; i++) pad3[i] = random ();

  initialized = 1;
}

int random_no (int no)
{
   random_no_init ();
   return pad1[no % PRIME1] ^ pad2[no % PRIME2] ^ pad3[no % PRIME3];
}

A amostra de código acima mostra um exemplo simples que gera 344618953247 inteiros acessíveis aleatoriamente. Para garantir resultados reprodutíveis entre as execuções, você deve fornecer a um gerador de números aleatórios uma semente. Um sistema mais complexo construído sobre o mesmo princípio com variação de sementes com base na escolha de diferentes números pode ser encontrado em http://git.gnome.org/browse/gegl/tree/gegl/gegl-random.c

Todos os geradores que eu conhecem são iterativos. Portanto, qualquer 'acesso aleatório' envolveria o cálculo de todos os valores do primeiro ao que você solicita.

O mais próximo que você pode chegar é pegar uma semente fixa, hash e depois hash o valor do índice, usando algo que se mistura com muito entusiasmo.

Ou gerar uma longa lista deles e guarde -os.

Dê uma olhada nesta patente: gerador de número aleatório de acesso aleatóriohttps://patents.google.com/patent/us4791594

Ele usa um esquema de scrambling de vários estágios para gerar uma sequência de números de pseudo-número capaz de ser acessada aleatoriamente.

A idéia é usar o endereço de entrada como bits de controle para embarcar em vários números de sementes e, em seguida, xorar os resultados para produzir uma saída e, em seguida, um segundo passe de luta usando o resultado gerado a partir da passagem anterior.

Licenciado em: CC-BY-SA com atribuição

Não afiliado a StackOverflow