esiste una cosa come un generatore di numeri pseudo-casuali casuale accessibile? (Preferibilmente open-source)

Question

Prima di tutto, c'è una cosa come un accesso casuale generatore di numeri casuali, dove si poteva non solo in modo sequenziale generare numeri casuali, come siamo tutti abituati, assumendo rand100 () genera sempre un valore da 0-100:

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

output: 
14
75
36
22
67

, ma anche l'accesso in modo casuale ogni valore casuale come:

rand100 (0) output sarebbe 14 fino a quando non ha cambiato il seme

rand100 (3) sarebbe sempre uscita 22

rand100 (4) sarebbe sempre uscita 67

e così via ...

In realtà ho trovato un algoritmo generatore open-source che fa questo, ma non è possibile modificare il seme. So che pseudorandomness è un campo complesso; Io non saprei come modificarlo per aggiungere tale funzionalità.

C'è un accesso casuale generatore di numeri casuali seedable, preferibilmente open source? o c'è un termine migliore per questo posso google per maggiori informazioni?

In caso contrario, la parte 2 della mia domanda sarebbe, c'è qualche open source convenzionale seedable numeri pseudo-casuali in modo affidabile casuale in modo ho potuto portarlo a più piattaforme / linguaggi, pur mantenendo una sequenza coerente di valori per ogni piattaforma per ogni seme ?

Answer 1

Il PCG famiglia di generatori di numeri pseudo-casuali può saltare avanti e indietro nel tempo logaritmico (ie saltare avanti 1.000 numeri richiede O (log (1000)) operazioni), che probabilmente è buono abbastanza per essere considerato accesso casuale. I C e C ++ implementazioni di riferimento sia per supportare questa funzione.

La tabella sulla prima pagina del sito PCG indica che un certo numero di altri generatori in grado di supportare jump-avanti, ma io non l'ho visto in qualsiasi implementazioni.

Answer 2

Non ho sentito parlare di una cosa del genere, ma mi sembra che si potrebbe prendere usa un hash decente e scrivere una funzione wrapper che prende un valore di seme e la tua 'indice', e li attraversa la funzione hash. Non sono sicuro della casualità dell'uscita bit da varie funzioni di hash crittografico, ma immagino che qualcuno ha preso uno sguardo a questo.

Answer 3

Blum Blum Shub è un generatore di numeri pseudocasuali con un seme e accesso casuale a un valore qualsiasi genera.

Answer 4

Grazie per tutte le risposte, e anche, per tutti coloro che potrebbe accadere su questo fare una domanda simile, ho trovato una soluzione che non è esattamente quello che ho chiesto, ma si adatta il disegno di legge per i miei scopi.

Si tratta di una Perlin classe rumore che può essere trovato qui . Io non sono sicuro di come computazionalmente complesso questo è relativo ad un generatore di numeri casuali convenzionale, che è una preoccupazione, dal momento che una delle piattaforme previsto è Android. Inoltre, Perlin rumore non è la stessa cosa di pseudorandomness, ma da quello che posso dire, un alto ottave e / o il valore di frequenza dovrebbe fornire casualità adatto per scopi non-crittografici, dove il livello statistico della vera casualità non è così importante come la mera apparenza di casualità.

Questa soluzione permette semina, e permette anche il campionamento di un insieme casuale da qualsiasi punto, in altre parole, l'accesso casuale casualità.

qui un esempio insieme di c ++ regolare casualità (Rand% 200) nella colonna di sinistra per il confronto, e Perlin rumore (con l'equivalente di 200%) a destra:

91 , 100
48 , 97
5 , 90
93 , 76
197 , 100
97 , 114
132 , 46
190 , 67
118 , 103
78 , 96
143 , 110
187 , 108
139 , 79
69 , 58
156 , 81
123 , 128
84 , 98
15 , 105
178 , 117
10 , 82
13 , 110
182 , 56
10 , 96
144 , 64
133 , 105

entrambi sono state seminate a 0

i parametri per il disturbo Perlin erano

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

l'ordine di campionamento sequenziale per il rumore Perlin era semplicemente

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

Answer 5

Una volta ho letto un ottimo post sul blog da un ragazzo che ha usato per lavorare a Google, che ha risposto ad una domanda molto simile al tuo.

In breve, la risposta è stata di utilizzare un cifrario a blocchi con un numero casuale come la chiave di crittografia, e l'indice del numero che si desidera nella sequenza in quanto i dati da cifrare. Ha citato una cifra che può lavorare su blocchi di qualsiasi dimensione (in bit), che è conveniente - avrei dovuto cercare il blog per trovare il nome del cifrario

.

Ad esempio: dire che si desidera un rimescolamento casuale di numeri interi da 0 a (2 ^ 32) -1. È possibile ottenere che utilizza un cifrario a blocchi che prende in ingresso 4 byte, e ritorna 4 byte crittografati. Per scorrere la serie, prima "cifrare" un blocco di valore 0, 1, poi 2, ecc Se si vuole solo l'elemento 1 milionesimo nella sequenza già mescolato, basta criptare il numero 1.000.000.

Le "sequenze casuali" si otterrà utilizzando un cifrario sono diversi da quello che si otterrebbe con una funzione di hash (come suggerito @MichaelBurr). Utilizzando un cifrario, è possibile ottenere un permutazione casuale di una serie di numeri interi, e assaggiare qualsiasi elemento che permutazione in tempo costante. In altre parole, i "numeri casuali" non si ripeteranno. Se si utilizza una funzione di hash, i numeri nella sequenza possono ripetere.

Detto tutto questo, la soluzione di @ MichaelBurr è più appropriato per la situazione, e lo consiglio lo si utilizza.

Answer 6

Un modo per raggiungere questo obiettivo è quello di sintetizzare una maggiore quantità di dati casuali da un insieme più piccolo. Un modo per farlo è quello di avere tre matrici di dati casuali pre-generati. Ogni array dovrebbe avere numero primo di interi.

Per produrre i nostri numeri casuali immaginiamo ognuno di questi one-time pad ad essere passato inifintely e campionate in modo incrementale; uniamo i dati in ciascuno di essi utilizzando 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];
}

Il codice di esempio sopra mostra un semplice esempio che produce 344618953247 entires casualmente accessibili. Per garantire risultati riproducibili tra piste, è necessario fornire un generatore di numeri casuali con un seme. Un sistema più complesso costruito sullo stesso principio con variazione seme basato su raccogliendo diversi numeri primi possono essere trovate all'indirizzo http://git.gnome.org/browse/gegl/tree/gegl/gegl-random.c

Answer 7

Tutti i generatori io sappia sono iterativo. Quindi, qualsiasi 'accesso casuale' coinvolgerebbe il calcolo di tutti i valori dalla prima a quella che si chiede.

Il più vicino si potrebbe venire è quello di prendere un seme fisso, hash, e poi hash il valore dell'indice, utilizzando qualcosa che mescola realtà con entusiasmo.

o generare una lunga lista di loro e memorizzarlo.

Answer 8

dare un'occhiata a questo brevetto: Ad accesso casuale pseudo generatore di numeri casuali https://patents.google.com/patent/US4791594

Si utilizza uno schema di scrambling po 'più stadi per generare una sequenza pseudo numero che è in grado di accedere in modo casuale.

L'idea è di utilizzare l'indirizzo di ingresso come bit di controllo di numeri scramble molteplici semi e quindi XOR i risultati per produrre un'uscita, poi un secondo passaggio di rimescolamento impiegando il risultato generato dal passo precedente.