Expandir un rango aleatorio de 1-5 a 1-7

Dada una función que produce un entero aleatorio en el rango de 1 a 5, escribe una función que produce un entero aleatorio en el rango de 1 a 7.

  1. ¿Qué es una solución simple?
  2. ¿Cuál es una solución efectiva para reducir el uso de memoria o ejecutar en una CPU más lenta?

Esto es equivalente a la solución de Adam Rosenfield, pero puede ser un poco más claro para algunos lectores. Supone que rand5 () es una función que devuelve un entero estadísticamente aleatorio en el rango de 1 a 5 inclusive.

 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; } 

¿Como funciona? Piénselo de esta manera: imagínense imprimir esta matriz de doble dimensión en papel, unirla a un tablero de dardos y arrojarle dardos al azar. Si tocas un valor distinto de cero, es un valor estadísticamente aleatorio entre 1 y 7, ya que hay una cantidad igual de valores distintos de cero para elegir. Si tocas un cero, sigue arrojando el dardo hasta que toques un valor distinto de cero. Eso es lo que hace este código: los índices iyj seleccionan aleatoriamente una ubicación en el tablero de dardos, y si no obtenemos un buen resultado, seguimos arrojando dardos.

Como dijo Adam, esto puede durar para siempre en el peor de los casos, pero estadísticamente el peor de los casos nunca ocurre. 🙂

No hay una solución (exactamente correcta) que se ejecute en una cantidad de tiempo constante, ya que 1/7 es un decimal infinito en la base 5. Una solución simple sería usar el muestreo de rechazo, por ejemplo:

 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 

Esto tiene un tiempo de ejecución esperado de 25/21 = 1.19 iteraciones del bucle, pero hay una probabilidad infinitesimalmente pequeña de bucle para siempre.

Me gustaría agregar otra respuesta, además de mi primera respuesta . Esta respuesta intenta minimizar el número de llamadas a rand5() por llamada a rand7() , para maximizar el uso de la aleatoriedad. Es decir, si considera que la aleatoriedad es un recurso precioso, queremos utilizar la mayor cantidad de información posible, sin descartar ningún fragmento aleatorio. Esta respuesta también tiene algunas similitudes con la lógica presentada en la respuesta de Ivan .

La entropía de una variable aleatoria es una cantidad bien definida. Para una variable aleatoria que toma N estados con probabilidades iguales (una distribución uniforme), la entropía es log 2 N. Por lo tanto, rand5() tiene aproximadamente 2.32193 bits de entropía, y rand7() tiene aproximadamente 2.80735 bits de entropía. Si esperamos maximizar nuestro uso de la aleatoriedad, necesitamos usar todos los 2.32193 bits de entropía de cada llamada a rand5() , y aplicarlos para generar 2.80735 bits de entropía necesarios para cada llamada a rand7() . El límite fundamental, entonces, es que no podemos hacer nada mejor que registrar (7) / log (5) = 1.20906 llamadas a rand5() por llamada a rand7() .

Notas al margen: todos los logaritmos en esta respuesta serán la base 2 a menos que se especifique lo contrario. rand5() devolverá números en el rango [0, 4] y se rand7() devuelve números en el rango [0, 6]. Ajustar los rangos a [1, 5] y [1, 7] respectivamente es trivial.

Entonces, ¿Cómo lo hacemos? Generamos un número real aleatorio infinitamente preciso entre 0 y 1 (pretendemos por el momento que podríamos calcular y almacenar ese número infinitamente preciso, lo arreglaremos más adelante). Podemos generar dicho número generando sus dígitos en la base 5: escogemos el número aleatorio 0. a 1 a 2 a 3 …, donde cada dígito a i es elegido por una llamada a rand5() . Por ejemplo, si nuestro RNG eligió un i = 1 para todo i , entonces ignorando el hecho de que no es muy aleatorio, eso correspondería al número real 1/5 + 1/5 2 + 1/5 3 + .. . = 1/4 (sum de una serie geométrica).

