Random number generation

[gagan.singh.arora]

Hi there.
I want to generate random numbers with a given probability, say 80%
even and 20% odd. Is it possible to implement such an algorithm in C?

 

[Richard Heathfield]

(e-mail address removed) said:

Hi there.
I want to generate random numbers with a given probability, say 80%
even and 20% odd. Is it possible to implement such an algorithm in C?

Yes, if you can get satisfactorily random bits from somewhere. (If you're
not overly fussy, rand() will supply them.)

 

[Walter Roberson]

I want to generate random numbers with a given probability, say 80%
even and 20% odd. Is it possible to implement such an algorithm in C?

Not in standard C, no. In order to generate random numbers, you
have to have a source of non-deterministic information -- something
that is random. C itself does not provide any true random operations,
and hacks such as getting the time of day or timing a loop tend not to
really be very random at all.

C provides some pseudo-random functions, the actual randomness of
which varies considerably with the implementation. The comp.lang.c FAQ
probably describes several possibilities, such as the
Mersenne Twister ( http://en.wikipedia.org/wiki/Mersenne_twister )
implementations of which are fairly easily available.

 

[David T. Ashley]

Hi there.
I want to generate random numbers with a given probability, say 80%
even and 20% odd. Is it possible to implement such an algorithm in C?

It depends on what you mean by "random".

If you mean "random" in the sense that the algorithm passes certain
statistical tests of randomness, then there may be one or two built into the
C library, but also you can roll your own (see the URLs at the end). There
are at least a few algorithms based on prime moduli, eliptic curves, etc.
The output of these algorithms would be suitable for simulations and similar
activities where an "opponent" is not involved. Every random number
algorithm that I'm aware of has (a)a "seed" or "internal state", and (b)a
finite period in which the generated sequence will repeat. The typical
period is at least 2^31 or so, but I'm sure there are those with much larger
periods. (Algorithms like this are really pseudo-random, not random.)

If you mean "random" in the sense that an attacker cannot guess what the
next number will be ... then you have to be far more careful. (In fact,
RSA's Securid product line is designed to make this very hard.) If you're
dealing with cryptography ... the notion of statistical randomness is
unrelated to the notion of whether an attacker can elicit the algorithm
and/or the seed ... an algorithm can pass statistical tests but not be
suitable if its goal is to prevent guessing the next number. (In fact, you
might want to review the notion of the one-time cryptopad ... these are best
based on physical processes, such as tossing a coin.)

Helpful URLs:

http://en.wikipedia.org/wiki/Pseudorandom_number_generator

http://en.wikipedia.org/wiki/List_of_pseudorandom_number_generators

http://www.rsasecurity.com/node.asp?id=3050

http://www.random.org/

http://random.mat.sbg.ac.at/generators/

http://random.mat.sbg.ac.at/links/rando.html

http://www.agner.org/random/

 

[osmium]

I want to generate random numbers with a given probability, say 80%
even and 20% odd. Is it possible to implement such an algorithm in C?

RAND_MAX is a known constant on a C system. If the number drawn via rand()
is less than 0.8 * RAND_MAX, return a 1 from a function you write, else
return a 0. Ignore blather about real vs. pseudo and bad generator war
stories. A person who was interested in such stuff wouldn't have asked the
question you asked.

 

[Martin Ambuhl]

Hi there.
I want to generate random numbers with a given probability, say 80%
even and 20% odd. Is it possible to implement such an algorithm in C?

Of course it is possible. There are numerous solutions, but here is one
that I believe will be intuitively satisfactory.
Suppose the largest number you want ever to see is 2*N+1 where N <=
RAND_MAX. Generate two random numbers, the first one ('First') scaled
to the range (0,N). If the second is less than .8 * RAND_MAX, return
2*FIRST, otherwise return 2*FIRST + 1.

 

[Keith Thompson]

RAND_MAX is a known constant on a C system. If the number drawn via rand()
is less than 0.8 * RAND_MAX, return a 1 from a function you write, else
return a 0. Ignore blather about real vs. pseudo and bad generator war
stories. A person who was interested in such stuff wouldn't have asked the
question you asked.

I don't think we know that. Someone could have any number of reasons
for wanting the kind of random numbers the OP asked about. He may or
may not be concerned about predictability or the various measure of
randomness.

Truly random numbers are impossible without some kind of hardware
assistance. There are a number of ways to generate pseudo-random
numbers. The standard rand() function is one of them, but in practice
it's often not very good, and it definitely shouldn't be used in an
application where predictability would create a security problem.
There are other, likely better, algorithms that can be implemented in
standard C, and yet other techniques that depend on system-specific
features (<OT>/dev/random, /dev/urandom</OT>). As the saying goes,
"The generation of random numbers is too important to be left to
chance." (attributed to Robert R. Coveyou). Or, as John von Neumann
put it, "Anyone who considers arithmetical methods of producing random
digits is, of course, in a state of sin."

The OP may or may not care about any of this, but it's all good to
know even if it's not immediately relevant.

Also, the original question is ambiguous. If he wanted to get 0 80%
of the time and 1 20% of the time, that would be unambiguous (and
consistent with the requirement as stated), but he said he wants even
and odd numbers respectively 80% and 20% of the time. But he *might*
want numbers over some range, with a bias in favor of even numbers.

To the original poster: Do you care *which* even or odd numbers you
get? Please post a followup and clarify the question for us.

Also, the technique of using the result of rand() and returning 0 the
range 0 to 0.8*RAND_MAX could introduce a bias if the total number of
possible results from RAND_MAX is not a multiple of 5, even if the
results returned by rand() are properly distributed. The bias is
going to be small, since RAND_MAX is at least 32767, so this may or
may not matter. If it does, you can avoid the problem by reducing the
range of numbers; this can be done by rejecting a few values at the
top end of the range, calling rand() repeatedly until you get a number
that's in the range you need. Figuring out what the range should be,
and writing the code to implement this, are left as exercises.

 

[CBFalconer]

Of course it is possible. There are numerous solutions, but here is
one that I believe will be intuitively satisfactory.
Suppose the largest number you want ever to see is 2*N+1 where N <=
RAND_MAX. Generate two random numbers, the first one ('First')
scaled to the range (0,N). If the second is less than .8 * RAND_MAX,
return 2*FIRST, otherwise return 2*FIRST + 1.

Most (not all) random generators will never generate a zero
(because that value gets them into an infinite loop). If you know
this you can take advantage by conditionally subtracting one after
the odd/even decision.

 

[Mark McIntyre]

On 5 Dec 2006 10:15:13 -0800, in comp.lang.c ,

Hi there.
I want to generate random numbers with a given probability, say 80%
even and 20% odd.

by definition, such numbers arent random....

Is it possible to implement such an algorithm in C?

Yes, but its not really a C problem, itsan algorithm problem, and
probably better suited for comp.programming or a maths group.

--
Mark McIntyre

"Debugging is twice as hard as writing the code in the first place.
Therefore, if you write the code as cleverly as possible, you are,
by definition, not smart enough to debug it."
--Brian Kernighan

 

[websnarf]

Hi there.
I want to generate random numbers with a given probability, say 80%
even and 20% odd. Is it possible to implement such an algorithm in C?

Ignoring the problem of the quality of the PRNG in C, this is fairly
straightforward:

#include <stdlib.h>

int rand80_20() {
int r;
do {
if (0 == ((r = rand ()) & 1) || 0 == (rand()&3)) break;
} while(1);
return r;
}

How and why this works is left as an exercise to the reader.

 

[websnarf]

RAND_MAX is a known constant on a C system. If the number drawn via rand()
is less than 0.8 * RAND_MAX, return a 1 from a function you write, else
return a 0.

I don't think the OP was loking for 0 and 1 as the only value outputs.

 

[osmium]

I don't think the OP was loking for 0 and 1 as the only value outputs.

I thought I recognized "earth speak" and on that planet, 100% is all there
is. YMMV.

 

[Walter Roberson]

On 5 Dec 2006 10:15:13 -0800, in comp.lang.c ,
(e-mail address removed) wrote:

by definition, such numbers arent random....

Sure they are (if they could be randomly generated at all).
They just don't have a uniform distribution.

Throw two fair-weighted six-sided dice. The total of the upwards
faces is random in the range 2 to 12 -- but the total will not
have a uniform random distribution. (e.g., 2 and 12 will each have
probability 1/36; 7 will have probability 1/6).

 

[Keith Thompson]

I thought I recognized "earth speak" and on that planet, 100% is all there
is. YMMV.

The OP asked for even and odd, not for 0 and 1. He didn't say enough
about *which* even or odd numbers he wants; until he does, I suggest
there's not much point in guessing what he actually meant.

 

[Richard Tobin]

I want to generate random numbers with a given probability, say 80%
even and 20% odd.

[/QUOTE]

by definition, such numbers arent random....

You have too narrow a definition of random. Random does not imply
any particular distribution of values.

Yes, but its not really a C problem, itsan algorithm problem, and
probably better suited for comp.programming or a maths group.

On the other hand, it's pretty simple. First generate a random number
to choose whether to pick an odd or even number - for example,
generate a random integer and if it's equal to 0 mod 5 you're going to
generate an odd number, otherwise an even one. Then generate another
integer - to make it even, double it; to make it odd, double it and
add one.

Of course, you probably really want numbers in some range, so you'll
have to modify it a bit.

-- Richard

 

[CBFalconer]

.... snip ...

Throw two fair-weighted six-sided dice. The total of the upwards
faces is random in the range 2 to 12 -- but the total will not
have a uniform random distribution. (e.g., 2 and 12 will each have
probability 1/36; 7 will have probability 1/6).

Not if you let me use MY dice

 

[Keith Thompson]

Most (not all) random generators will never generate a zero
(because that value gets them into an infinite loop). If you know
this you can take advantage by conditionally subtracting one after
the odd/even decision.

I'd expect that to be the case only for RNGs where the value returned
is the same size as the entire state.

 

[websnarf]

Most (not all) random generators will never generate a zero
(because that value gets them into an infinite loop).

I am not aware of *any* random number generator in practical usage with
this supposed property. Can you cite an example of one?

 

[pete]

Hi there.
I want to generate random numbers with a given probability, say 80%
even and 20% odd. Is it possible to implement such an algorithm in C?

/* BEGIN new.c */

#include <stdio.h>
#include <stdlib.h>

int even80odd20(void);

int main(void)
{
int x, even, odd, e8o2;

for (even = odd = x = 0; x != 100; ++x) {
e8o2 = even80odd20();
printf("%d\n", e8o2);
if ((e8o2 & 1) != 0) {
++odd;
} else {
++even;
}
}
printf("\n%d even, %d odd\n", even, odd);
return 0;
}

int even80odd20(void)
{
int r = rand();

return RAND_MAX / 5 * 4 > r ? r & ~1 : r | 1;
}

/* END new.c */

 

[CBFalconer]

I am not aware of *any* random number generator in practical usage with
this supposed property. Can you cite an example of one?

The simplified linear congruential r = mr % rmax; (the addend is
0). Also those based on polynomials, eg a CRC16 generator.

I didn't say they were good prngs.