Número aleatorio de 64 bits entre un rango

Así que he estado buscando durante un par de días una función que toma 2 argumentos, un valor bajo y un valor alto (ambos de los cuales 64bits ints) que genera un número aleatorio entre estos rangos. El problema con el que me encuentro es que el número no es un int de 64 bits. o el número en los bordes es más común que los que están en el medio.

Aquí hay un código: simplemente sigue devolviendo -1 o 0 …

#include #include #include int64_t range1=0,range2=18446744073709551614; int64_t getRandomInRange(int64_t low, int64_t high ) { int64_t base_random = rand(); if (RAND_MAX==base_random) return getRandomInRange(low, high); int range = high-low, remainder = RAND_MAX%range, bucket = RAND_MAX/range; if (base_random < RAND_MAX-remainder) { return low+base_random/bucket; } else { return getRandomInRange(low, high); } } int main () { int i; for (i=0;i<100;i++) { printf("random number: %lld\n",getRandomInRange(range1, range2)); } } 

Tomar un módulo N no conduce a una distribución uniforme, a menos que N divida el rango R exactamente:

  rnd = 0..15, range = 9. 0 1 2 3 4 5 6 7 8 <-- 0..8 % 9 0 1 2 3 4 5 6 <-- 9-15 % 9 ---------------------------------- 2 2 2 2 2 2 2 1 1 <-- sum = 16 

De la misma manera, si uno trata de evitar ese hecho multiplicando con eg 9/16

  rnd = 0..15, range = 9, reducing function = rnd * 9 >> 4, one has 0 1 2 3 4 5 6 7 8 for rnd = 0, 2, 4, 6, 8, 9, 13, 15 and 0 1 2 3 5 6 7 for rnd = 1, 3, 5, 7, 10, 12, 14 ------------------------ 2 2 2 2 1 2 2 2 1 <-- sum = 16 

Este es el llamado 'principio de la paloma' en acción.

Una forma adecuada de crear una distribución uniforme de números aleatorios es generar bits de ceil (log2 (N)) de números aleatorios, hasta que el número representado por los bits sea menor que el rango:

  int rand_orig(); // the "original" random function returning values from 0..2^n-1 // We assume that n = ceil(log2(N)); int rand(int N) { int y; do { y = rand_orig(); } while (y >= N); return y; } 

Por supuesto, esto se puede mejorar si rand_orig (); devolvería valores mucho mayores n >> log (N) en distribución uniforme; entonces es suficiente descartar solo aquellos valores de rand_orig () que son más grandes que el múltiplo más grande de N y reducir el rango con módulo.

Otra forma sería crear un método que equilibre los valores (N> rango) de manera uniforme a todos los grupos, por ejemplo

  #define CO_PRIME 1 // Better to have some large prime 2^(n-1) < CO_PRIME < 2^n-1 int rand_orig(); // some function returning random numbers in range 0..2^n-1 int rand(int N) // N is the range { static int x; int y = rand_orig(); int new_rand = (x + y) % N; x = (x + CO_PRIME) % N; return new_rand; } 

Ahora el período de este término de equilibrio x es N, lo que lleva a una distribución al menos uniforme.

Su código devuelve 0 o -1 porque 18446744073709551614 es demasiado grande para caber en un int64_t . (De hecho, es un poco demasiado grande para caber en un uint64_t , ya que es exactamente 2 64 , y el número más grande que puede caber en un entero sin signo de k bit es 2 k -1). . (gcc y clang (al menos) te advirtieron sobre esto, incluso sin -Wall .)

En cualquier caso, no es tan difícil producir la función de biblioteca que está buscando, siempre que tenga algún mecanismo para generar enteros sin signo de 64 bits aleatorios. Una buena opción sería la biblioteca de Mersenne Twister . Sin embargo, para una demostración solo podemos usar las funciones estándar de la biblioteca C, en este caso lrand48 que produce un entero de distribución uniforme en el rango (0, 2 31 -1) . Dado que ese rango produce solo 31 bits de aleatoriedad, necesitaremos llamarlo varias veces para producir 64 bits.

 #define _XOPEN_SOURCE #include  #include  uint64_t urand64() { uint64_t hi = lrand48(); uint64_t md = lrand48(); uint64_t lo = lrand48(); return (hi << 42) + (md << 21) + lo; } 

Para obtener una muestra imparcial del rango [low, high) , debemos restringir nuestra generación de números aleatorios a algunos múltiplos de high - low . El rango de urand64 es de tamaño 2 64 , por lo que debemos excluir los valores mod high-low 2 64 . Desafortunadamente, a menos que tengamos un int sin signo de más de 64 bits, no podemos calcular el módulo directamente. Sin embargo, podemos usar la identidad:

mod k (mod k m + mod k n) = mod k (m+n) .

En este caso, elegiremos m como 2 64 -1 y n como 1, para evitar tener que calcular modhigh-lown . Además, es fácil demostrar que a menos que k sea ​​una potencia exacta de 2, es imposible que el mod k 2 64 -1 + mod k 1 sea ​​exactamente k , mientras que si k es una potencia exacta de 2, el mod k 2 64 deseado mod k 2 64 es 0. Podemos usar la siguiente prueba simple para una potencia de 2, cuya explicación se puede encontrar en otra parte:

 bool is_power_of_2(uint64_t x) { return x == x & -x; } 

Así podemos definir:

 uint64_t unsigned_uniform_random(uint64_t low, uint64_t high) { static const uint64_t M = ~(uint64_t)0; uint64_t range = high - low; uint64_t to_exclude = is_power_of_2(range) ? 0 : M % range + 1; uint64_t res; // Eliminate `to_exclude` possible values from consideration. while ((res = urand64()) < to_exclude) {} return low + res % range; } 

Tenga en cuenta que, en el peor de los casos, el número de valores a excluir es 2 63 -1, que es ligeramente inferior a la mitad del rango de valores posibles. Entonces, en el peor de los casos, necesitaremos, en promedio, dos llamadas a urand64 antes de encontrar un valor satisfactorio.

Finalmente, debemos lidiar con el hecho de que se nos pide que produzcamos enteros con signo, en lugar de enteros sin signo. Sin embargo, eso no es un problema porque las conversiones necesarias están bien definidas.

 int64_t uniform_random(int64_t low, int64_t high) { static const uint64_t OFFSET = ((uint64_t)1) << 63; uint64_t ulow = (uint64_t)low + OFFSET; uint64_t uhigh = (uint64_t)high + OFFSET; uint64_t r = unsigned_uniform_random(ulow, uhigh); // Conform to the standard; a good compiler should optimize. if (r >= OFFSET) return r - OFFSET; else return (int64_t)r - (int64_t)(OFFSET - 1) - 1; }