By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
424,847 Members | 2,392 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 424,847 IT Pros & Developers. It's quick & easy.

Random number generation

P: n/a
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?

Dec 5 '06 #1
Share this Question
Share on Google+
22 Replies


P: n/a
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.
Dec 5 '06 #2

P: n/a
In article <11**********************@16g2000cwy.googlegroups. com>,
<ga***************@gmail.comwrote:
>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
Dec 5 '06 #3

P: n/a
<ga***************@gmail.comwrote in message
news:11**********************@16g2000cwy.googlegro ups.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/


Dec 5 '06 #4

P: n/a
<ga***************@gmail.comwrote:
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.
Dec 5 '06 #5

P: n/a
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.
Dec 5 '06 #6

P: n/a
"osmium" <r1********@comcast.netwrites:
<ga***************@gmail.comwrote:
>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_Keith) 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.
Dec 5 '06 #7

P: n/a
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.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
Dec 5 '06 #8

P: n/a
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/

Dec 5 '06 #9

P: n/a
osmium wrote:
<ga***************@gmail.comwrote:
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/

Dec 5 '06 #10

P: n/a
<we******@gmail.comwrote:
osmium wrote:
><ga***************@gmail.comwrote:
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.
I thought I recognized "earth speak" and on that planet, 100% is all there
is. YMMV.
Dec 5 '06 #11

P: n/a
In article <4p********************************@4ax.com>,
Mark McIntyre <ma**********@spamcop.netwrote:
>On 5 Dec 2006 10:15:13 -0800, in comp.lang.c ,
ga***************@gmail.com wrote:
>>I want to generate random numbers with a given probability, say 80%
even and 20% odd.
>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).
--
"No one has the right to destroy another person's belief by
demanding empirical evidence." -- Ann Landers
Dec 5 '06 #12

P: n/a
"osmium" <r1********@comcast.netwrites:
<we******@gmail.comwrote:
>osmium wrote:
>><ga***************@gmail.comwrote:
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.

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.

--
Keith Thompson (The_Other_Keith) 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.
Dec 6 '06 #13

P: n/a
Martin Ambuhl wrote:
ga***************@gmail.com wrote:
>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.
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.

--
Chuck F (cbfalconer at maineline dot net)
Available for consulting/temporary embedded and systems.
<http://cbfalconer.home.att.net>
Dec 6 '06 #14

P: n/a
In article <4p********************************@4ax.com>,
Mark McIntyre <ma**********@spamcop.netwrote:
>>I want to generate random numbers with a given probability, say 80%
even and 20% odd.
>by definition, such numbers arent random.... :-)
You have too narrow a definition of random. Random does not imply
any particular distribution of values.
>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.
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

--
"Consideration shall be given to the need for as many as 32 characters
in some alphabets" - X3.4, 1963.
Dec 6 '06 #15

P: n/a
CBFalconer <cb********@yahoo.comwrites:
[...]
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.

--
Keith Thompson (The_Other_Keith) 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.
Dec 6 '06 #16

P: n/a
CBFalconer wrote:
Martin Ambuhl wrote:
ga***************@gmail.com wrote:
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.

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?

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

Dec 6 '06 #17

P: n/a
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?
/* 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 */
--
pete
Dec 6 '06 #18

P: n/a
Walter Roberson wrote:
>
.... 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 :-)

--
Chuck F (cbfalconer at maineline dot net)
Available for consulting/temporary embedded and systems.
<http://cbfalconer.home.att.net>

Dec 6 '06 #19

P: n/a
we******@gmail.com wrote:
CBFalconer wrote:
>Martin Ambuhl wrote:
>>ga***************@gmail.com wrote:

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.

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

--
Chuck F (cbfalconer at maineline dot net)
Available for consulting/temporary embedded and systems.
<http://cbfalconer.home.att.net>
Dec 6 '06 #20

P: n/a
CBFalconer wrote:
we******@gmail.com wrote:
CBFalconer wrote:
Martin Ambuhl wrote:
ga***************@gmail.com wrote:

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.

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?

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. :-)
I wouldn't say they were prngs at all. And I'm not aware of anyone
else calling them that either. As far as I know, all serious PRNGs
will output 0 (or any other value in range) exactly 1/(1+RANDMAX)
proportion of the time.

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

Dec 6 '06 #21

P: n/a
On Wed, 6 Dec 2006 00:09:27 +0000 (UTC), in comp.lang.c ,
ro******@ibd.nrc-cnrc.gc.ca (Walter Roberson) wrote:
>In article <4p********************************@4ax.com>,
Mark McIntyre <ma**********@spamcop.netwrote:
>>On 5 Dec 2006 10:15:13 -0800, in comp.lang.c ,
ga***************@gmail.com wrote:
>>>I want to generate random numbers with a given probability, say 80%
even and 20% odd.
>>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.
For some reason I read the OP's requirement as wanting 80% to be even,
and 20% to be odd.
>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).
You have two sets of random numbers here. :-)

FWIW I know what you're saying. BTW its probably how I'd solve the
OP's problem - generate two sets of random data, and an algo for
weighting them.
--
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
Dec 6 '06 #22

P: n/a
CBFalconer <cb********@yahoo.comwrote:
Martin Ambuhl wrote:
ga***************@gmail.com wrote:
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.

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.
The Standard rand() can generate values from 0 to RAND_MAX, though.
While I don't think that means that it _must_ sometimes return 0, I'd
consider a version of rand() (or a replacement for it) that didn't to be
poor design. Amongst other reasons, you now have a function which
returns RAND_MAX (usually 2**N-1) values, rather than the expected
RAND_MAX+1 (usually 2**N), i.e. 0 through RAND_MAX.

Richard
Dec 8 '06 #23

This discussion thread is closed

Replies have been disabled for this discussion.