449,322 Members | 1,375 Online Need help? Post your question and get tips & solutions from a community of 449,322 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
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>, 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

 P: n/a

 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" 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 (/dev/random, /dev/urandom). 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 San Diego Supercomputer Center <* 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 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:

 P: n/a

 P: n/a In article <4p********************************@4ax.com>, Mark McIntyre 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" osmium wrote: >> San Diego Supercomputer Center <* 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. Dec 6 '06 #14

 P: n/a In article <4p********************************@4ax.com>, Mark McIntyre >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, andprobably 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 San Diego Supercomputer Center <* 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 #include 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. 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 isone 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. 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 isone 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 >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 upwardsfaces is random in the range 2 to 12 -- but the total will nothave a uniform random distribution. (e.g., 2 and 12 will each haveprobability 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

### This discussion thread is closed

Replies have been disabled for this discussion. 