sorteos - ¿Hay alguna alternativa al uso del tiempo para generar una generación aleatoria de números?

numeros aleatorios google

Question

Estoy intentando ejecutar varias instancias de un fragmento de código (2000 instancias más o menos) simultáneamente en un clúster informático. La forma en que funciona es que envío los trabajos y el clúster los ejecutará a medida que los nodos se abren cada cierto tiempo, con varios trabajos por nodo. Esto parece producir los mismos valores para un buen número de instancias en su generación de números aleatorios, que usa una semilla de tiempo.

¿Hay una alternativa simple que pueda usar en su lugar? La reproducibilidad y la seguridad no son importantes, es la generación rápida de semillas únicas. ¿Cuál sería el enfoque más simple de esto, y si es posible un enfoque de plataforma cruzada sería bueno.

Answer 1

Windows

Proporciona CryptGenRandom() y RtlGenRandom() . Le darán una selección de bytes aleatorios, que puede usar como semillas.

Puede encontrar los documentos en las pages msdn .

Linux / Unixes

Puede usar RAND_bytes RAND_bytes() de RAND_bytes() para obtener un número aleatorio de bytes en Linux. Utilizará /dev/random por defecto.

Poniendo todo junto:

#ifdef _WIN32
  #include <NTSecAPI.h>
#else
  #include <openssl/rand.h> 
#endif

uint32_t get_seed(void)
{
  uint32_t seed = 0;

#ifdef _WIN32
  RtlGenRandom(&seed, sizeof(uint32_t) );
#else
  RAND_bytes(&seed, sizeof(uint32_t) ); 
#endif

  return seed;
}

Tenga en cuenta que openssl proporciona un PRNG criptográficamente seguro por defecto, por lo que puede usarlo directamente. Más información here .

Answer 2

En lugar de tiempo directo, medido en segundos desde la función C std lib time (), ¿podría usar el contador del procesador? La mayoría de los procesadores tienen un conteo de ticks gratis, por ejemplo, en x86 / x64 está el contador de sellos de tiempo :

El Contador de sellos de tiempo es un registro de 64 bits presente en todos los procesadores x86 desde el Pentium. Cuenta el número de tics desde el reinicio.

(Esa página también tiene muchas formas de acceder a este contador en diferentes plataformas: gcc / ms visual c / etc)

Tenga en cuenta que el contador de la marca de tiempo no está libre de fallas, es posible que no se sincronice entre los procesadores (probablemente no le interese su aplicación). Y las funciones de ahorro de energía pueden subir o bajar el procesador (de nuevo, probablemente no le importe).

Answer 3

Si la singularidad es importante, debe organizar que cada nodo sepa qué identificaciones han sido reclamadas por otros. Podrías hacer esto con un protocolo preguntando "¿alguien reclamó ID x?" u organizando con anticipación para que cada nodo tenga una selección de ID que no han sido asignadas a otros.

(Los GUID utilizan el MAC de la máquina, por lo que entrarían en la categoría "organizar con anticipación").

Sin algún tipo de acuerdo, correrá el riesgo de que dos nodos tengan la misma identificación.

Answer 4

Si se puede usar C ++ 11, entonces considere std::random_device . Le sugiero que vea el link para obtener una guía completa.

Extracción del mensaje esencial del enlace de video : nunca debe usar srand & rand , sino usar std::random_device y std::mt19937 ; en la mayoría de los casos, lo siguiente sería lo que desea:

#include <iostream>
#include <random>
int main() {
    std::random_device rd;
    std::mt19937 mt(rd());
    std::uniform_int_distribution<int> dist(0,99);
    for (int i = 0; i < 16; i++) {
        std::cout << dist(mt) << " ";
    }
    std::cout << std::endl;
}

Answer 5

Solo una idea ... generar un GUID (que es de 16 bytes) y sumar sus trozos de 4 bytes u 8 bytes (dependiendo del ancho esperado de la semilla), lo que permite el envolvimiento de enteros. Usa el resultado como una semilla.

Los GUID generalmente encapsulan las características de la computadora que los generó (como la dirección MAC), lo que debería hacer bastante improbable que dos máquinas diferentes terminen generando la misma secuencia aleatoria.

Obviamente, esto no es portátil, pero encontrar las API / bibliotecas adecuadas para su sistema no debería ser demasiado difícil (por ejemplo, UuidCreate en Win32, uuid_generate en Linux).

Answer 6

Supongo que tienes algún proceso para lanzar los otros procesos. Haz que pase en la semilla para usar. Entonces puede hacer que ese proceso maestro simplemente pase un número al azar para que cada proceso lo use como su semilla. De esta forma, en realidad solo se elige una semilla arbitraria ... puedes usar tiempo para eso.

Si no tiene un proceso maestro iniciando los otros, entonces si cada proceso al menos tiene un índice único, entonces lo que puede hacer es tener un proceso que genere una serie de números aleatorios en la memoria (si es memoria compartida) o en un archivo (si es un disco compartido) y luego haga que cada proceso saque el número aleatorio del índice para usarlo como su semilla.

Nada le dará una distribución más uniforme de las semillas que una serie de números aleatorios de una sola semilla.

Answer 7

Suponiendo que está en un sistema razonablemente POSIX-ish, debería tener clock_gettime . Esto dará la hora actual en nanosegundos , lo que significa que para todos los propósitos prácticos es imposible obtener el mismo valor dos veces. (En teoría, las implementaciones malas podrían tener una resolución mucho menor, por ejemplo, solo multiplicar milisegundos por 1 millón, pero incluso sistemas medio decentes como Linux dan resultados de nanosegundos reales).

Answer 8

Una combinación del PID y el tiempo debería ser suficiente para obtener una semilla única. No es 100% multiplataforma, pero getpid(3) en las plataformas * nix y GetProcessId en Windows le GetProcessId el 99.9% del camino hasta allí. Algo como esto debería funcionar:

srand((time(NULL) & 0xFFFF) | (getpid() << 16));

También puede leer datos de /dev/urandom en sistemas * nix, pero no hay un equivalente a eso en Windows.

Answer 9

La instrucción rdtsc es una semilla bastante confiable (y aleatoria).

En Windows se puede acceder a través de __rdtsc() intrínseco.

En GNU C, se puede acceder a través de:

unsigned long long rdtsc(){
    unsigned int lo,hi;
    __asm__ __volatile__ ("rdtsc" : "=a" (lo), "=d" (hi));
    return ((unsigned long long)hi << 32) | lo;
}

La instrucción mide los pseudociclos totales desde que se encendió el procesador. Dada la alta frecuencia de las máquinas actuales, es extremadamente improbable que dos procesadores devuelvan el mismo valor incluso si arrancaron al mismo tiempo y se sincronizan a la misma velocidad.

Answer 10

unsigned seed;

read(open("/dev/urandom", O_RDONLY), &seed, sizeof seed);
srand(seed); // IRL, check for errors, close the fd, etc...

También recomendaría un generador de números aleatorios mejor.