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?  
Share this Question
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.  
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 nondeterministic 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 pseudorandom 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  
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 pseudorandom, 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 onetime 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/  
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.  
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.  
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 pseudorandom
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 systemspecific
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.  
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  
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/  
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/  
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.  
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 fairweighted sixsided 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  
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.  
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>  
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.  
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.  
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/  
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  
P: n/a

Walter Roberson wrote:
>
.... snip ...
>
Throw two fairweighted sixsided 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>  
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>  
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/  
P: n/a

On Wed, 6 Dec 2006 00:09:27 +0000 (UTC), in comp.lang.c , ro******@ibd.nrccnrc.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 fairweighted sixsided 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  
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**N1) values, rather than the expected
RAND_MAX+1 (usually 2**N), i.e. 0 through RAND_MAX.
Richard   This discussion thread is closed Replies have been disabled for this discussion.   Question stats  viewed: 2959
 replies: 22
 date asked: Dec 5 '06
