quickest way to generate random bits

Question

What would be the fastest way to generate a large number of (pseudo-)random bits. Each bit must be independent and be zero or one with equal probability. I could obviously do some variation on

randbit=rand()%2;

but I feel like there should be a faster way, generating several random bits from each call to the random number generator. Ideally I'd like to get an int or a char where each bit is random and independent, but other solutions are also possible.

The application is not cryptographic in nature so strong randomness isn't a major factor, whereas speed and getting the correct distribution is important.

Answer 1

Take a look at Boost.Random, especially boost::uniform_int<>.

Answer 2

As you say just generate random integers.
Then you have 32 random bits with ones and zeroes all equally probable.

Get the bits in a loop:

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

Repeat this for as many times you need to to get the correct amount of bits.

Answer 3

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

Note the use of the [ThreadStatic] attribute, this object automatically handle's new thread's, no locking. That's the only way your going to ensure high-performance random, SMP lockfree.

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

Answer 4

You can generate a random number and keep on right shifitng and testing the least significant bit to get the random bits instead of doing a mod operation.

Answer 5

convert a random number into binary
Why not get just one number (of appropriate size to get enough bits you need) and then convert it to binary. You'll actually get bits from a random number which means they are random as well.

Zeros and ones also have the probability of 50%, since taking all numbers between 0 and some 2^n limit and counting the number of zeros and ones are equal > meaning that probability of zeros and ones is the same.

regarding speed
this would probably be very fast, since getting just one random number compared to number of bits in it is faster. it purely depends on your binary conversion now.

Answer 6

Just read some memory - take a n bit section of raw memory. It will be pretty random.

Alternatively, generate a large random int x and just use the bit values.

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

Answer 7

If I rememeber correctly, the least significant bits are normally having a "less random" distribution for most pseuodo random number generators, so using modulo and/or each bit in the generated number would be bad if you are worried about the distribution.

(Maybe you should at least google what Knuth says...)

If that holds ( and its hard to tell without knowing exactly what algorithm you are using) just use the highest bit in each generated number.

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

Answer 8

How large do you need the number of generated bits to be? If it is not larger than a few million, and keeping in mind that you are not using the generator for cryptography, then I think the fastest possible way would be to precompute a large set of integers with the correct distribution, convert it to a text file like this:

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

and then compile the array into your program and go through it one number at a time.

That way you get 32 bits with every call (on a 32-bit processor), the generation time is the shortest possible because all the numbers are generated in advance, and the distribution is controlled by you. The downside is, of course, that these numbers are not random at all, which depending on what you are using the PRNG for may or may not matter.

Answer 9

Here's a very fast one I coded in Java based on George Marsaglia's XORShift algorithm: gets you 64 bits at a time!

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