¿Cómo se generan números enteros aleatorios distribuidos uniformemente?
Necesito una función que genere un número entero aleatorio en un rango determinado (incluidos los valores límite). No tengo requisitos irrazonables de calidad/aleatoriedad; Tengo cuatro requisitos:
- Necesito que sea rápido. Mi proyecto necesita generar millones (o a veces incluso decenas de millones) de números aleatorios y mi función generadora actual ha demostrado ser un cuello de botella.
- Necesito que sea razonablemente uniforme (el uso de rand() está perfectamente bien).
- los rangos mínimo-máximo pueden ser desde <0, 1> hasta <-32727, 32727>.
- tiene que ser sembrable.
Actualmente tengo el siguiente código C++:
output = min + (rand() * (int)(max - min) / RAND_MAX)
El problema es que no es realmente uniforme: max se devuelve sólo cuando rand() = RAND_MAX (para Visual C++ es 1/32727). Este es un problema importante para rangos pequeños como <-1, 1>, donde casi nunca se devuelve el último valor.
Así que tomé lápiz y papel y se me ocurrió la siguiente fórmula (que se basa en el truco de redondeo de enteros (int)(n + 0,5):
( (max - min) * rand() + (RAND_MAX / (2 * (max - min))) ) / RAND_MAX
Pero todavía no me da una distribución uniforme. Las ejecuciones repetidas con 10000 muestras me dan una proporción de 37:50:13 para valores -1, 0, 1.
¿Existe una fórmula mejor? (¿O incluso la función generadora de números pseudoaleatorios completa?)
La respuesta más simple (y por lo tanto mejor) de C++ (usando el estándar 2011) es:
#include <random>
std::random_device rd; // Only used once to initialise (seed) engine
std::mt19937 rng(rd()); // Random-number engine used (Mersenne-Twister in this case)
std::uniform_int_distribution<int> uni(min,max); // Guaranteed unbiased
auto random_integer = uni(rng);
No hay necesidad de reinventar la rueda, ni preocuparse por los prejuicios ni por utilizar el tiempo como semilla aleatoria.
Una solución distribuida rápida, algo mejor que la suya, pero aún no adecuadamente uniforme, es
output = min + (rand() % static_cast<int>(max - min + 1))
Excepto cuando el tamaño del rango es una potencia de 2, este método produce números distribuidos sesgados y no uniformes independientemente de la calidad de rand(). Para obtener una prueba exhaustiva de la calidad de este método, lea esto .
Si su compilador admite C++ 0x y usarlo es una opción para usted, entonces <random>es probable que el nuevo encabezado estándar satisfaga sus necesidades. Tiene una alta calidad uniform_int_distributionque aceptará límites mínimos y máximos (incluidos los que necesite), y puede elegir entre varios generadores de números aleatorios para conectarlos a esa distribución.
Aquí hay un código que genera un millón de intmensajes aleatorios distribuidos uniformemente en [-57, 365]. He utilizado las nuevas <chrono>instalaciones estándar para cronometrarlo, ya que usted mencionó que el rendimiento es una preocupación importante para usted.
#include <iostream>
#include <random>
#include <chrono>
int main()
{
typedef std::chrono::high_resolution_clock Clock;
typedef std::chrono::duration<double> sec;
Clock::time_point t0 = Clock::now();
const int N = 10000000;
typedef std::minstd_rand G; // Select the engine
G g; // Construct the engine
typedef std::uniform_int_distribution<> D; // Select the distribution
D d(-57, 365); // Construct the distribution
int c = 0;
for (int i = 0; i < N; ++i)
c += d(g); // Generate a random number
Clock::time_point t1 = Clock::now();
std::cout << N/sec(t1-t0).count() << " random numbers per second.\n";
return c;
}
Para mí (Intel Core i5 de 2,8 GHz ), esto imprime:
2.10268e+07 números aleatorios por segundo.
Puedes inicializar el generador pasando un int a su constructor:
G g(seed);
Si luego descubre que eso intno cubre el rango que necesita para su distribución, puede solucionarlo cambiando algo uniform_int_distributionasí (por ejemplo, a long long):
typedef std::uniform_int_distribution<long long> D;
Si luego descubre que minstd_randno es un generador de suficiente calidad, también puede cambiarlo fácilmente. P.ej:
typedef std::mt19937 G; // Now using mersenne_twister_engine
Tener un control independiente sobre el generador de números aleatorios y la distribución aleatoria puede resultar bastante liberador.
También calculé (no se muestran) los primeros cuatro " momentos " de esta distribución (usando minstd_rand) y los comparé con los valores teóricos en un intento de cuantificar la calidad de la distribución:
min = -57
max = 365
mean = 154.131
x_mean = 154
var = 14931.9
x_var = 14910.7
skew = -0.00197375
x_skew = 0
kurtosis = -1.20129
x_kurtosis = -1.20001
(El x_prefijo se refiere a "esperado".)
