c++ - rango - srand c

Forma recomendada para inicializar srand?

Question

Necesito una ''buena'' manera de inicializar el generador de números pseudoaleatorios en C ++. Encontré un artículo que dice:

Para generar números aleatorios, srand generalmente se inicializa a algún valor distintivo, como los relacionados con el tiempo de ejecución. Por ejemplo, el valor devuelto por el tiempo de la función (declarado en el encabezado ctime) es diferente cada segundo, lo que es lo suficientemente distintivo para la mayoría de las necesidades de aleatorización.

Unixtime no es lo suficientemente distintivo para mi aplicación. ¿Cuál es una mejor manera de inicializar esto? Puntos de bonificación si es portátil, pero el código se ejecutará principalmente en hosts Linux.

Estaba pensando en hacer algunas operaciones de pid / unixtime para obtener un int, o posiblemente leer datos de /dev/urandom .

¡Gracias!

EDITAR

Sí, en realidad estoy comenzando mi aplicación varias veces por segundo y me he encontrado con colisiones.

Answer 1

En windows:

srand(GetTickCount());

proporciona una mejor semilla que time() ya que está en milisegundos.

Answer 2

Esto es lo que he usado para pequeños programas de línea de comandos que se pueden ejecutar con frecuencia (varias veces por segundo):

unsigned long seed = mix(clock(), time(NULL), getpid());

Donde la mezcla es:

// http://www.concentric.net/~Ttwang/tech/inthash.htm
unsigned long mix(unsigned long a, unsigned long b, unsigned long c)
{
a=a-b; a=a-c; a=a^(c >> 13);
b=b-c; b=b-a; b=b^(a << 8);
c=c-a; c=c-b; c=c^(b >> 13);
a=a-b; a=a-c; a=a^(c >> 12);
b=b-c; b=b-a; b=b^(a << 16);
c=c-a; c=c-b; c=c^(b >> 5);
a=a-b; a=a-c; a=a^(c >> 3);
b=b-c; b=b-a; b=b^(a << 10);
c=c-a; c=c-b; c=c^(b >> 15);
return c;
}

Answer 3

Incluya el encabezado en la parte superior de su programa, y ​​escriba:

srand(time(NULL));

En su programa antes de declarar su número aleatorio. Aquí hay un ejemplo de un programa que imprime un número aleatorio entre uno y diez:

#include <iostream>
#include <iomanip>
using namespace std;
int main()
{
//Initialize srand
srand(time(NULL));
//Create random number
int n = rand() % 10 + 1;
//Print the number
cout << n << endl; //End the line
//The main function is an int, so it must return a value
return 0;
}

Answer 4

La mejor manera es usar otro generador de números pseudoaleatorios. Mersenne twister (y Wichmann-Hill) es mi recomendación.

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

Answer 5

La mejor respuesta es usar las cosas del número aleatorio de Boost. O si tiene acceso a C ++ 11, use el encabezado <random> .

Pero si hablamos de rand() y srand()
La mejor manera es simplemente usar time() :

int main()
{
srand(time(NULL));
...
}

Asegúrese de hacer esto al principio de su programa, ¡y no cada vez que llame a rand() !

Cada vez que inicie, time () devolverá un valor único (a menos que inicie la aplicación varias veces por segundo). En sistemas de 32 bits, solo se repetirá cada 60 años más o menos.

Sé que no crees que el tiempo sea lo suficientemente único, pero me resulta difícil de creer. Pero se sabe que estoy equivocado.

Si está comenzando muchas copias de su aplicación simultáneamente, podría usar un temporizador con una resolución más fina. Pero luego corre el riesgo de un período de tiempo más corto antes de que el valor se repita.

OK, entonces si realmente crees que estás iniciando múltiples aplicaciones por segundo.
Luego use un grano más fino en el temporizador.

 int main()
{
struct timeval time;
gettimeofday(&time,NULL);
// microsecond has 1 000 000
// Assuming you did not need quite that accuracy
// Also do not assume the system clock has that accuracy.
srand((time.tv_sec * 1000) + (time.tv_usec / 1000));
// The trouble here is that the seed will repeat every
// 24 days or so.
// If you use 100 (rather than 1000) the seed repeats every 248 days.
// Do not make the MISTAKE of using just the tv_usec
// This will mean your seed repeats every second.
}

