modo più rapido per generare bit casuali

Question

Quale sarebbe il modo più veloce per generare un gran numero di bit (pseudo-) casuali. Ogni bit deve essere indipendente ed essere zero o uno con uguale probabilità. Ho potuto ovviamente fare qualche variazione sul

randbit=rand()%2; 

ma ritengo come ci dovrebbe essere un modo più veloce, generando più bit casuali da ogni chiamata al generatore di numeri casuali. Idealmente mi piacerebbe ottenere un int o un char in cui ogni bit è casuale e indipendente, ma sono anche possibili altre soluzioni.

L'applicazione non è di natura crittografica, quindi la casualità non è un fattore importante, mentre la velocità e la corretta distribuzione sono importanti.

Answer 1

Dai un'occhiata a Boost.Random, in particolare boost::uniform_int<>.

Answer 2

Come dici tu generi solo numeri interi casuali.
Quindi avete 32 bit casuali con uno e zero tutti ugualmente probabili.

Ottenere i bit in un ciclo:

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

Ripetere questo per tutte le volte è necessario per ottenere la giusta quantità di bit.

Answer 3

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

noti l'uso dell'attributo [ThreadStatic], tale scopo del nuovo filo di, nessun impuntamento gestire automaticamente. Questo è l'unico modo per garantire un sistema di lock-back SMP casuale e ad alte prestazioni.

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

Answer 4

È possibile generare un numero casuale e continuare a shifitng destra e testare il bit meno significativo per ottenere i bit casuali invece di fare un'operazione mod.

Answer 5

convertire un numero casuale in binario
Perché non avere un solo numero (di dimensioni adeguate per ottenere abbastanza bit è necessario) e quindi convertirlo in binario. In realtà otterrai bit da un numero casuale, il che significa che sono anche casuali.

Gli zeri e quelli hanno anche la probabilità del 50%, poiché si prendono tutti i numeri compresi tra 0 e qualche limite 2^n e il conteggio del numero di zeri e di quelli sono uguali> il che significa che la probabilità di zeri e uno è la stessa.

per quanto riguarda la velocità
questo probabilmente sarebbe molto veloce, dal momento che ottenere solo un numero casuale rispetto al numero di bit in esso è più veloce. dipende solo dalla tua conversione binaria ora.

Answer 6

Basta leggere un po 'di memoria - prendere una sezione n bit di memoria grezza. Sarà piuttosto casuale.

In alternativa, generare un int x casuale di grandi dimensioni e utilizzare solo i valori di bit.

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

Answer 7

Se Rememeber correttamente, i bit meno significativi sono normalmente avendo un "meno casuale" distribuzione per più pseuodo generatori di numeri casuali, in modo da utilizzare modulo e/o ogni bit del numero generato sarebbe male se sono preoccupati per la distribuzione.

(Forse si dovrebbe almeno google quello che dice Knuth ...)

Se che tiene (e la sua difficile dire senza sapere esattamente cosa si sta utilizzando l'algoritmo) basta usare il più alto bit in ogni numero generato.

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

Answer 8

Quanto grande cosa avete bisogno il numero di bit generati per essere? Se non è più grande di un paio di milioni, e tenendo presente che non si sta utilizzando il generatore per la crittografia, quindi penso che il modo più veloce possibile sarebbe quella di precompute un grande insieme di numeri interi con la distribuzione corretta, convertirlo in un testo file in questo modo:

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

e quindi compilare la matrice nel vostro programma e passare attraverso di essa un numero alla volta.

In questo modo si ottengono 32 bit per ogni chiamata (su un processore a 32 bit), il tempo di generazione è il più breve possibile perché tutti i numeri vengono generati in anticipo e la distribuzione è controllata dall'utente. Il rovescio della medaglia è, naturalmente, che questi numeri non sono affatto casuali, che a seconda di ciò che si sta usando il PRNG potrebbero non avere importanza.

Answer 9

Ecco uno molto veloce ho codificato in Java sulla base di un algoritmo XORShift di George Marsaglia: si ottiene 64 bit alla volta!

/** 
* 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

se avete solo bisogno di un po 'alla volta provare bool coinToss() { return rand()&1; } Si sarebbe tecnicamente un modo più veloce per generare i bit a causa della sostituzione del% 2 con un & 1 che sono equivalenti.