Espandi un intervallo casuale compreso tra 1-5 e 1-7

Data una funzione che produce un numero intero casuale nell’intervallo da 1 a 5, scrivere una funzione che produce un numero intero casuale nell’intervallo da 1 a 7.

  1. Qual è una soluzione semplice?
  2. Qual è una soluzione efficace per ridurre l’utilizzo della memoria o eseguire su una CPU più lenta?

Questo è equivalente alla soluzione di Adam Rosenfield, ma potrebbe essere un po ‘più chiaro per alcuni lettori. Suppone che rand5 () sia una funzione che restituisce un numero intero statisticamente casuale compreso tra 1 e 5 inclusi.

 int rand7() { int vals[5][5] = { { 1, 2, 3, 4, 5 }, { 6, 7, 1, 2, 3 }, { 4, 5, 6, 7, 1 }, { 2, 3, 4, 5, 6 }, { 7, 0, 0, 0, 0 } }; int result = 0; while (result == 0) { int i = rand5(); int j = rand5(); result = vals[i-1][j-1]; } return result; } 

Come funziona? Pensala in questo modo: immagina di stampare questa matrice a doppia dimensione su carta, fissandola a un bersaglio per le freccette e lanciarla a caso a freccette. Se si preme un valore diverso da zero, è un valore statisticamente casuale compreso tra 1 e 7, in quanto vi è un numero uguale di valori diversi da zero tra cui scegliere. Se colpisci uno zero, continua a tirare il dardo fino a quando non colpisci un non-zero. Questo è ciò che sta facendo questo codice: gli indici i e j selezionano a caso una posizione sul tabellone per le freccette, e se non otteniamo un buon risultato, continuiamo a lanciare freccette.

Come ha detto Adam, questo può durare per sempre nel peggiore dei casi, ma statisticamente il caso peggiore non accade mai. 🙂

Non esiste una soluzione (esattamente corretta) che funzioni in un lasso di tempo costante, poiché 1/7 è un decimale infinito in base 5. Una soluzione semplice sarebbe quella di utilizzare il campionamento del rifiuto, ad esempio:

 int i; do { i = 5 * (rand5() - 1) + rand5(); // i is now uniformly random between 1 and 25 } while(i > 21); // i is now uniformly random between 1 and 21 return i % 7 + 1; // result is now uniformly random between 1 and 7 

Questo ha un tempo di esecuzione previsto di 25/21 = 1.19 iterazioni del ciclo, ma c’è una probabilità infinitamente piccola di loop per sempre.

Vorrei aggiungere un’altra risposta, oltre alla mia prima risposta . Questa risposta tenta di ridurre al minimo il numero di chiamate a rand5() per chiamata a rand7() , per massimizzare l’utilizzo della casualità. Cioè, se consideri la casualità come una risorsa preziosa, vogliamo utilizzarne il più ansible, senza buttare via pezzi casuali. Questa risposta ha anche alcune somiglianze con la logica presentata nella risposta di Ivan .

L’ entropia di una variabile casuale è una quantità ben definita. Per una variabile casuale che assume N stati con probabilità uguali (una distribuzione uniforms), l’entropia è log 2 N. Quindi, rand5() ha circa 2.32193 bit di entropia e rand7() ha circa 2.80735 bit di entropia. Se speriamo di massimizzare il nostro uso della casualità, dobbiamo usare tutti i 2.32193 bit di entropia da ogni chiamata a rand5() , e applicarli alla generazione di 2.80735 bit di entropia necessari per ogni chiamata a rand7() . Il limite fondamentale, quindi, è che non possiamo fare di meglio di log (7) / log (5) = 1.20906 chiamate a rand5() per chiamata a rand7() .

Note a margine: tutti i logaritmi in questa risposta saranno di base 2 se non diversamente specificato. rand5() verrà assunto per restituire i numeri nell’intervallo [0, 4] e rand7() verrà utilizzato per restituire i numeri nell’intervallo [0, 6]. Regolare gli intervalli su [1, 5] e [1, 7] rispettivamente è banale.

Quindi come lo facciamo? Generiamo un numero reale casuale infinitamente preciso tra 0 e 1 (fingiamo per il momento di poter effettivamente calcolare e memorizzare un numero infinitamente preciso – lo ripareremo in seguito). Possiamo generare un numero di questo tipo generando le sue cifre nella base 5: selezioniamo il numero casuale 0. a 1 a 2 a 3 …, dove ogni cifra a è scelta da una chiamata a rand5() . Ad esempio, se il nostro RNG ha scelto un i = 1 per tutti i , ignorando il fatto che non è molto casuale, ciò corrisponderebbe al numero reale 1/5 + 1/5 2 + 1/5 3 + .. . = 1/4 (sum di una serie geometrica).

Ok, quindi abbiamo scelto un numero reale casuale tra 0 e 1. Ora sostengo che un numero casuale così distribuito è uniforms. Intuitivamente, questo è facile da capire, dal momento che ogni cifra è stata selezionata in modo uniforms e il numero è infinitamente preciso. Tuttavia, una prova formale di questo è un po ‘più coinvolta, poiché ora abbiamo a che fare con una distribuzione continua invece che con una distribuzione discreta, quindi dobbiamo dimostrare che la probabilità che il nostro numero si trovi in ​​un intervallo [ a , b ] sia uguale a lunghezza di tale intervallo, b - a . La dimostrazione è lasciata come esercizio per il lettore =).