Bien, hemos escogido un número real aleatorio entre 0 y 1. Ahora afirmo que ese número aleatorio está distribuido uniformemente. Intuitivamente, esto es fácil de entender, ya que cada dígito fue elegido de manera uniforme, y el número es infinitamente preciso. Sin embargo, una prueba formal de esto es algo más complicada, ya que ahora estamos tratando con una distribución continua en lugar de una distribución discreta, así que tenemos que demostrar que la probabilidad de que nuestro número se encuentre en un intervalo [ a , b ] es igual a duración de ese intervalo, b - a . La prueba queda como ejercicio para el lector =).

Ahora que tenemos un número real aleatorio seleccionado uniformemente del rango [0, 1], necesitamos convertirlo en una serie de números uniformemente aleatorios en el rango [0, 6] para generar la salida de rand7() . Cómo hacemos esto? Justo al revés de lo que acabamos de hacer, lo convertimos en un decimal infinitamente preciso en la base 7, y luego cada dígito base 7 corresponderá a una salida de rand7() .

Tomando el ejemplo de antes, si nuestro rand5() produce una stream infinita de 1, entonces nuestro número real aleatorio será 1/4. Convirtiendo 1/4 a base 7, obtenemos el decimal infinito 0.15151515 …, así que produciremos como salida 1, 5, 1, 5, 1, 5, etc.

Ok, entonces tenemos la idea principal, pero nos quedan dos problemas: no podemos realmente calcular o almacenar un número real infinitamente preciso, entonces, ¿cómo manejamos solo una porción finita de él? En segundo lugar, ¿cómo lo convertimos realmente a la base 7?

Una forma en que podemos convertir un número entre 0 y 1 a la base 7 es la siguiente:

  1. Multiplicar por 7
  2. La parte integral del resultado es la próxima base de 7 dígitos
  3. Reste la parte integral, dejando solo la parte fraccionaria
  4. Ir al paso 1

Para tratar el problema de la precisión infinita, calculamos un resultado parcial, y también almacenamos un límite superior en lo que podría ser el resultado. Es decir, supongamos que hemos llamado rand5() dos veces y devolvió 1 ambas veces. El número que hemos generado hasta ahora es 0.11 (base 5). Cualquiera que sea el rest de la serie infinita de llamadas a rand5() , el número real aleatorio que estamos generando nunca será mayor que 0.12: siempre es cierto que 0.11 ≤ 0.11xyz … <0.12.

Por lo tanto, haciendo un seguimiento del número actual hasta el momento, y el valor máximo que podría tomar, convertimos ambos números en base 7. Si coinciden en los primeros k dígitos, podemos emitir de forma segura los siguientes k dígitos, independientemente de ¡cuál es la stream infinita de 5 dígitos básicos, nunca afectarán los próximos k dígitos de la representación de base 7!

Y ese es el algoritmo: para generar la siguiente salida de rand7() , generamos solo tantos dígitos de rand5() como necesitamos para asegurarnos de que sabemos con certeza el valor del siguiente dígito en la conversión del número real aleatorio a la base 7. Aquí hay una implementación de Python, con un arnés de prueba:

 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) 

Tenga en cuenta que rand7_gen() devuelve un generador, ya que tiene un estado interno que implica la conversión del número a la base 7. El arnés de prueba llama al next(r7) 10000 veces para producir 10000 números aleatorios, y luego mide su distribución. Solo se utilizan cálculos enteros, por lo que los resultados son exactamente correctos.

También tenga en cuenta que los números aquí son muy grandes, muy rápidos. Los poderes de 5 y 7 crecen rápidamente. Por lo tanto, el rendimiento comenzará a degradarse notablemente después de generar muchos números aleatorios, debido a la aritmética de bignum. Pero recuerde que mi objective fue maximizar el uso de bits aleatorios, no maximizar el rendimiento (aunque ese es un objective secundario).

En una ejecución de esto, hice 12091 llamadas a rand5() para 10000 llamadas a rand7() , logrando el mínimo de log (7) / log (5) llamadas en promedio a 4 cifras significativas, y el resultado resultante fue uniforme.