Answer 6

La verdadera pregunta que debe hacerse es qué calidad de aleatoriedad necesita.

libc random es un LCG

La calidad de la aleatoriedad será baja con independencia de la entrada que proporciones.

Si solo necesita asegurarse de que las diferentes instancias tendrán inicializaciones diferentes, puede mezclar id de proceso (getpid), id de subproceso y un temporizador. Mezcle los resultados con xor. La entropía debería ser suficiente para la mayoría de las aplicaciones.

Ejemplo:

struct timeb tp;
ftime(&tp);
srand(static_cast<unsigned int>(getpid()) ^
static_cast<unsigned int>(pthread_self()) ^
static_cast<unsigned int >(tp.millitm));

Para una mejor calidad aleatoria, use / dev / urandom. Puede hacer que el código anterior sea portátil al usar boost :: thread y boost :: date_time.

Answer 7

La versión c++11 de la publicación más votadas por Jonathan Wright:

#include <ctime>
#include <random>
#include <thread>
...
const auto time_seed = static_cast<size_t>(std::time(0));
const auto clock_seed = static_cast<size_t>(std::clock());
const size_t pid_seed =
std::hash<std::thread::id>()(std::this_thread::get_id());
std::seed_seq seed_value { time_seed, clock_seed, pid_seed };
...
// E.g seeding an engine with the above seed.
std::mt19937 gen;
gen.seed(seed_value);

Answer 8

Para aquellos que usan Visual Studio aquí hay otra forma:

#include "stdafx.h"
#include <time.h>
#include <windows.h>
const __int64 DELTA_EPOCH_IN_MICROSECS= 11644473600000000;
struct timezone2
{
__int32 tz_minuteswest; /* minutes W of Greenwich */
bool tz_dsttime; /* type of dst correction */
};
struct timeval2 {
__int32 tv_sec; /* seconds */
__int32 tv_usec; /* microseconds */
};
int gettimeofday(struct timeval2 *tv/*in*/, struct timezone2 *tz/*in*/)
{
FILETIME ft;
__int64 tmpres = 0;
TIME_ZONE_INFORMATION tz_winapi;
int rez = 0;
ZeroMemory(&ft, sizeof(ft));
ZeroMemory(&tz_winapi, sizeof(tz_winapi));
GetSystemTimeAsFileTime(&ft);
tmpres = ft.dwHighDateTime;
tmpres <<= 32;
tmpres |= ft.dwLowDateTime;
/*converting file time to unix epoch*/
tmpres /= 10; /*convert into microseconds*/
tmpres -= DELTA_EPOCH_IN_MICROSECS;
tv->tv_sec = (__int32)(tmpres * 0.000001);
tv->tv_usec = (tmpres % 1000000);
//_tzset(),don''t work properly, so we use GetTimeZoneInformation
rez = GetTimeZoneInformation(&tz_winapi);
tz->tz_dsttime = (rez == 2) ? true : false;
tz->tz_minuteswest = tz_winapi.Bias + ((rez == 2) ? tz_winapi.DaylightBias : 0);
return 0;
}
int main(int argc, char** argv) {
struct timeval2 tv;
struct timezone2 tz;
ZeroMemory(&tv, sizeof(tv));
ZeroMemory(&tz, sizeof(tz));
gettimeofday(&tv, &tz);
unsigned long seed = tv.tv_sec ^ (tv.tv_usec << 12);
srand(seed);
}

Tal vez un poco exagerado, pero funciona bien para intervalos rápidos. la función gettimeofday se encuentra here .

Editar: tras una investigación más profunda rand_s podría ser una buena alternativa para Visual Studio, no es solo un rand seguro (), es totalmente diferente y no usa la semilla de srand. Supuse que era casi idéntico a rand simplemente "más seguro".

Para usar rand_s solo no olvide #define _CRT_RAND_S antes de incluir stdlib.h.