Ora che abbiamo un numero reale casuale selezionato in modo uniforms nell’intervallo [0, 1], dobbiamo convertirlo in una serie di numeri casuali uniforms nell’intervallo [0, 6] per generare l’output di rand7() . Come facciamo questo? Proprio l’opposto di ciò che abbiamo appena fatto – lo convertiamo in un decimale infinitamente preciso in base 7, e quindi ogni 7 cifre di base corrisponderà a un’uscita di rand7() .

Prendendo esempio da prima, se il nostro rand5() produce un stream infinito di 1, il nostro numero reale casuale sarà 1/4. Conversione da 1/4 a base 7, otteniamo il decimale infinito 0.15151515 …, quindi produrremo come output 1, 5, 1, 5, 1, 5, ecc.

Ok, quindi abbiamo l’idea principale, ma abbiamo ancora due problemi: non possiamo effettivamente calcolare o memorizzare un numero reale infinitamente preciso, quindi come possiamo gestirne solo una parte limitata? In secondo luogo, come possiamo convertirlo in base 7?

Un modo per convertire un numero compreso tra 0 e 1 nella base 7 è il seguente:

  1. Moltiplicare per 7
  2. La parte integrale del risultato è la prossima cifra di base 7
  3. Sottrarre la parte integrale, lasciando solo la parte frazionaria
  4. Vai al passaggio 1

Per affrontare il problema della precisione infinita, calcoliamo un risultato parziale e memorizziamo anche un limite superiore su quale potrebbe essere il risultato. Cioè, supponiamo di aver chiamato rand5() due volte e che sia ritornato 1 entrambe le volte. Il numero che abbiamo generato finora è 0.11 (base 5). Qualunque sia il resto della serie infinita di chiamate a rand5() , il numero reale casuale che stiamo generando non sarà mai più grande di 0.12: è sempre vero che 0.11 ≤ 0.11xyz … <0.12.

Quindi, tenendo traccia del numero attuale finora, e del valore massimo che potrebbe mai prendere, convertiamo entrambi i numeri nella base 7. Se sono d’accordo sulle prime cifre k , allora possiamo tranquillamente emettere le successive cifre k – indipendentemente da quale sia il stream infinito delle cifre di base 5, esse non influenzeranno mai le successive cifre k della rappresentazione di base 7!

E questo è l’algoritmo – per generare il prossimo output di rand7() , generiamo solo il numero di cifre di rand5() poiché è necessario assicurarsi di conoscere con certezza il valore della prossima cifra nella conversione del numero reale casuale alla base 7. Ecco un’implementazione Python, con un’imbracatura di test:

 import random rand5_calls = 0 def rand5(): global rand5_calls rand5_calls += 1 return random.randint(0, 4) def rand7_gen(): state = 0 pow5 = 1 pow7 = 7 while True: if state / pow5 == (state + pow7) / pow5: result = state / pow5 state = (state - result * pow5) * 7 pow7 *= 7 yield result else: state = 5 * state + pow7 * rand5() pow5 *= 5 if __name__ == '__main__': r7 = rand7_gen() N = 10000 x = list(next(r7) for i in range(N)) distr = [x.count(i) for i in range(7)] expmean = N / 7.0 expstddev = math.sqrt(N * (1.0/7.0) * (6.0/7.0)) print '%d TRIALS' % N print 'Expected mean: %.1f' % expmean print 'Expected standard deviation: %.1f' % expstddev print print 'DISTRIBUTION:' for i in range(7): print '%d: %d (%+.3f stddevs)' % (i, distr[i], (distr[i] - expmean) / expstddev) print print 'Calls to rand5: %d (average of %f per call to rand7)' % (rand5_calls, float(rand5_calls) / N) 

Si noti che rand7_gen() restituisce un generatore, poiché ha uno stato interno che comporta la conversione del numero in base 7. Il test harness chiama next(r7) 10000 volte per produrre 10000 numeri casuali, quindi misura la loro distribuzione. Viene utilizzato solo un numero intero di matematica, quindi i risultati sono esattamente corretti.

Si noti inoltre che i numeri qui diventano molto grandi, molto veloci. I poteri di 5 e 7 crescono rapidamente. Quindi, le prestazioni inizieranno a peggiorare notevolmente dopo aver generato un sacco di numeri casuali, a causa dell’aritmetica bignum. Ma ricorda qui, il mio objective era massimizzare l’uso di bit casuali, non per massimizzare le prestazioni (anche se questo è un objective secondario).

In una sola esecuzione, ho effettuato 12091 chiamate a rand5() per 10000 chiamate a rand7() , ottenendo il numero minimo di chiamate di registro (7) / registro (5) in media a 4 cifre significative e l’output risultante era uniforms.

