Qual è il metodo corretto per limitare un numero casuale di pseduo a un intervallo più piccolo?

Question

Qual è il modo migliore per limitare i valori di un PRNG a un intervallo più piccolo? Se si utilizza modulo e il vecchio numero massimo non è equamente divisibile per il nuovo numero massimo si polarizza verso lo 0 tramite (old_max - new_max - 1). Suppongo che il modo migliore sarebbe qualcosa di simile (questo punto è fluttuante, non matematica intero)

random_num = PRNG()/max_orginal_range * max_smaller_range 

ma qualcosa nel mio stomaco mi fa dubitare che il metodo (forse floating point differenze di implementazione e di rappresentanza?).

Il generatore di numeri casuali produrrà risultati coerenti su piattaforme hardware e software e anche il vincolo deve essere rispettato.

Avevo ragione a dubitare dello pseudocodice sopra (ma non per le ragioni che stavo pensando). Il numero answer di MichaelGG mi ha fatto riflettere sul problema in un modo diverso. Posso modellarlo usando numeri più piccoli e testare ogni risultato. Quindi, supponiamo di avere un PRNG che produce un numero casuale compreso tra 0 e 31 e si desidera che l'intervallo più piccolo sia compreso tra 0 e 9. Se si utilizza il modulo si polarizza verso 0, 1, 2 e 3. Se si utilizza lo pseudocodice sopra di voi la preferenza verso 0, 2, 5 e 7. Non penso che ci possa essere un buon modo per mappare un set nell'altro. Il meglio che ho trovato finora è quello di rigenerare i numeri casuali che sono maggiori di old_max/new_max, ma che ha anche problemi profondi (riduzione del periodo, tempo per generare nuovi numeri fino a quando uno è nella giusta fascia, ecc.) .

Penso che potrei aver ingenuamente affrontato questo problema. Potrebbe essere il momento di iniziare una ricerca seria sulla letteratura (qualcuno deve averlo affrontato prima).

Answer 1

So che questa potrebbe non essere una risposta particolarmente utile, ma penso che il modo migliore sarebbe quello di concepire alcuni metodi diversi, quindi provarli qualche milione di volte e controllare i set di risultati.

In caso di dubbio, provare da soli.

EDIT

Va notato che molti linguaggi (come C#) hanno costruito a limitare nelle loro funzioni

int maximumvalue = 20; 
Random rand = new Random(); 

rand.Next(maximumvalue); 

e per quanto possibile, si dovrebbe usare quelli, piuttosto che qualsiasi codice si farebbe scrivi te stesso Non reinventare la ruota.

Answer 2

Se PRNG() genera numeri casuali distribuiti uniformemente, quanto sopra sembra buono. Infatti (se si vuole ridimensionare la media ecc.) Quanto sopra dovrebbe andare bene per tutti gli scopi. Immagino sia necessario chiedersi quale sia l'errore associato al PRNG originale() e se ulteriori manipolazioni si aggiungeranno sostanzialmente a ciò.

In caso di dubbio, genera un set di prova di dimensioni adeguate, e guardare i risultati in Excel o simili (per controllare il media/std.dev ecc per quello che ci si aspetterebbe)

Answer 3

Se si ha accesso a una funzione PRNG (diciamo, Random()) che i numeri verrà generato nel range 0 < = x < 1, si può non solo fare:

random_num = (int) (random() * max_range); 

per darvi numeri nell'intervallo da 0 a max_range?

Answer 4

Ecco come funziona classe Random del CLR, quando limitato (come da Reflector):

long num = maxValue - minValue; 
if (num <= 0x7fffffffL) { 
    return (((int) (this.Sample() * num)) + minValue); 
} 
return (((int) ((long) (this.GetSampleForLargeRange() * num))) + minValue); 

Anche se sei dato un int positiva, non è difficile da ottenere in un doppio. Basta moltiplicare l'int random per (1/maxint). Passare da un int a 32 bit a un doppio dovrebbe fornire una precisione adeguata. (Non ho effettivamente provato un PRNG come questo, quindi potrei mancare qualcosa con i float.)

Answer 5

I generatori di numeri casuali di Psuedo stanno essenzialmente producendo una serie casuale di 1 e 0, che una volta aggiunti l'uno all'altro, sono un numero infinitamente grande nella seconda base. ogni volta che consumi un po 'da te, stai dividendo quel numero per due e mantenendo il modulo. Puoi farlo per sempre senza sprecare un solo bit.

Se avete bisogno di un numero nell'intervallo [0, N), allora avete bisogno dello stesso, ma invece della base due, avete bisogno della base N. È fondamentalmente banale convertire le basi. Consuma il numero di bit necessari, restituisci il resto di quei bit al tuo prng per essere utilizzato la prossima volta che è necessario un numero.