CODEWITHSUNDEEP
c++random
dagw
dagw

Reputation: 2618

quickest way to generate random bits

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.

Upvotes: 12

Views: 21594

Answers (11)

Anno
Anno

Reputation: 861

#include <iostream>
#include <bitset>
#include <random>

int main()
{
    const size_t nrOfBits = 256;
    std::bitset<nrOfBits> randomBits;

    std::default_random_engine generator;
    std::uniform_real_distribution<float> distribution(0.0,1.0);

    float randNum;
    for(size_t i = 0; i < nrOfBits; i++)
    {
        randNum = distribution(generator);
        if(randNum < 0.5) {
            randNum = 0;
        } else {
            randNum = 1;
        }
        randomBits.set(i, randNum);
    }

    std::cout <<  "randomBits =\n" << randomBits << std::endl;
    return 0;
}

This took 4.5886e-05s in my test with 256 bits.

Upvotes: 1

user2146937
user2146937

Reputation: 1

if you only need a bit at a time try bool coinToss() { return rand()&1; } It would technically be a faster way to generate bits because of replacing the %2 with a &1 which are equivalent.

Upvotes: 0

mikera
mikera

Reputation: 106351

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

Upvotes: 2

ajanicij
ajanicij

Reputation: 415

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.

Upvotes: 0

KarlP
KarlP

Reputation: 5181

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

Upvotes: 1

RandomNickName42
RandomNickName42

Reputation: 5955

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

Upvotes: 1

Robert Koritnik
Robert Koritnik

Reputation: 105029

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.

Upvotes: 6

Antony Carthy
Antony Carthy

Reputation: 5597

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);

Upvotes: -3

Naveen
Naveen

Reputation: 73443

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.

Upvotes: 0

Sani Huttunen
Sani Huttunen

Reputation: 24385

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.

Upvotes: 3

avakar
avakar

Reputation: 32635

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

Upvotes: 4

Related Questions