Perché 1103515245 viene utilizzato in rand?

Question

Sto parlando di this sorprendentemente semplice implementazione di rand() dallo standard C:

static unsigned long int next = 1; 

int rand(void) /* RAND_MAX assumed to be 32767. */ 
{ 
    next = next * 1103515245 + 12345; 
    return (unsigned)(next/65536) % 32768; 
} 

Da this Wikipedia article sappiamo che il moltiplicatore a (nel codice sopra a = 1103515245) deve soddisfare solo 2 condizioni:

1. a - 1 è divisibile per tutti i fattori primi di m.
   (nel nostro caso m = 2^32, dimensione del int, quindi m ha un solo fattore primo = 2)
2. a - 1 è un multiplo di 4 se m è un multiplo di 4.
   (32768 è multiplo di 4, e 1103515244 troppo)

Perché hanno scelto come uno strano, difficile da ricordare, "l'uomo, io sono stufo di questi numeri casuali, scrivere qualunque" il numero, come 1.103.515,245 mila?

Forse ci sono alcuni saggi motivi, che questo numero è in qualche modo migliore rispetto agli altri?

Ad esempio, perché non impostare a = 20000000001? È più grande, dall'aspetto fresco e più facile da ricordare.

Answer 1

Se si utilizza un LCG per disegnare punti sullo spazio dimensionale D, si trovano su al massimo (d! M) ^{/ _d} iperpiani. Questo è un difetto noto degli LCG.

Se non si seleziona attentamente a e m (oltre la condizione di piena periodicità), potrebbero trovarsi su un numero di piani inferiore rispetto a quello. Questi numeri sono stati selezionati da quello che viene chiamato il test dello spettro .

Il "test spettrale" (il nome deriva dalla teoria dei numeri) è la distanza massima tra gli iperplani consecutivi su cui giacciono le distribuzioni articolari bidimensionali. Vuoi che sia il più piccolo possibile per più d che puoi testare.

Vedere this paper per una revisione storica sull'argomento. Nota che il generatore che citi è menzionato nel documento (come ANSIC) e determinato a non essere molto buono. I 16 bit di ordine elevato sono accettabili, tuttavia, ma molte applicazioni avranno bisogno di più di 32768 valori distinti (come indicato nei commenti, il periodo è in effetti 2^31 - le condizioni per la periodicità completa nel collegamento di Wikipedia sono probabilmente solo necessarie).

Il codice sorgente originale nel documento ANSI non ha preso l'ordine alto 16 bit, ottenendo un generatore molto povera che è facile da uso improprio (rand() % n è quello che la gente pensa prima di disegnare un numero compreso tra 0 e n, e questo produce qualcosa di molto non casuale in questo caso).

Vedere anche la discussione su LCG in Numerical Recipes. Citando:

Peggio ancora, molti primi generatori hanno fatto particolarmente male le scelte per me e a. Una infame routine di questo tipo, RANDU, con un = 65539 e m = 231, era diffusa su computer mainframe IBM per molti anni, e ampiamente copiata su altri sistemi. Uno di noi ricorda come uno studente uno studente che produceva un complotto "casuale" con solo 11 piani e veniva detto dal consulente di programmazione del suo centro di computer che aveva usato male il codice il generatore di numeri casuali: "Garantiamo che ogni numero è casuale singolarmente, ma non garantiamo che più di uno di essi sia uguale a casuale ". Ciò riduce la nostra formazione universitaria di almeno un anno!

Answer 2

Ricordare che rand() è un'approssimazione di uniform distribution. Questi numeri vengono utilizzati perché sono stati testati per dimostrare che generano una distribuzione dall'aspetto più uniforme.

Data la moltitudine di coppie di numeri interi senza segno nell'intervallo rappresentabile, dubito che qualcuno li abbia provati tutti con tutti i semi validi. Se pensi di avere una scelta migliore di parametri, provalo! Hai il codice, basta calcolare i parametri del LCG ed eseguire test. Generare un gruppo di numeri (ad esempio 10 milioni), calcolare un istogramma dei numeri generati e tracciare quello per esaminare la distribuzione.

modificare Se siete interessati a sviluppare un generatore di numeri pseudo-casuali per l'uso in applicazioni reali, vi consiglio di leggere sul considerevole letteratura sull'argomento. Il "consiglio" di cui sopra è solo suggerito per aiutare a dimostrare che la scelta di parametri arbitrari "più grandi, di bell'aspetto e più facili da ricordare" darà una distribuzione molto scarsa. /modificare

Inoltre, si tratta di una funzione di libreria e non ho mai visto un programma che utilizza la versione della libreria standard rand() per ricordare i parametri del suo LCG.

Answer 3

Questo numero sembra speciale, è solo tra due numeri primi: P.

Ora parlando seriamente, per vedere se è una buona scelta, basta guardare l'output. Dovreste vedere risultati molto diversi anche se girate un singolo bit.

Inoltre, considera quanta prevedibilità ti aspetti ... che l'implementazione è terribile, potresti considerare un'alternativa più solida ma semplice, come FNV-1a.

Answer 4

calcoli I primi tendevano ad occuparsi con i bit e byte e trucchi giocato con i registri per ridurre al minimo byte di codice (prima linea c'erano byte)

ho trovato un solo indizio ragionevole di seguito:

L'output di questo generatore non è molto casuale. Se usiamo il generatore di campioni sopra elencato, la sequenza di 16 byte chiave sarà altamente non casuale. Ad esempio, si scopre che il bit basso di ciascuna uscita successiva di rand() si alternerà (ad es. 0,1,0,1,0,1, ...). Capisci perché? Il bit basso di x * 1103515245 è lo stesso del bit basso di x, e quindi l'aggiunta di 12345 capta semplicemente il bit più basso. Quindi il bit basso si alterna. Ciò limita l'insieme delle possibili chiavi a sole 2113 possibilità, molto meno del valore desiderato di 2128.

http://inst.eecs.berkeley.edu/~cs161/fa08/Notes/random.pdf

E due risposte ragionevoli:

Migliorare un povero generatore di numeri casuali (1976) da baie, Durham Bays, Carter, SD Durham

http://en.wikipedia.org/wiki/TRNG