¿Cuál es el algoritmo óptimo para generar un entero aleatorio imparcial dentro de un rango?

En esta pregunta de StackOverflow:

Generar entero aleatorio de un rango

la respuesta aceptada sugiere la siguiente fórmula para generar un entero aleatorio entre el min y el max dados, con min y max incluidos en el rango:

 output = min + (rand() % (int)(max - min + 1)) 

Pero también dice que

Esto sigue siendo ligeramente sesgado hacia números más bajos … También es posible extenderlo para que elimine el sesgo.

Pero no explica por qué está sesgada hacia números más bajos o cómo eliminar el sesgo. Entonces, la pregunta es: ¿este es el enfoque más óptimo para la generación de un entero aleatorio dentro de un rango (firmado) sin depender de nada sofisticado, solo la función rand() y, en caso de que sea óptimo, cómo eliminar el sesgo ?

EDITAR:

Acabo de probar el algoritmo while loop sugerido por @Joey contra la extrapolación de coma flotante:

 static const double s_invRandMax = 1.0/((double)RAND_MAX + 1.0); return min + (int)(((double)(max + 1 - min))*rand()*s_invRandMax); 

para ver cuánto uniformemente “bolas” están “cayendo” y se están distribuyendo entre una serie de “cubos”, una prueba para la extrapolación de coma flotante y otra para el algoritmo while loop. Pero los resultados variaron dependiendo de la cantidad de “bolas” (y “cubos”), por lo que no pude elegir fácilmente un ganador. El código de trabajo se puede encontrar en esta página de Ideone . Por ejemplo, con 10 cubos y 100 bolas, la desviación máxima de la probabilidad ideal entre cubos es menor para la extrapolación de punto flotante que para el algoritmo while loop (0.04 y 0.05 respectivamente) pero con 1000 bolas, la desviación máxima del while -loop Algoritmo es menor (0.024 y 0.011), y con 10000 bolas, la extrapolación de coma flotante vuelve a estar mejor (0.0034 y 0.0053), y así sucesivamente sin mucha consistencia. Pensando en la posibilidad de que ninguno de los algoritmos produzca una distribución uniforme mejor que la del otro algoritmo, me inclino hacia la extrapolación de punto flotante, ya que parece funcionar más rápido que el algoritmo while -loop. Entonces, ¿está bien elegir el algoritmo de extrapolación de coma flotante o mis pruebas / conclusiones no son del todo correctas?

El problema se produce cuando el número de salidas del generador de números aleatorios (RAND_MAX + 1) no es divisible de manera uniforme en el rango deseado (máx. Mín. + 1). Dado que habrá un mapeo consistente de un número aleatorio a una salida, algunos resultados se asignarán a más números aleatorios que otros. Esto es independientemente de cómo se realice la asignación: puede usar módulo, división, conversión a coma flotante, cualquier vudú que se le ocurra, el problema básico permanece.

La magnitud del problema es muy pequeña, y las aplicaciones poco exigentes generalmente pueden salirse con la suya al ignorarlo. Cuanto menor sea el rango y mayor sea RAND_MAX, menos pronunciado será el efecto.

Tomé tu progtwig de ejemplo y lo pellizqué un poco. Primero creé una versión especial de rand que solo tiene un rango de 0-255, para demostrar mejor el efecto. Hice algunos ajustes a rangeRandomAlg2 . Finalmente cambié el número de “bolas” a 1000000 para mejorar la consistencia. Puede ver los resultados aquí: http://ideone.com/4P4HY

Observe que la versión de coma flotante produce dos probabilidades estrechamente agrupadas, cerca de 0.101 o 0.097, nada en el medio. Este es el sesgo en acción.

Creo que llamar a este “algoritmo de Java” es un poco engañoso, estoy seguro de que es mucho más antiguo que Java.

 int rangeRandomAlg2 (int min, int max) { int n = max - min + 1; int remainder = RAND_MAX % n; int x; do { x = rand(); } while (x >= RAND_MAX - remainder); return min + x % n; } 

