Identificazione e comprensione di questo PRNG

Question

Identificazione e comprensione di questo PRNG

#1 da (5 voti)
#2 da (4 voti)

2

Ho questo generatore di numeri casuali, e l'ho avuto per un po 'di tempo, ma nonostante quanto lo uso non lo capisco davvero.

public static int Random(int x)
{
    x = x + seed;
    x = (x << 13) ^ x;
    return (x * (x * x * 15731 + 789221) + 1376312589) & 0x7fffffff;
}

Funziona molto bene per i miei scopi: prende un numero intero e sputa un altro intero casuale. Non si basa su uno stato, né fa affidamento sul suo ultimo output come tanti generatori lineari congruenti.

Che tipo di generatore è questo? Vorrei alcuni termini che posso comprendere su Google e saperne di più. A quale famiglia di PRNG appartiene? Come / perché funziona?

random

posta Mavichist 23.06.2016 - 16:20

fonte

2 risposte

4

Per essere chiari, questo non produce un numero casuale. Quello che fa (mi aspetto) è produrre numeri molto diversi per interi che sono vicini l'uno all'altro. Il modo in cui lo fa è facendo traboccare l'int creando numeri più grandi (valore assoluto) che l'intervallo a 32 bit può supportare almeno una volta. Lo shift e xor sembrano espandere l'input su 32 bit e le moltiplicazioni e le aggiunte lo fanno traboccare e migliorare la distribuzione. Non sono un matematico ma credo che questo possa essere descritto come un caotico funzione di .

Ho eseguito alcuni numeri tramite Java con seed di 13. Sembra abbastanza ben distribuito:

Anchealivellolocale:

risposta data 23.06.2016 - 16:43

fonte

Leggi altre domande sui tag random

Quale potrebbe essere un motivo per lo sviluppatore di applicazioni server multipiattaforma per far funzionare la sua app in più processi? È una cattiva pratica usare le stringhe JSON come chiavi degli oggetti?

score 5 · Accepted Answer

Un po 'di curiosità su Google suggerisce che si tratta di un Registra spostamento lineare feedback o LFSR. Apparentemente è comunemente usato per produrre rumore per gli shader.

Ulteriori letture
Generatore di numeri casuali di rumore e pseudo in GLSL
Registro a scorrimento lineare di feedback