Para transferir este código a un idioma que no tenga números enteros arbitrariamente grandes, tendrá que pow5 los valores de pow5 y pow7 al valor máximo de su tipo integral nativo, si se vuelven demasiado grandes, luego reinicia todo y comienza de nuevo. Esto boostá la cantidad promedio de llamadas a rand5() por llamada a rand7() muy ligeramente, pero ojalá no aumente demasiado incluso para enteros de 32 o 64 bits.

(He robado la respuesta de Adam Rosenfeld y la he ejecutado aproximadamente un 7% más rápido).

Supongamos que rand5 () devuelve uno de {0,1,2,3,4} con distribución igual y el objective es return {0,1,2,3,4,5,6} con igual distribución.

 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); } 

Estamos haciendo un seguimiento del mayor valor que el bucle puede hacer en la variable max . Si el resultado hasta ahora está entre max% 7 y max-1, el resultado se distribuirá uniformemente en ese rango. Si no, usamos el rest, que es aleatorio entre 0 y max% 7-1, y otra llamada a rand () para hacer un nuevo número y un nuevo máximo. Entonces comenzamos de nuevo.

Editar: Esperar el número de veces para llamar a rand5 () es x en esta ecuación:

 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 se puede representar en una secuencia de 3 bits

Usa rand (5) para llenar aleatoriamente cada bit con 0 o 1.
Por ejemplo: call rand (5) y

si el resultado es 1 o 2, llena el bit con 0
si el resultado es 4 o 5, llena el bit con 1
si el resultado es 3, ignore y vuelva a hacerlo (rechazo)

De esta forma podemos llenar 3 bits aleatoriamente con 0/1 y así obtener un número del 1-7.

EDITAR: Esta parece ser la respuesta más simple y eficiente, así que aquí hay un código para ello:

 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 

Editar: Eso no funciona. Está desactivado en aproximadamente 2 partes en 1000 (suponiendo un rand perfecto5). Los cubos obtienen:

 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 

Al cambiar a una sum de

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

parece ganar un orden de magnitud por cada 2 agregados

Por cierto: la tabla de errores anterior no se generó a través del muestreo sino por la siguiente relación de recurrencia:

p[x,n] es el número de formas en que output=x puede ocurrir dado n llamadas 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] 

Lo siguiente produce una distribución uniforme en {1, 2, 3, 4, 5, 6, 7} usando un generador de números aleatorios que produce una distribución uniforme en {1, 2, 3, 4, 5}. El código es complicado, pero la lógica es clara.

 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; } 

Si consideramos la restricción adicional de tratar de dar la respuesta más eficiente, es decir, una que tenga un flujo de entrada, I , de enteros uniformemente distribuidos de longitud m de 1-5 produce una secuencia O , de enteros uniformemente distribuidos de 1 a 7 de la la longitud más larga con respecto a m , digamos L(m) .

La forma más sencilla de analizar esto es tratar las streams I y O como números 5-arios y 7-arios, respectivamente. Esto se logra con la idea de la respuesta principal de tomar la stream a1, a2, a3,... -> a1+5*a2+5^2*a3+.. y de manera similar para la stream O

Entonces, si tomamos una sección de la stream de entrada de longitud m choose n st 5^m-7^n=c donde c>0 y es lo más pequeña posible. Luego hay un mapa uniforme de la secuencia de entrada de longitud m a números enteros de 1 a 5^m otro mapa uniforme de enteros de 1 a 7^n a la secuencia de salida de longitud n donde podemos tener que perder algunos casos de la stream de entrada cuando el entero mapeado excede 7^n .

Entonces esto da un valor para L(m) de alrededor de m (log5/log7) que es aproximadamente .82m .

La dificultad con el análisis anterior es la ecuación 5^m-7^n=c que no es fácil de resolver exactamente y el caso donde el valor uniforme de 1 a 5^m excede 7^n y perdemos eficiencia.

La pregunta es qué tan cerca del mejor valor posible de m (log5 / log7) se puede alcanzar. Por ejemplo, cuando este número se acerca a un número entero ¿podemos encontrar una forma de lograr este número integral exacto de valores de salida?

