Generando una distribución uniforme de ENTEROS en C

5 minutos de lectura

He escrito una función C que creo que selecciona enteros a partir de una distribución uniforme con rango [rangeLow, rangeHigh], inclusive. Esto no es tarea, solo estoy usando esto en algunos sistemas integrados que estoy haciendo para divertirme.

En mis casos de prueba, este código parece producir una distribución adecuada. Sin embargo, no estoy completamente seguro de que la implementación sea correcta. ¿Podría alguien hacer una verificación de cordura y decirme si he hecho algo mal aquí?

//uniform_distribution returns an INTEGER in [rangeLow, rangeHigh], inclusive.
int uniform_distribution(int rangeLow, int rangeHigh)
{
    int myRand = (int)rand(); 
    int range = rangeHigh - rangeLow + 1; //+1 makes it [rangeLow, rangeHigh], inclusive.
    int myRand_scaled = (myRand % range) + rangeLow;
    return myRand_scaled;
}
//note: make sure rand() was already initialized using srand()

PD: busqué otras preguntas como esta. Sin embargo, fue difícil filtrar el pequeño subconjunto de preguntas que analizan números enteros aleatorios en lugar de números de coma flotante aleatorios.

  • Para una aleatoriedad decente, es posible que deba optar por algo específico de la plataforma o al menos usar algo fuera del estándar C, por ejemplo, funciones POSIX o BSD-spec.

    – sueño relajado

    25 de julio de 2012 a las 3:36

Supongamos que rand() genera un valor I distribuido uniformemente en el rango [0..RAND_MAX]y desea generar un valor O distribuido uniformemente en el rango [L,H].

Supongamos que I in es el rango [0..32767] y O está en el rango [0..2].

De acuerdo con el método sugerido, O= I%3. Tenga en cuenta que en el rango dado, hay 10923 números para los que I%3=0, 10923 números para los que I%3=1, pero solo 10922 números para los que I%3=2. Por lo tanto, su método no asignará un valor de I a O de manera uniforme.

Como otro ejemplo, supongamos que O está en el rango [0..32766].

De acuerdo con su método sugerido, O=I%32767. Ahora obtendrá O=0 tanto para I=0 como para I=32767. Por lo tanto, 0 es el doble de probable que cualquier otro valor: su método nuevamente no es uniforme.


La forma sugerida de generar un mapeo uniforme es la siguiente:

  1. Calcule la cantidad de bits que se necesitan para almacenar un valor aleatorio en el rango [L,H]:

    int sin signo nRange = (int sin signo)H – (int sin signo)L + 1;
    unsigned int nRangeBits= (unsigned int)ceil(log((doble(nRange) / log(2.));

  2. Generar nRangeBits bits aleatorios

    esto se puede implementar fácilmente desplazando hacia la derecha el resultado de rand()

  3. Asegúrese de que el número generado no sea mayor que HL. Si es así, repita el paso 2.

  4. Ahora puede mapear el número generado en O simplemente agregando una L.

  • He hecho referencia a esta buena respuesta. aquí. Mejora de candidatos pequeños ceil(log((double(nRange) / log(2.)) –> ceil(log2((double)nRange)) o algún otro cálculo de enteros solamente.

    – chux – Reincorporar a Monica

    06/01/2018 a las 21:45


avatar de usuario
jxh

En algunas implementaciones, rand() no proporcionó una buena aleatoriedad en sus bits de orden inferior, por lo que el operador de módulo no proporcionaría resultados muy aleatorios. Si encuentra que ese es el caso, puede probar esto en su lugar:

int uniform_distribution(int rangeLow, int rangeHigh) {
    double myRand = rand()/(1.0 + RAND_MAX); 
    int range = rangeHigh - rangeLow + 1;
    int myRand_scaled = (myRand * range) + rangeLow;
    return myRand_scaled;
}

Utilizando rand() de esta manera se producirá un sesgo como lo señala Lior. Pero, la técnica está bien si puede encontrar un generador de números uniformes para calcular myRand. Un posible candidato sería drand48(). Esto reducirá en gran medida la cantidad de sesgo a algo que sería muy difícil de detectar.

Sin embargo, si necesita algo criptográficamente seguro, debe usar un algoritmo descrito en la respuesta de Lior, suponiendo que su rand() es criptográficamente seguro en sí mismo (el predeterminado probablemente no lo sea, por lo que deberá encontrar uno). A continuación se muestra una implementación simplificada de lo que Lior describió. En lugar de contar bits, asumimos que el rango cae dentro RAND_MAXy calcule un múltiplo adecuado. En el peor de los casos, el algoritmo termina llamando al generador de números aleatorios dos veces en promedio por solicitud de un número en el rango.

int uniform_distribution_secure(int rangeLow, int rangeHigh) {
    int range = rangeHigh - rangeLow + 1;
    int secureMax = RAND_MAX - RAND_MAX % range;
    int x;
    do x = secure_rand(); while (x >= secureMax);
    return rangeLow + x % range;
}

  • Debería ser “return rangeLow + x % range;”.

    – Marc

    21 de enero de 2016 a las 10:39

avatar de usuario
jose petit

Creo que se sabe que rand() no es muy bueno. Solo depende de qué tan buenos sean los datos “aleatorios” que necesite.

Supongo que podría escribir una prueba y luego calcular el valor de chi-cuadrado para ver qué tan bueno es su generador uniforme:

http://en.wikipedia.org/wiki/Pearson%27s_chi-squared_test

Dependiendo de su uso (no use esto para su barajador de póquer en línea), podría considerar un LFSR

http://en.wikipedia.org/wiki/Linear_feedback_shift_register

Puede ser más rápido, si solo desea una salida pseudoaleatoria. Además, supuestamente pueden ser uniformes, aunque no he estudiado las matemáticas lo suficiente como para respaldar esa afirmación.

avatar de usuario
dave

Una versión que corrige los errores de distribución (anotados por Lior), involucra los bits altos devueltos por rand() y solo usa matemáticas enteras (si eso es deseable):

int uniform_distribution(int rangeLow, int rangeHigh)
{
    int range = rangeHigh - rangeLow + 1; //+1 makes it [rangeLow, rangeHigh], inclusive.
    int copies=RAND_MAX/range; // we can fit n-copies of [0...range-1] into RAND_MAX
    // Use rejection sampling to avoid distribution errors
    int limit=range*copies;    
    int myRand=-1;
    while( myRand<0 || myRand>=limit){
        myRand=rand();   
    }
    return myRand/copies+rangeLow;    // note that this involves the high-bits
}

//nota: asegúrese de que rand() ya se haya inicializado usando srand()

Esto debería funcionar bien siempre que range es mucho más pequeño que RAND_MAXde lo contrario volverás al problema de que rand() no es un buen generador de números aleatorios en términos de bits bajos.

¿Ha sido útil esta solución?

Esta web utiliza cookies propias y de terceros para su correcto funcionamiento y para fines analíticos y para mostrarte publicidad relacionada con sus preferencias en base a un perfil elaborado a partir de tus hábitos de navegación. Al hacer clic en el botón Aceptar, acepta el uso de estas tecnologías y el procesamiento de tus datos para estos propósitos. Configurar y más información
Privacidad