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]

ga************* **@gmail.com 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.)

--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at the above domain, - www.

[Walter Roberson]

In article <11************ **********@16g2 000cwy.googlegr oups.com>,
<ga************ ***@gmail.comwr ote:

>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.

--
Is there any thing whereof it may be said, See, this is new? It hath
been already of old time, which was before us. -- Ecclesiastes

[David T. Ashley]

<ga************ ***@gmail.comwr ote in message
news:11******** **************@ 16g2000cwy.goog legroups.com...

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/Pseudor...mber_generator

http://en.wikipedia.org/wiki/List_of...ber_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]

<ga************ ***@gmail.comwr ote:

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]

ga************* **@gmail.com wrote:

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]

"osmium" <r1********@com cast.netwrites:

<ga************ ***@gmail.comwr ote:

>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.

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.

--
Keith Thompson (The_Other_Keit h) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <* <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.

[Mark McIntyre]

On 5 Dec 2006 10:15:13 -0800, in comp.lang.c ,
ga************* **@gmail.com wrote:

>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.programmin g 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]

ga************* **@gmail.com wrote:

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. :)

--
Paul Hsieh
http://www.pobox.com/~qed/
http://bstring.sf.net/

[websnarf]

osmium wrote:

<ga************ ***@gmail.comwr ote:

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.

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

--
Paul Hsieh
http://www.pobox.com/~qed/
http://bstring.sf.net/