Si 5^m-7^n=c entonces desde el flujo de entrada generamos efectivamente un número aleatorio uniforme de 0 a (5^m)-1 y no utilizamos valores superiores a 7^n . Sin embargo, estos valores se pueden rescatar y usar de nuevo. Generan efectivamente una secuencia uniforme de números de 1 a 5^m-7^n . Entonces podemos tratar de usar estos y convertirlos en números 7-arios para que podamos crear más valores de salida.

Si dejamos que T7(X) sea ​​la longitud promedio de la secuencia de salida de enteros random(1-7) derivados de una entrada uniforme de tamaño X , y suponiendo que 5^m=7^n0+7^n1+7^n2+...+7^nr+s, s<7 .

Entonces T7(5^m)=n0x7^n0/5^m + ((5^m-7^n0)/5^m) T7(5^m-7^n0) ya que tenemos una longitud sin secuencia con probabilidad 7 ^ n0 / 5 ^ m con un residual de longitud 5^m-7^n0 con probabilidad (5^m-7^n0)/5^m) .

Si seguimos sustituyendo obtenemos:

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

Por lo tanto

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

Otra forma de express esto es:

 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) 

El mejor caso posible es el original anterior, donde 5^m=7^n+s , donde s<7 .

Entonces T7(5^m) = nx(7^n)/(7^n+s) = n+o(1) = m (Log5/Log7)+o(1) como antes.

El peor caso es cuando solo podemos encontrar k y st 5 ^ m = kx7 + s.

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

Otros casos están en algún lugar intermedio. Sería interesante ver qué tan bien podemos hacer para m muy grande, es decir, qué tan bueno podemos obtener el término de error:

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

Parece imposible alcanzar e(m) = o(1) en general, pero con suerte podemos demostrar e(m)=o(m) .

Todo el asunto se basa en la distribución de los dígitos 7-arios de 5^m para varios valores de m .

Estoy seguro de que existe una gran cantidad de teoría que cubre esto, puedo echarle un vistazo e informar en algún momento.

¿Se permiten los problemas de tarea aquí?

Esta función realiza cálculos crudos de “base 5” para generar un número entre 0 y 6.

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

Aquí hay una implementación de Python en funcionamiento de la respuesta de 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 

Me gusta arrojar algoritmos que estoy mirando en Python para poder jugar con ellos, pensé que lo publicaría aquí con la esperanza de que sea útil para alguien, no es que haya tardado en lanzarse juntos.

¿Por qué no hacerlo simple?

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

Las posibilidades de obtener 1 y 7 en esta solución son menores debido al módulo, sin embargo, si solo desea una solución rápida y legible, este es el camino a seguir.

Suponiendo que rand (n) aquí significa “entero aleatorio en una distribución uniforme de 0 a n-1 “, aquí hay una muestra de código usando randint de Python, que tiene ese efecto. Utiliza solo randint (5) y constantes para producir el efecto de randint (7) . Un poco tonto, en realidad

 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 premisa detrás de la respuesta correcta de Adam Rosenfield es:

  • x = 5 ^ n (en este caso: n = 2)
  • manipular n rand5 llamadas para obtener un número y dentro del rango [1, x]
  • z = ((int) (x / 7)) * 7
  • si y> z, inténtalo de nuevo. else return y% 7 + 1

Cuando n es igual a 2, tienes 4 posibilidades de descarte: y = {22, 23, 24, 25}. Si usa n es igual a 6, solo tiene 1 descarte: y = {15625}.

5 ^ 6 = 15625
7 * 2232 = 15624

Llamas rand5 más veces. Sin embargo, tiene muchas menos posibilidades de obtener un valor de descarte (o un ciclo infinito). Si hay una manera de no obtener un valor de descarte posible para y, aún no lo he encontrado.

Aquí está mi respuesta:

 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.

Explicación

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 

Asi que

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

se convierte

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

Teoría

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. En 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 = Random5@e9c592 scala> val seven = new FiveSevener(five) seven: FiveSevener = FiveSevener@143c423 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; y
  • 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