2

I was wondering if there is a smart way to find out

There is a 1/4 chance something happens.

I know we can do this with rand() % 4 and checking if it is equal to 0, but is there a way without using rand()? In c++, thanks.

Eric Schoonover
  • 47,184
  • 49
  • 157
  • 202
  • 1
    don't do "rand()%" as the low order bits of rand are highly predictable. IIRC it goes: even, odd, even, odd... – BCS Nov 28 '08 at 22:52
  • I am not sure that I understand what you are asking for. ( My Random Number Generator pseudocode got downvoted in another posting. http://stackoverflow.com/questions/298301/roulette-wheel-selection-algorithm#299524 ) – Mark Stock Nov 29 '08 at 03:46
  • I think you mean "Best way to calculate if something which has a 1/4 chance of happening will happen", and not what you've written. There is no way to calculate the chance of something happening without knowing what it is. – ShreevatsaR Nov 29 '08 at 07:28
  • Why "without rand()"? Please clarify. – peterchen Nov 29 '08 at 19:28

11 Answers11

11

If you mean you want to avoid the inherent crappiness of many rand() implementations, you should probably look into the Boost Random library, which has several high-quality pRNGs (pseudo-random number generators), and many ways to control the output. This library is also present in slightly modified form in std::tr1.

Bill the Lizard
  • 398,270
  • 210
  • 566
  • 880
coppro
  • 14,338
  • 5
  • 58
  • 73
  • 3
    I would like to see just ONE question about C++ that isn't answered with "Use boost:;something_or_other" :-) – paxdiablo Nov 28 '08 at 23:24
9

Never ever use % for truncating a PRNG value into a range. Most PRNGs have relatively non-random lower order bits.

For your case, use a division (RAND_MAX / n) like BCS suggests.

Barry Kelly
  • 41,404
  • 5
  • 117
  • 189
5

random number generator

Community
  • 1
  • 1
Greg Hewgill
  • 951,095
  • 183
  • 1,149
  • 1,285
4
rand() < RAND_MAX/n;

pick a better rand() than C's if you don't like C's standard rand().

BCS
  • 75,627
  • 68
  • 187
  • 294
3

You could write your own rand. ( dont do it ).
You could grab the tickcount. ( dont do it too often ).
You could just count, and every fourth call return true.

You should probably just call rand().

Sanjaya R
  • 6,246
  • 2
  • 17
  • 19
3

I don't know much C++, so I might be wrong. But it seems rand() return a value between 0 and RAND_MAX-1. So maybe you could do something like this:

double odds = .25;

if(rand() <= RAND_MAX * odds) {
    // there should be .25 chance of entering this condition
}

PS: Maybe this requires some casting.

leemes
  • 44,967
  • 21
  • 135
  • 183
Juan Pablo Califano
  • 12,213
  • 5
  • 29
  • 42
1

Why not use rand()? If you are concerned about "true" randomness vs. pseudo randomness, you can try using physical sources of random bits. Much more complicated, and usually unnecessary.

Yuval F
  • 20,565
  • 5
  • 44
  • 69
  • No physical method of generating random bits is certified by NIST for use in FIPS-140-2 compliant devices. Only pseudorandom techniques are acceptable (see Annex C). – Peter K. Nov 29 '08 at 00:32
1

You could use another type of RNG such as the Mersenne twister which has better overall entropy. I also hear good thing about Multuply with Carry RNGs.

Evan Teran
  • 87,561
  • 32
  • 179
  • 238
1

4 is a special case. You can assume that your PRNG has got 50% chances of outputting an even number, which is the case - I think - for the LCG of the libc (rand). The probability of outputting an even number twice is therefore 25%.

Therefore...

bool rand_afourth(void)
{
    return !!((rand() & 1) & (rand() & 1));
}

And now for the pedantic...

What you want to do is to have an uniform random generated, but restricted to a certain range, in this case an entropy of 4. If your PRNG has, say, an entropy of 32-bit, you cannot be certain that computing the output mod 4 will work as expected. This require a bit more work.

Fortunately, this work has already been implemented in the boost library.

boost::uniform_int<> aFourth(1,4)

And you would for example say "ok" everytime you get 1 (or 2, 3, 4, as you fancy).

But you may not want to use the boost library. Then, simply look at the code of uniform_int and reproduce the behaviour. Talents imitate, geniuses steal. ;)

Edouard A.
  • 6,100
  • 26
  • 31
  • Any random number generator should generate even values 50% of the time, otherwise it's not random. That being said, the low bits of PRNGs are notoriously predictable, so your method is likely worse than simple rand() % 4 == 0, for randomness, and is definitely slower and less understable. – Eclipse Nov 30 '08 at 05:26
  • Which PRNG are you talking about? All the bits of the libc rand() function are predictable if you have any element of the sequence. If the low bits of your PRNG have special properties, this means your PRNG is problematic in the first place. Maybe I didn't understand your comment? – Edouard A. Nov 30 '08 at 21:40
  • See Barry Kelly's answer above. – Eclipse Dec 01 '08 at 16:51
0

Umm... write your own rand()? You will need some kind of random function!

Vilx-
  • 104,512
  • 87
  • 279
  • 422
0

Try:

static int r = 0;
: : :
if ((r = (r+1)%4) == 0) {
    // do something.
}

Then you'll find it gives you a perfect 25% probability of something happening (assuming you execute the if-statement a multiple of four times.

</humor>

paxdiablo
  • 854,327
  • 234
  • 1,573
  • 1,953