Answer 9

Siempre y cuando su programa solo se ejecute en Linux (y su programa sea un ejecutable ELF), se le garantiza que el núcleo le proporciona a su proceso una semilla aleatoria única en el vector auxiliar ELF. El núcleo le da 16 bytes aleatorios, diferentes para cada proceso, que puede obtener con getauxval(AT_RANDOM) . Para utilizar estos para srand , use solo un int de ellos, como tal:

#include <sys/auxv.h>
void initrand(void)
{
unsigned int *seed;
seed = (unsigned int *)getauxval(AT_RANDOM);
srand(*seed);
}

Es posible que esto también se traduzca en otros sistemas basados ​​en ELF. No estoy seguro de qué valores auxiliares se implementan en sistemas que no sean Linux.

Answer 10

Sugiero que veas el archivo unix_random.c en el código de mozilla. (supongo que es mozilla / security / freebl / ...) debería estar en la biblioteca freebl.

allí utiliza información de llamada del sistema (como pwd, netstat ....) para generar ruido para el número aleatorio, está escrito para soportar la mayoría de las plataformas (lo que puede ganarme un punto de bonificación: D).

Answer 11

Supongamos que tiene una función con una firma como:

int foo(char *p);

Una excelente fuente de entropía para una semilla aleatoria es un hash de los siguientes:

• Resultado total de clock_gettime (segundos y nanosegundos) sin tirar los bits bajos: son los más valiosos.
• El valor de p , emitido a uintptr_t .
• La dirección de p , emitida a uintptr_t .

Al menos el tercero, y posiblemente también el segundo, derivan entropía del ASLR del sistema, si está disponible (la dirección de pila inicial y, por lo tanto, la dirección de pila actual, es algo aleatoria).

También evitaría usar rand / srand completo, tanto para no tocar el estado global, y así tener más control sobre el PRNG que se usa. Pero el procedimiento anterior es una buena (y bastante portátil) forma de obtener una entropía decente sin mucho trabajo, independientemente de qué PRNG utilices.

Answer 12

si necesita un generador de números aleatorios mejor, no use el libc rand. En lugar de eso, solo use algo como /dev/random o /dev/urandom directamente (lea en int directamente de él o algo así).

El único beneficio real de libc rand es que, dado un valor inicial, es predecible lo que ayuda con la depuración.

Answer 13

C ++ 11 random_device

Si necesita una calidad razonable, no debería usar rand () en primer lugar; deberías usar la biblioteca <random> . Proporciona muchas funcionalidades excelentes, como una variedad de motores para diferentes intercambios de calidad / tamaño / rendimiento, reentrada y distribuciones predefinidas para que no los termine equivocándose. Incluso puede proporcionar un acceso fácil a datos aleatorios no deterministas (por ejemplo, / dev / aleatorio), según su implementación.

#include <random>
#include <iostream>
int main() {
std::random_device r;
std::seed_seq seed{r(), r(), r(), r(), r(), r(), r(), r()};
std::mt19937 eng(seed);
std::uniform_int_distribution<> dist{1,100};
for (int i=0; i<50; ++i)
std::cout << dist(eng) << ''/n'';
}

eng es una fuente de aleatoriedad, aquí una implementación incorporada de mersenne twister. Sembramos usando random_device, que en cualquier implementación decente será un RNG no determinista, y seed_seq para combinar más de 32 bits de datos aleatorios. Por ejemplo, en libc ++ random_device accede a / dev / urandom de forma predeterminada (aunque puede darle otro archivo para acceder en su lugar).

A continuación, creamos una distribución tal que, dada una fuente de aleatoriedad, las llamadas repetidas a la distribución producirán una distribución uniforme de las entradas de 1 a 100. Luego procederemos a usar la distribución repetidamente e imprimiremos los resultados.

Answer 14

#include <stdio.h>
#include <sys/time.h>
main()
{
struct timeval tv;
gettimeofday(&tv,NULL);
printf("%d/n", tv.tv_usec);
return 0;
}

tv.tv_usec está en microsegundos. Esto debería ser una semilla aceptable.