Per portare questo codice in una lingua che non ha interi interi arbitrariamente grandi, devi pow5 i valori di pow5 e pow7 al valore massimo del tuo tipo integrale nativo – se diventano troppo grandi, quindi resettare tutto e ricominciare. Ciò aumenterà leggermente il numero medio di chiamate a rand5() per chiamata a rand7() , ma si spera che non dovrebbe aumentare troppo anche per interi a 32 o 64 bit.

(Ho rubato la risposta di Adam Rosenfeld e l’ho fatto girare circa il 7% più velocemente.)

Supponiamo che rand5 () restituisca uno di {0,1,2,3,4} con distribuzione uguale e l’objective sia return {0,1,2,3,4,5,6} con distribuzione uguale.

 int rand7() { i = 5 * rand5() + rand5(); max = 25; //i is uniform among {0 ... max-1} while(i < max%7) { //i is uniform among {0 ... (max%7 - 1)} i *= 5; i += rand5(); //i is uniform {0 ... (((max%7)*5) - 1)} max %= 7; max *= 5; //once again, i is uniform among {0 ... max-1} } return(i%7); } 

Stiamo tenendo traccia del valore massimo che il loop può fare nella variabile max . Se il reult fino ad ora è tra max% 7 e max-1 allora il risultato sarà uniformsmente distrubuito in quell'intervallo. In caso contrario, utilizzeremo il resto, che è casuale tra 0 e max% 7-1, e un'altra chiamata a rand () per creare un nuovo numero e un nuovo massimo. Quindi iniziamo di nuovo.

Modifica: Aspettatevi il numero di volte in cui chiamare rand5 () è x in questa equazione:

 x = 2 * 21/25 + 3 * 4/25 * 14/20 + 4 * 4/25 * 6/20 * 28/30 + 5 * 4/25 * 6/20 * 2/30 * 7/10 + 6 * 4/25 * 6/20 * 2/30 * 3/10 * 14/15 + (6+x) * 4/25 * 6/20 * 2/30 * 3/10 * 1/15 x = about 2.21 calls to rand5() 

Algoritmo:

7 può essere rappresentato in una sequenza di 3 bit

Usa rand (5) per riempire a caso ogni bit con 0 o 1.
Ad esempio: call rand (5) e

se il risultato è 1 o 2, riempire il bit con 0
se il risultato è 4 o 5, riempire il bit con 1
se il risultato è 3, quindi ignoralo e fallo di nuovo (rifiuto)

In questo modo possiamo riempire a caso 3 bit con 0/1 e ottenere così un numero compreso tra 1 e 7.

EDIT: Questa sembra la risposta più semplice ed efficiente, quindi ecco un codice per questo:

 public static int random_7() { int returnValue = 0; while (returnValue == 0) { for (int i = 1; i <= 3; i++) { returnValue = (returnValue << 1) + random_5_output_2(); } } return returnValue; } private static int random_5_output_2() { while (true) { int flip = random_5(); if (flip < 3) { return 0; } else if (flip > 3) { return 1; } } } 
 int randbit( void ) { while( 1 ) { int r = rand5(); if( r <= 4 ) return(r & 1); } } int randint( int nbits ) { int result = 0; while( nbits-- ) { result = (result<<1) | randbit(); } return( result ); } int rand7( void ) { while( 1 ) { int r = randint( 3 ) + 1; if( r <= 7 ) return( r ); } } 
 int ans = 0; while (ans == 0) { for (int i=0; i<3; i++) { while ((r = rand5()) == 3){}; ans += (r < 3) >> i } } 
 rand7() = (rand5()+rand5()+rand5()+rand5()+rand5()+rand5()+rand5())%7+1 

Modifica: non funziona abbastanza. È spento di circa 2 parti su 1000 (presupponendo un rand perfetto5). I secchi ottengono:

 value Count Error% 1 11158 -0.0035 2 11144 -0.0214 3 11144 -0.0214 4 11158 -0.0035 5 11172 +0.0144 6 11177 +0.0208 7 11172 +0.0144 

Passando a una sum di

 n Error% 10 +/- 1e-3, 12 +/- 1e-4, 14 +/- 1e-5, 16 +/- 1e-6, ... 28 +/- 3e-11 

sembra guadagnare un ordine di grandezza ogni 2 aggiunti

BTW: la tabella degli errori di cui sopra non è stata generata tramite campionamento ma dalla seguente relazione di ricorrenza:

p[x,n] è il numero di modi in cui output=x può accadere dato n chiamate a rand5 .

  p[1,1] ... p[5,1] = 1 p[6,1] ... p[7,1] = 0 p[1,n] = p[7,n-1] + p[6,n-1] + p[5,n-1] + p[4,n-1] + p[3,n-1] p[2,n] = p[1,n-1] + p[7,n-1] + p[6,n-1] + p[5,n-1] + p[4,n-1] p[3,n] = p[2,n-1] + p[1,n-1] + p[7,n-1] + p[6,n-1] + p[5,n-1] p[4,n] = p[3,n-1] + p[2,n-1] + p[1,n-1] + p[7,n-1] + p[6,n-1] p[5,n] = p[4,n-1] + p[3,n-1] + p[2,n-1] + p[1,n-1] + p[7,n-1] p[6,n] = p[5,n-1] + p[4,n-1] + p[3,n-1] + p[2,n-1] + p[1,n-1] p[7,n] = p[6,n-1] + p[5,n-1] + p[4,n-1] + p[3,n-1] + p[2,n-1] 

Quanto segue produce una distribuzione uniforms su {1, 2, 3, 4, 5, 6, 7} usando un generatore di numeri casuali che produce una distribuzione uniforms su {1, 2, 3, 4, 5}. Il codice è disordinato, ma la logica è chiara.

 public static int random_7(Random rg) { int returnValue = 0; while (returnValue == 0) { for (int i = 1; i <= 3; i++) { returnValue = (returnValue << 1) + SimulateFairCoin(rg); } } return returnValue; } private static int SimulateFairCoin(Random rg) { while (true) { int flipOne = random_5_mod_2(rg); int flipTwo = random_5_mod_2(rg); if (flipOne == 0 && flipTwo == 1) { return 0; } else if (flipOne == 1 && flipTwo == 0) { return 1; } } } private static int random_5_mod_2(Random rg) { return random_5(rg) % 2; } private static int random_5(Random rg) { return rg.Next(5) + 1; } 

Se consideriamo il vincolo addizionale di cercare di dare la risposta più efficiente, ad esempio quella data un stream di input, I , di interi uniformsmente distribuiti di lunghezza m da 1-5, emette un stream O , di interi distribuiti uniformsmente da 1-7 del lunghezza più lunga rispetto a m , diciamo L(m) .

Il modo più semplice per analizzare questo è trattare i flussi I e O come numeri 5-ary e 7-ary. Ciò è ottenuto dall’idea della risposta principale di prendere lo stream a1, a2, a3,... -> a1+5*a2+5^2*a3+.. e allo stesso modo per lo stream O

Quindi se prendiamo una sezione del stream di input di lunghezza m choose n st 5^m-7^n=c dove c>0 ed è il più piccolo ansible. Poi c’è una mappa uniforms dal stream di input di lunghezza m a numeri interi da 1 a 5^m e un’altra mappa uniforms da numeri interi da 1 a 7^n al stream di output di lunghezza n dove potremmo dover perdere alcuni casi da il stream di input quando il numero intero mappato supera 7^n .

Quindi questo dà un valore per L(m) di circa m (log5/log7) che è approssimativamente di .82m .

La difficoltà con l’analisi di cui sopra è l’equazione 5^m-7^n=c che non è facile da risolvere esattamente e il caso in cui il valore uniforms da 1 a 5^m supera 7^n e perdiamo efficienza.

La domanda è quanto può essere raggiunto il valore migliore ansible di m (log5 / log7). Ad esempio, quando questo numero si avvicina a un numero intero, possiamo trovare un modo per ottenere questo numero integrale esatto dei valori di uscita?

Se 5^m-7^n=c quindi dal stream di input generiamo effettivamente un numero casuale uniforms da 0 a (5^m)-1 e non utilizziamo valori superiori a 7^n . Tuttavia questi valori possono essere salvati e utilizzati di nuovo. Generano effettivamente una sequenza uniforms di numeri da 1 a 5^m-7^n . Quindi possiamo provare a usarli e convertirli in numeri 7-ary in modo da poter creare più valori di output.

Se lasciamo che T7(X) sia la lunghezza media della sequenza di output degli interi random(1-7) derivati ​​da un input uniforms di dimensione X , e assumendo che 5^m=7^n0+7^n1+7^n2+...+7^nr+s, s<7 .

Quindi T7(5^m)=n0x7^n0/5^m + ((5^m-7^n0)/5^m) T7(5^m-7^n0) poiché abbiamo una lunghezza nessuna sequenza con probabilità 7 ^ n0 / 5 ^ m con un residuo di lunghezza 5^m-7^n0 con probabilità (5^m-7^n0)/5^m) .

