PRNG dipendente dalle argomentazioni

Question

Sono interessato a una funzione rand(x, y, seed) che restituisce (pseudo) numeri casuali in base ai suoi argomenti, con le seguenti proprietà:

.

1. Il valore restituito dovrebbe dipendere dai suoi 3 argomenti e non dipendono dalla quantità di volte rand è stato chiamato finora. Ad esempio, assumendo queste chiamate, in questo ordine:

   .

   rand(0, 0, 123) = 1
   rand(0, 1, 123) = 2
   rand(0, 2, 123) = 3
   

   .

   Quindi chiamare rand con gli stessi argomenti, ma in un ordine diverso, dovremmo ottenere gli stessi valori. Ad esempio:

   .

   rand(0, 1, 123) = 2
   rand(0, 2, 123) = 3
   rand(0, 0, 123) = 1
   

   .

   La funzione dovrebbe avere le solite proprietà di un bene (decente, non ho davvero bisogno di niente molto elegante) PRNG: grande periodo, distribuzione uniforme ecc. Restituire interi positivi che si adattano a un int. Può anche andare più in alto se vuoi.

   Assumere questi numeri verranno utilizzati per generare una matrice. Quindi cambiare il seme dovrebbe assicurarsi che la matrice generata sia il più diverso possibile da matrici generate da altri semi. Questo dovrebbe accadere per un numero più grande possibile di semi: non voglio ripetere le matrici.

   Se aiuta, i miei semi saranno sempre il timestamp Unix in millisecondi (può essere in pochi secondi se questo rende più facile in qualche modo). Tutti gli argomenti possono arrivare fino a 32 bit con interni firmati, ma lavorare con valori a 64 bit all'interno della funzione non è un problema.

   Quale funzione potrei usare per questo?

   Cosa ho pensato a:

   rumore perlin sembra fare un po 'di quello che voglio, ma Non ho idea di quanto sia adatto davvero come PRNG, in particolare la distribuzione-saggio. Non sono sicuro di quanto sia efficiente, dal momento che i miei parametri (x, y) saranno piuttosto casuali, e non posso preptentarlo per tutti loro.

   Ho anche esaminato la seguente funzione:

   p = 1400328593
   rand(x, y, seed) = (x * x * seed + y * seed * seed + seed * x * y + seed) mod p
                    = (seed * (x * x + y * seed + x * y + 1)) mod p
   

   .

   Questo sembra per generare numeri abbastanza buoni. Basandosi sui miei test (molto deboli), sembrano anche distribuiti molto bene. Test del periodo è più difficile però, non l'ho fatto.

   Aggiornamento:

   Ecco l'output di ENT per la funzione di cui sopra, con time(NULL) in c come seme e valori generati Per (x, y) in {0 ... 999} x {0 ... 999}:

   .

   Entropia= 3.312850 bit per byte.

   La compressione ottimale ridurrebbe la dimensione di questo file byte 9207076 di 58 percento.

   La distribuzione di Chi Square per 9207076 campioni è 229710872.43, e supererebbe casualmente questo valore inferiore allo 0,01 percento dei tempi.

   Il valore medio aritmetico dei data byte è 52.3354 (127,5= casuale). Monte. Il valore Carlo per PI è 4.000000000 (errore 27.32 percento). Seriale Il coefficiente di correlazione è 0,036131 (totalmente non correlato= 0,0).

   È abbastanza buono nella pratica (in teoria, i test di cui sopra suggeriscono che non è affatto buono), o c'è qualcosa di ben noto che dovrei usare?

Answer 1

Sembra che tu voglia una funzione hash.Scegli uno sicuro come SHA1 se non è troppo inefficiente, dal momento che è garantito avere buone caratteristiche di distribuzione;Altrimenti, è possibile utilizzare una funzione hash comune come FNV.Basta usare il tuo seme e le coordinate come dati di input e l'hash come valore casuale.

Answer 2

Potresti provare a utilizzare Blum Blum Shub . Ha la proprietà che puoi calcolare direttamente il valore n'th della serie, che sembra appropriato per la tua situazione. Ci vogliono tre parametri, P, Q e X0. P e Q sono Prime e X0 è in modo rilassante in modo relativo a P e Q. Quindi i tuoi argomenti X e Y potrebbero essere usati per trovare le prime X'th e Y'th, allora sarebbero adatti per P e Q, e quindi è possibile utilizzare il terzo parametro per trovare un valore adatto per X0. Questo è un po 'noioso, e Blum Blum Shub è lento poiché è un RNG crittografico, ma se non hai davvero bisogno di velocità, allora funzionerebbe e non sarebbe terribilmente difficile da implementare.

Un altro modo per farlo sarebbe quello di prendere un rng come Cmwc e riempire la posizione I'th del generatore con qualcosa come x + y ^ i + seed ^ (2i), eseguire il generatore per un po '(forse un numero di volte uguale al numero di Valuta i negozi IT), quindi tira un valore di esso.

Se si desidera utilizzare un CMWC puoi guardare un'implementazione che ho su GitHub qui , e Valori per la costruzione del generatore con periodi noti qui .