forma más rápida de generar bits aleatorios

Question

¿Cuál sería la forma más rápida de generar una gran cantidad de bits (pseudo) aleatorios? Cada bit debe ser independiente y ser cero o uno con la misma probabilidad. Yo, obviamente, podría hacer alguna variación en

randbit=rand()%2; 

pero siento que debe haber una manera más rápida, generando varios bits aleatorios de cada llamada al generador de números aleatorios. Idealmente me gustaría obtener un int o un char donde cada bit es aleatorio e independiente, pero también son posibles otras soluciones.

La aplicación no es de naturaleza criptográfica, por lo que la aleatoriedad fuerte no es un factor importante, mientras que la velocidad y la distribución correcta es importante.

Answer 1

Eche un vistazo a Boost.Random, especialmente boost::uniform_int<>.

Answer 2

Como dices solo generas enteros aleatorios.
Luego tienes 32 bits aleatorios con unos y ceros igualmente probables.

Obtener los bits en un bucle:

for (int i = 0; i < 32; i++) 
{ 
    randomBit = (randomNum >> i) & 1 
    ... 
    // Do your thing 
} 

Repita esto para el mayor número de veces que se necesita para obtener la cantidad correcta de bits.

Answer 3

SMP Safe (i.e. Fastest way possiable these days) and good bits

Nota el uso del atributo [ThreadStatic], este objeto de nuevo hilo de, sin bloqueo manejar automáticamente. Esa es la única manera de asegurar un alto rendimiento al azar, sin bloque de SMP.

http://blogs.msdn.com/pfxteam/archive/2009/02/19/9434171.aspx

Answer 4

Puede generar un número aleatorio y seguir shifitng derecha y probar el bit menos significativo para obtener los bits aleatorios en lugar de hacer una operación mod.

Answer 5

convertir un número binario de azar en
Por qué no conseguir un solo número (del tamaño apropiado para obtener suficientes bits que necesita) y luego convertirlo a binario. Obtendrás bits de un número aleatorio, lo que significa que también son aleatorios.

Los ceros y unos también tienen la probabilidad del 50%, ya que tomar todos los números entre 0 y algunos 2^n limitar y contar el número de ceros y unos es igual> lo que significa que la probabilidad de ceros y unos es la misma.

respecto a la velocidad
esto sería probablemente muy rápido, ya que acaba de conseguir un número aleatorio en comparación con el número de bits en el que es más rápido. simplemente depende de tu conversión binaria ahora.

Answer 6

Simplemente lea algo de memoria: tome una sección de n bits de la memoria en bruto. Será bastante aleatorio.

O bien, genere una gran int x aleatoria y simplemente use los valores de bit.

for(int i = (bitcount-1); i >= 0 ; i--) bin += x & (1 << i); 

Answer 7

Si rememeber correctamente, los bits menos significativos son normalmente teniendo un "menos aleatoria" distribución para la mayoría pseuodo generadores de números aleatorios, por lo que el uso de módulo y/o cada bit en el número generado sería malo si están preocupados por la distribución.

(Tal vez debería, al menos, lo que dice google Knuth ...)

Si que mantiene (y es difícil saber, sin conocer exactamente qué algoritmo que está utilizando) sólo tiene que utilizar el bit más alto en cada número generado.

http://en.wikipedia.org/wiki/Pseudo-random

Answer 8

¿Qué tan grande quiere el número de bits generados a ser? Si no es superior a unos pocos millones, y teniendo en cuenta que no está utilizando el generador para la criptografía, entonces creo que la manera más rápida posible sería calcular previamente un gran conjunto de enteros con la distribución correcta, convertirlo a texto archivo como este:

unsigned int numbers[] = 
{ 
    0xABCDEF34, ... 
}; 

y luego compilar la matriz en su programa y recorrerlo un número a la vez.

De esta forma obtienes 32 bits con cada llamada (en un procesador de 32 bits), el tiempo de generación es el más corto posible porque todos los números se generan por adelantado y la distribución es controlada por ti. La desventaja es, por supuesto, que estos números no son aleatorios en absoluto, lo que puede depender o no del contenido del PRNG.

Answer 9

Aquí hay uno muy rápido que codifiqué en Java basado en el algoritmo XORShift de George Marsaglia: ¡obtiene 64 bits a la vez!

/** 
* State for random number generation 
*/ 
private static volatile long state=xorShift64(System.nanoTime()|0xCAFEBABE); 

/** 
* Gets a long random value 
* @return Random long value based on static state 
*/ 
public static final long nextLong() { 
    long a=state; 
    state = xorShift64(a); 
    return a; 
} 

/** 
* XORShift algorithm - credit to George Marsaglia! 
* @param a Initial state 
* @return new state 
*/ 
public static final long xorShift64(long a) { 
    a ^= (a << 21); 
    a ^= (a >>> 35); 
    a ^= (a << 4); 
    return a; 
} 

Answer 10

si sólo se necesita un poco a la vez intenta bool coinToss() { return rand()&1; } sería técnicamente una manera más rápida para generar los bits a causa de la sustitución del 2% con una & 1 que son equivalentes.