El problema es que estás haciendo una operación de módulo. Esto no sería un problema si RAND_MAX sería divisible de manera uniforme por su módulo, pero generalmente ese no es el caso. Como un ejemplo muy artificial, suponga que RAND_MAX es 11 y su módulo es 3. Obtendrá los siguientes números aleatorios posibles y los siguientes residuos resultantes:

 0 1 2 3 4 5 6 7 8 9 10 0 1 2 0 1 2 0 1 2 0 1 

Como puede ver, 0 y 1 son ligeramente más probables que 2.

Una opción para resolver esto es el muestreo de rechazo: al rechazar los números 9 y 10 anteriores, puede causar que la distribución resultante sea uniforme nuevamente. La parte difícil es descubrir cómo hacerlo de manera eficiente. Un buen ejemplo (uno que me llevó dos días para entender por qué funciona) se puede encontrar en el método java.util.Random.nextInt(int) Java.

La razón por la cual el algoritmo de Java es un poco complicado es que evitan las operaciones lentas como la multiplicación y la división para el control. Si no te importa demasiado, también puedes hacerlo de la manera ingenua:

 int n = (int)(max - min + 1); int remainder = RAND_MAX % n; int x, output; do { x = rand(); output = x % n; } while (x >= RAND_MAX - remainder); return min + output; 

EDIT: corrigió un error de fencepost en el código anterior, ahora funciona como debería. También creé un pequeño progtwig de muestra (C #, tomando un PRNG uniforme para números entre 0 y 15 y construyendo un PRNG para números entre 0 y 6 a través de varias maneras):

 using System; class Rand { static Random r = new Random(); static int Rand16() { return r.Next(16); } static int Rand7Naive() { return Rand16() % 7; } static int Rand7Float() { return (int)(Rand16() / 16.0 * 7); } // corrected static int Rand7RejectionNaive() { int n = 7, remainder = 16 % n, x, output; do { x = Rand16(); output = x % n; } while (x >= 16 - remainder); return output; } // adapted to fit the constraints of this example static int Rand7RejectionJava() { int n = 7, x, output; do { x = Rand16(); output = x % n; } while (x - output + 6 > 15); return output; } static void Test(Func rand, string name) { var buckets = new int[7]; for (int i = 0; i < 10000000; i++) buckets[rand()]++; Console.WriteLine(name); for (int i = 0; i < 7; i++) Console.WriteLine("{0}\t{1}", i, buckets[i]); } static void Main() { Test(Rand7Naive, "Rand7Naive"); Test(Rand7Float, "Rand7Float"); Test(Rand7RejectionNaive, "Rand7RejectionNaive"); } } 

El resultado es el siguiente (pegado en Excel y agregado de color condicional de las celdas para que las diferencias sean más aparentes):

enter image description here

Ahora que arreglé mi error en el muestreo de rechazo anterior, funciona como debería (antes de que sesgue 0). Como puede ver, el método de flotación no es perfecto en absoluto, solo distribuye los números sesgados de manera diferente.

Es fácil ver por qué este algoritmo produce una muestra sesgada. Supongamos que su función rand() devuelve números enteros uniformes del conjunto {0, 1, 2, 3, 4} . Si quiero usar esto para generar un bit aleatorio 0 o 1 , diría rand() % 2 . El conjunto {0, 2, 4} me da 0 y el conjunto {1, 3} me da 1 , así que claramente muestro 0 con 60% y 1 con 40% de probabilidad, ¡no uniforme en absoluto!

Para solucionar esto, debes asegurarte de que tu rango deseado divide el rango del generador de números aleatorios, o descarta el resultado siempre que el generador de números aleatorios devuelva un número mayor que el múltiplo más grande posible del rango objective.

En el ejemplo anterior, el rango objective es 2, el múltiplo más grande que cabe en el rango de generación aleatoria es 4, por lo que desechamos cualquier muestra que no esté en el conjunto {0, 1, 2, 3} y volvemos a tirar.

Con mucho, la solución más fácil es std::uniform_int_distribution(min, max) .