Se continuiamo a sostituire, otteniamo:

 T7(5^m) = n0x7^n0/5^m + n1x7^n1/5^m + ... + nrx7^nr/5^m = (n0x7^n0 + n1x7^n1 + ... + nrx7^nr)/5^m 

Quindi

 L(m)=T7(5^m)=(n0x7^n0 + n1x7^n1 + ... + nrx7^nr)/(7^n0+7^n1+7^n2+...+7^nr+s) 

Un altro modo per dirlo è:

 If 5^m has 7-ary representation `a0+a1*7 + a2*7^2 + a3*7^3+...+ar*7^r Then L(m) = (a1*7 + 2a2*7^2 + 3a3*7^3+...+rar*7^r)/(a0+a1*7 + a2*7^2 + a3*7^3+...+ar*7^r) 

Il caso migliore è il mio originale sopra dove 5^m=7^n+s , dove s<7 .

Quindi T7(5^m) = nx(7^n)/(7^n+s) = n+o(1) = m (Log5/Log7)+o(1) come prima.

Il caso peggiore è quando possiamo trovare solo k e st 5 ^ m = kx7 + s.

 Then T7(5^m) = 1x(k.7)/(k.7+s) = 1+o(1) 

Altri casi sono da qualche parte tra di loro. Sarebbe interessante vedere come possiamo fare per m molto grandi, cioè quanto bene possiamo ottenere il termine di errore:

 T7(5^m) = m (Log5/Log7)+e(m) 

Sembra imansible ottenere e(m) = o(1) in generale, ma speriamo di poter provare e(m)=o(m) .

Il tutto quindi si basa sulla distribuzione delle cifre 7-ary di 5^m per vari valori di m .

Sono sicuro che c'è un sacco di teoria là fuori che copre ciò che potrei dare un'occhiata e riferire a un certo punto.

I problemi di compiti a casa sono permessi qui?

Questa funzione fa la matematica “base 5” grezza per generare un numero compreso tra 0 e 6.

 function rnd7() { do { r1 = rnd5() - 1; do { r2=rnd5() - 1; } while (r2 > 1); result = r2 * 5 + r1; } while (result > 6); return result + 1; } 

Ecco una implementazione Python funzionante della risposta di Adam .

 import random def rand5(): return random.randint(1, 5) def rand7(): while True: r = 5 * (rand5() - 1) + rand5() #r is now uniformly random between 1 and 25 if (r <= 21): break #result is now uniformly random between 1 and 7 return r % 7 + 1 

Mi piace buttare gli algoritmi che sto guardando in Python in modo che possa giocare con loro, ho pensato di pubblicarlo qui nella speranza che sia utile a qualcuno là fuori, non che ci sia voluto molto tempo per unirsi.

Perché non farlo in modo semplice?

 int random7() { return random5() + (random5() % 3); } 

Le probabilità di ottenere 1 e 7 in questa soluzione sono inferiori a causa del modulo, tuttavia, se si desidera solo una soluzione rapida e leggibile, questa è la strada da percorrere.

Supponendo che rand (n) qui significhi “numero intero casuale in una distribuzione uniforms da 0 a n-1 “, ecco un esempio di codice che usa il randint di Python, che ha quell’effetto. Usa solo randint (5) e le costanti per produrre l’effetto di randint (7) . Un po ‘sciocco, in realtà

 from random import randint sum = 7 while sum >= 7: first = randint(0,5) toadd = 9999 while toadd>1: toadd = randint(0,5) if toadd: sum = first+5 else: sum = first assert 7>sum>=0 print sum 

La premessa dietro la risposta corretta di Adam Rosenfield è:

  • x = 5 ^ n (nel suo caso: n = 2)
  • manipola n chiamate rand5 per ottenere un numero y nel raggio [1, x]
  • z = ((int) (x / 7)) * 7
  • se y> z, riprova. altrimenti restituisci y% 7 + 1

Quando n è uguale a 2, hai 4 possibilità di lancio: y = {22, 23, 24, 25}. Se usi n uguale a 6, hai solo 1 throw-away: y = {15625}.

5 ^ 6 = 15625
7 * 2232 = 15624

Chiami altre 5 volte. Tuttavia, hai una probabilità molto inferiore di ottenere un valore di proiezione (o un ciclo infinito). Se c’è un modo per non ottenere alcun valore di throw-away per y, non l’ho ancora trovato.

Here’s my answer:

 static struct rand_buffer { unsigned v, count; } buf2, buf3; void push (struct rand_buffer *buf, unsigned n, unsigned v) { buf->v = buf->v * n + v; ++buf->count; } #define PUSH(n, v) push (&buf##n, n, v) int rand16 (void) { int v = buf2.v & 0xf; buf2.v >>= 4; buf2.count -= 4; return v; } int rand9 (void) { int v = buf3.v % 9; buf3.v /= 9; buf3.count -= 2; return v; } int rand7 (void) { if (buf3.count >= 2) { int v = rand9 (); if (v < 7) return v % 7 + 1; PUSH (2, v - 7); } for (;;) { if (buf2.count >= 4) { int v = rand16 (); if (v < 14) { PUSH (2, v / 7); return v % 7 + 1; } PUSH (2, v - 14); } // Get a number between 0 & 25 int v = 5 * (rand5 () - 1) + rand5 () - 1; if (v < 21) { PUSH (3, v / 7); return v % 7 + 1; } v -= 21; PUSH (2, v & 1); PUSH (2, v >> 1); } } 

It’s a little more complicated than others, but I believe it minimises the calls to rand5. As with other solutions, there’s a small probability that it could loop for a long time.

 int rand7() { int value = rand5() + rand5() * 2 + rand5() * 3 + rand5() * 4 + rand5() * 5 + rand5() * 6; return value%7; } 

Unlike the chosen solution, the algorithm will run in constant time. It does however make 2 more calls to rand5 than the average run time of the chosen solution.

Note that this generator is not perfect (the number 0 has 0.0064% more chance than any other number), but for most practical purposes the guarantee of constant time probably outweighs this inaccuracy.

Spiegazione

This solution is derived from the fact that the number 15,624 is divisible by 7 and thus if we can randomly and uniformly generate numbers from 0 to 15,624 and then take mod 7 we can get a near-uniform rand7 generator. Numbers from 0 to 15,624 can be uniformly generated by rolling rand5 6 times and using them to form the digits of a base 5 number as follows:

 rand5 * 5^5 + rand5 * 5^4 + rand5 * 5^3 + rand5 * 5^2 + rand5 * 5 + rand5 

Properties of mod 7 however allow us to simplify the equation a bit:

 5^5 = 3 mod 7 5^4 = 2 mod 7 5^3 = 6 mod 7 5^2 = 4 mod 7 5^1 = 5 mod 7 

Così

 rand5 * 5^5 + rand5 * 5^4 + rand5 * 5^3 + rand5 * 5^2 + rand5 * 5 + rand5 

diventa

 rand5 * 3 + rand5 * 2 + rand5 * 6 + rand5 * 4 + rand5 * 5 + rand5 

Teoria

The number 15,624 was not chosen randomly, but can be discovered using fermat’s little theorem, which states that if p is a prime number then

 a^(p-1) = 1 mod p 

So this gives us,

 (5^6)-1 = 0 mod 7 

(5^6)-1 is equal to

 4 * 5^5 + 4 * 5^4 + 4 * 5^3 + 4 * 5^2 + 4 * 5 + 4 

This is a number in base 5 form and thus we can see that this method can be used to go from any random number generator to any other random number generator. Though a small bias towards 0 is always introduced when using the exponent p-1.

As long as there aren’t seven possibilities left to choose from, draw another random number, which multiplies the number of possibilities by five. In Perl:

 $num = 0; $possibilities = 1; sub rand7 { while( $possibilities < 7 ) { $num = $num * 5 + int(rand(5)); $possibilities *= 5; } my $result = $num % 7; $num = int( $num / 7 ); $possibilities /= 7; return $result; } 

Simple and efficient:

 int rand7 ( void ) { return 4; // this number has been calculated using // rand5() and is in the range 1..7 } 

(Inspired by What’s your favorite “programmer” cartoon? ).

I don’t like ranges starting from 1, so I’ll start from 0 🙂

 unsigned rand5() { return rand() % 5; } unsigned rand7() { int r; do { r = rand5(); r = r * 5 + rand5(); r = r * 5 + rand5(); r = r * 5 + rand5(); r = r * 5 + rand5(); r = r * 5 + rand5(); } while (r > 15623); return r / 2232; } 

There you go, uniform distribution and zero rand5 calls.

 def rand7: seed += 1 if seed >= 7: seed = 0 yield seed 

Need to set seed beforehand.

I know it has been answered, but is this seems to work ok, but I can not tell you if it has a bias. My ‘testing’ suggests it is, at least, reasonable.

Perhaps Adam Rosenfield would be kind enough to comment?

My (naive?) idea is this:

Accumulate rand5’s until there is enough random bits to make a rand7. This takes at most 2 rand5’s. To get the rand7 number I use the accumulated value mod 7.

To avoid the accumulator overflowing, and since the accumulator is mod 7 then I take the mod 7 of the accumulator:

 (5a + rand5) % 7 = (k*7 + (5a%7) + rand5) % 7 = ( (5a%7) + rand5) % 7 

The rand7() function follows:

(I let the range of rand5 be 0-4 and rand7 is likewise 0-6.)

 int rand7(){ static int a=0; static int e=0; int r; a = a * 5 + rand5(); e = e + 5; // added 5/7ths of a rand7 number if ( e<7 ){ a = a * 5 + rand5(); e = e + 5; // another 5/7ths } r = a % 7; e = e - 7; // removed a rand7 number a = a % 7; return r; } 

Edit: Added results for 100 million trials.

'Real' rand functions mod 5 or 7

rand5 : avg=1.999802 0:20003944 1:19999889 2:20003690 3:19996938 4:19995539 rand7 : avg=3.000111 0:14282851 1:14282879 2:14284554 3:14288546 4:14292388 5:14288736 6:14280046

My rand7

Average looks ok and number distributions look ok too.

randt : avg=3.000080 0:14288793 1:14280135 2:14287848 3:14285277 4:14286341 5:14278663 6:14292943

There are elegant algorithms cited above, but here’s one way to approach it, although it might be roundabout. I am assuming values generated from 0.

R2 = random number generator giving values less than 2 (sample space = {0, 1})
R8 = random number generator giving values less than 8 (sample space = {0, 1, 2, 3, 4, 5, 6, 7})

In order to generate R8 from R2, you will run R2 thrice, and use the combined result of all 3 runs as a binary number with 3 digits. Here are the range of values when R2 is ran thrice:

0 0 0 –> 0
.
.
1 1 1 –> 7

Now to generate R7 from R8, we simply run R7 again if it returns 7:

 int R7() { do { x = R8(); } while (x > 6) return x; } 

The roundabout solution is to generate R2 from R5 (just like we generated R7 from R8), then R8 from R2 and then R7 from R8.

Here’s a solution that fits entirely within integers and is within about 4% of optimal (ie uses 1.26 random numbers in {0..4} for every one in {0..6}). The code’s in Scala, but the math should be reasonably clear in any language: you take advantage of the fact that 7^9 + 7^8 is very close to 5^11. So you pick an 11 digit number in base 5, and then interpret it as a 9 digit number in base 7 if it’s in range (giving 9 base 7 numbers), or as an 8 digit number if it’s over the 9 digit number, etc.:

 abstract class RNG { def apply(): Int } class Random5 extends RNG { val rng = new scala.util.Random var count = 0 def apply() = { count += 1 ; rng.nextInt(5) } } class FiveSevener(five: RNG) { val sevens = new Array[Int](9) var nsevens = 0 val to9 = 40353607; val to8 = 5764801; val to7 = 823543; def loadSevens(value: Int, count: Int) { nsevens = 0; var remaining = value; while (nsevens < count) { sevens(nsevens) = remaining % 7 remaining /= 7 nsevens += 1 } } def loadSevens { var fivepow11 = 0; var i=0 while (i<11) { i+=1 ; fivepow11 = five() + fivepow11*5 } if (fivepow11 < to9) { loadSevens(fivepow11 , 9) ; return } fivepow11 -= to9 if (fivepow11 < to8) { loadSevens(fivepow11 , 8) ; return } fivepow11 -= to8 if (fivepow11 < 3*to7) loadSevens(fivepow11 % to7 , 7) else loadSevens } def apply() = { if (nsevens==0) loadSevens nsevens -= 1 sevens(nsevens) } } 

If you paste a test into the interpreter (REPL actually), you get:

 scala> val five = new Random5 five: Random5 = [email protected] scala> val seven = new FiveSevener(five) seven: FiveSevener = [email protected] scala> val counts = new Array[Int](7) counts: Array[Int] = Array(0, 0, 0, 0, 0, 0, 0) scala> var i=0 ; while (i < 100000000) { counts( seven() ) += 1 ; i += 1 } i: Int = 100000000 scala> counts res0: Array[Int] = Array(14280662, 14293012, 14281286, 14284836, 14287188, 14289332, 14283684) scala> five.count res1: Int = 125902876 

The distribution is nice and flat (within about 10k of 1/7 of 10^8 in each bin, as expected from an approximately-Gaussian distribution).

By using a rolling total , you can both

  • maintain an equal distribution; e
  • not have to sacrifice any element in the random sequence.

Both these problems are an issue with the simplistic rand(5)+rand(5)... -type solutions. The following Python code shows how to implement it (most of this is proving the distribution).

 import random x = [] for i in range (0,7): x.append (0) t = 0 tt = 0 for i in range (0,700000): ######################################## ##### qq.py ##### r = int (random.random () * 5) t = (t + r) % 7 ######################################## ##### qq_notsogood.py ##### #r = 20 #while r > 6: #r = int (random.random () * 5) #r = r + int (random.random () * 5) #t = r ######################################## x[t] = x[t] + 1 tt = tt + 1 high = x[0] low = x[0] for i in range (0,7): print "%d: %7d %.5f" % (i, x[i], 100.0 * x[i] / tt) if x[i] < low: low = x[i] if x[i] > high: high = x[i] diff = high - low print "Variation = %d (%.5f%%)" % (diff, 100.0 * diff / tt) 

And this output shows the results:

 pax$ python qq.py 0: 99908 14.27257 1: 100029 14.28986 2: 100327 14.33243 3: 100395 14.34214 4: 99104 14.15771 5: 99829 14.26129 6: 100408 14.34400 Variation = 1304 (0.18629%) pax$ python qq.py 0: 99547 14.22100 1: 100229 14.31843 2: 100078 14.29686 3: 99451 14.20729 4: 100284 14.32629 5: 100038 14.29114 6: 100373 14.33900 Variation = 922 (0.13171%) pax$ python qq.py 0: 100481 14.35443 1: 99188 14.16971 2: 100284 14.32629 3: 100222 14.31743 4: 99960 14.28000 5: 99426 14.20371 6: 100439 14.34843 Variation = 1293 (0.18471%) 

A simplistic rand(5)+rand(5) , ignoring those cases where this returns more than 6 has a typical variation of 18%, 100 times that of the method shown above:

 pax$ python qq_notsogood.py 0: 31756 4.53657 1: 63304 9.04343 2: 95507 13.64386 3: 127825 18.26071 4: 158851 22.69300 5: 127567 18.22386 6: 95190 13.59857 Variation = 127095 (18.15643%) pax$ python qq_notsogood.py 0: 31792 4.54171 1: 63637 9.09100 2: 95641 13.66300 3: 127627 18.23243 4: 158751 22.67871 5: 126782 18.11171 6: 95770 13.68143 Variation = 126959 (18.13700%) pax$ python qq_notsogood.py 0: 31955 4.56500 1: 63485 9.06929 2: 94849 13.54986 3: 127737 18.24814 4: 159687 22.81243 5: 127391 18.19871 6: 94896 13.55657 Variation = 127732 (18.24743%) 

And, on the advice of Nixuz, I’ve cleaned the script up so you can just extract and use the rand7... stuff:

 import random # rand5() returns 0 through 4 inclusive. def rand5(): return int (random.random () * 5) # rand7() generator returns 0 through 6 inclusive (using rand5()). def rand7(): rand7ret = 0 while True: rand7ret = (rand7ret + rand5()) % 7 yield rand7ret # Number of test runs. count = 700000 # Work out distribution. distrib = [0,0,0,0,0,0,0] rgen =rand7() for i in range (0,count): r = rgen.next() distrib[r] = distrib[r] + 1 # Print distributions and calculate variation. high = distrib[0] low = distrib[0] for i in range (0,7): print "%d: %7d %.5f" % (i, distrib[i], 100.0 * distrib[i] / count) if distrib[i] < low: low = distrib[i] if distrib[i] > high: high = distrib[i] diff = high - low print "Variation = %d (%.5f%%)" % (diff, 100.0 * diff / count) 

This answer is more an experiment in obtaining the most entropy possible from the Rand5 function. t is therefore somewhat unclear and almost certainly a lot slower than other implementations.

Assuming the uniform distribution from 0-4 and resulting uniform distribution from 0-6:

 public class SevenFromFive { public SevenFromFive() { // this outputs a uniform ditribution but for some reason including it // screws up the output distribution // open question Why? this.fifth = new ProbabilityCondensor(5, b => {}); this.eigth = new ProbabilityCondensor(8, AddEntropy); } private static Random r = new Random(); private static uint Rand5() { return (uint)r.Next(0,5); } private class ProbabilityCondensor { private readonly int samples; private int counter; private int store; private readonly Action output; public ProbabilityCondensor(int chanceOfTrueReciprocal, Action output) { this.output = output; this.samples = chanceOfTrueReciprocal - 1; } public void Add(bool bit) { this.counter++; if (bit) this.store++; if (counter == samples) { bool? e; if (store == 0) e = false; else if (store == 1) e = true; else e = null;// discard for now counter = 0; store = 0; if (e.HasValue) output(e.Value); } } } ulong buffer = 0; const ulong Mask = 7UL; int bitsAvail = 0; private readonly ProbabilityCondensor fifth; private readonly ProbabilityCondensor eigth; private void AddEntropy(bool bit) { buffer <<= 1; if (bit) buffer |= 1; bitsAvail++; } private void AddTwoBitsEntropy(uint u) { buffer <<= 2; buffer |= (u & 3UL); bitsAvail += 2; } public uint Rand7() { uint selection; do { while (bitsAvail < 3) { var x = Rand5(); if (x < 4) { // put the two low order bits straight in AddTwoBitsEntropy(x); fifth.Add(false); } else { fifth.Add(true); } } // read 3 bits selection = (uint)((buffer & Mask)); bitsAvail -= 3; buffer >>= 3; if (selection == 7) eigth.Add(true); else eigth.Add(false); } while (selection == 7); return selection; } } 

The number of bits added to the buffer per call to Rand5 is currently 4/5 * 2 so 1.6. If the 1/5 probability value is included that increases by 0.05 so 1.65 but see the comment in the code where I have had to disable this.

Bits consumed by call to Rand7 = 3 + 1/8 * (3 + 1/8 * (3 + 1/8 * (…
This is 3 + 3/8 + 3/64 + 3/512 … so approx 3.42

By extracting information from the sevens I reclaim 1/8*1/7 bits per call so about 0.018

This gives a net consumption 3.4 bits per call which means the ratio is 2.125 calls to Rand5 for every Rand7. The optimum should be 2.1.

I would imagine this approach is significantly slower than many of the other ones here unless the cost of the call to Rand5 is extremely expensive (say calling out to some external source of entropy).

in php

 function rand1to7() { do { $output_value = 0; for ($i = 0; $i < 28; $i++) { $output_value += rand1to5(); } while ($output_value != 140); $output_value -= 12; return floor($output_value / 16); } 

loops to produce a random number between 16 and 127, divides by sixteen to create a float between 1 and 7.9375, then rounds down to get an int between 1 and 7. if I am not mistaken, there is a 16/112 chance of getting any one of the 7 outcomes.

 extern int r5(); int r7() { return ((r5() & 0x01) << 2 ) | ((r5() & 0x01) << 1 ) | (r5() & 0x01); } 

The function you need is rand1_7() , I wrote rand1_5() so that you can test it and plot it.

 import numpy def rand1_5(): return numpy.random.randint(5)+1 def rand1_7(): q = 0 for i in xrange(7): q+= rand1_5() return q%7 + 1 

just scale your output from your first function

 0) you have a number in range 1-5 1) subtract 1 to make it in range 0-4 2) multiply by (7-1)/(5-1) to make it in range 0-6 3) add 1 to increment the range: Now your result is in between 1-7