467,075 Members | 988 Online

# Random numbers something insatiable ?

 Can you tell me what happens inside CPU when I rand() ? Where can I find the true rand function implemented ? I have heard that rand() in C/C++ is n't a good one but why it isn't a good one, are they lying to me ? Why do they have to do that ? Thank you MnConly Jul 23 '05 #1
• viewed: 1528
Share:
23 Replies
 MConly wrote: Can you tell me what happens inside CPU when I rand() ? You should be able to see the implementation of this function in the source code for the C run-time library. It ships with almost every compiler nowadays. Where can I find the true rand function implemented ? In the source. "Use the Source, Luke!" I have heard that rand() in C/C++ is n't a good one but why it isn't a good one, are they lying to me ? Who? Why do they have to do that ? Who? Jul 23 '05 #2
 MConly wrote: Can you tell me what happens inside CPU when I rand() ? Nothing special. It is just a formula that gets executed. Where can I find the true rand function implemented ? There is none. The language standards don't specify which formula to use. But usual rand() implementations use a very simple formula. I have heard that rand() in C/C++ is n't a good one but why it isn't a good one, First of all you need to understand that 'randomness' in a computer is just a statistical property. That means: given eg. 1000 such numbers, one can use a statistical test to check if those numbers have the statistical properties of randomness (whereby nobody really knows what randomness really means). When doing so, one might notice that the result of rand() doesn't pass all those tests. Especially many implementations of rand() are known to be not that good in the low order bits of the numbers. So if one uses the results of rand() and clears the high order bits of all numbers (for some definition of 'high order') it may be that some pattern shows up in the result sequence. And if there is a pattern, then one can predict the outcome of the next random number by knowing the past history. are they lying to me ? Why do they have to do that ? Because it isn't that trivial to come up with good formulas for generating sequences of random numbers that are * fast * of good quality The point is: With a little bit of care, rand() is good enough for doing most homemade programming. If you need to program for a casino, where better random number generators are needed, you already have the knowledge to implement a better random number generator. -- Karl Heinz Buchegger kb******@gascad.at Jul 23 '05 #3
 Victor Bazarov wrote: that rand() in C/C++ is n't a good one but why it isn't a good one, are they lying to me ? Who? Why do they have to do that ? Who? They... You know, the bastards! Jul 23 '05 #4
 MConly wrote: I have heard that rand() in C/C++ is n't a good one but why it isn't a good one, are they lying to me ? I have heard that the C standard (or its rationale) *suggested* a not very good algorithm, which some implementations copied. This may be the origin of the folklore you've heard, but there's nothing to stop a competent vendor using a decent algorithm. If you don't know why rand() is bad, and it probably isn't, you are unlikely to do any better. Jul 23 '05 #5
 Much more on random number generators in the Numerical recipes book. You can buy the C++ edition in the bookstore, or browse the C edition on line at http://www.library.cornell.edu/nr/bookcpdf.html Jul 23 '05 #6
 In article , Ken Hagan writes: |> MConly wrote: |> > I have heard |> > that rand() in C/C++ is n't a good one but why it isn't a good one, |> > are they lying to me ? |> |> I have heard that the C standard (or its rationale) *suggested* a not |> very good algorithm, which some implementations copied. This may be |> the origin of the folklore you've heard, but there's nothing to stop |> a competent vendor using a decent algorithm. It's worse that that - the C standard effectively recommends an unnecessarily bad one. I tried to get it transferred to the Rationale, but failed :-( |> If you don't know why rand() is bad, and it probably isn't, you are |> unlikely to do any better. Right. Regards, Nick Maclaren. Jul 23 '05 #7
 In article <11**********************@o13g2000cwo.googlegroups .com>, "wi******@hotmail.com" writes: |> |> Much more on random number generators in the Numerical recipes book. |> You can buy the C++ edition in the bookstore, or browse the C edition |> on line at http://www.library.cornell.edu/nr/bookcpdf.html Please don't recommend that. The first version contained the worst generators that I have ever seen published, and the second is still dire. Regards, Nick Maclaren. Jul 23 '05 #8
 "Matthias Kaeppler" wrote in message news:d1*************@news.t-online.com... Victor Bazarov wrote: that rand() in C/C++ is n't a good one but why it isn't a good one, are they lying to me ? Who? Why do they have to do that ? Who? They... You know, the bastards! You mean the ones that killed Kenny??? -Howard Jul 23 '05 #9
 Howard wrote: "Matthias Kaeppler" wrote in message news:d1*************@news.t-online.com...Victor Bazarov wrote:that rand() in C/C++ is n't a good one but why it isn't a good one,are they lying to me ? Who? Why do they have to do that ? Who?They... You know, the bastards! You mean the ones that killed Kenny??? -Howard :D Jul 23 '05 #10
 "MConly" wrote in message news:7f**************************@posting.google.c om... Can you tell me what happens inside CPU when I rand() ? A sequence of machine codes is executed - the same way any other formula is evaluated. Where can I find the true rand function implemented ? Well, the big question to start with is - which and what is the "true" rand function? I´m not sure whether the C standard makes any requirements of the implementation but I didn´t find anything in the last C++ standard. Anyway, randomness is a property which is an implicit property of, e.g., quantum mechanical processes and other processes in nature. However, with a deterministic machine (=computer) there is no way to get "true" randomness. Hence, there are formulas that will give you a sequence of pseudo-random numbers that have certain statistical properties, that are used to prove that they are more (or mostly less) random. One way to produce such sequences is the simple MPLCG algorithm: x(n+1) = (a*x(n) + c) % b with a, b, c being constants another would be the Fibonacci generator: x(n+1) = x(n) + x(n-1) % a However, the period length of the sequence is closely connected to the choice of the constants and thus crucial for the "randomness". If you´ve got a short period you´ll get the same sequence repeated very soon, which is certainly not what you´re looking for. A natural question is now what is a "good" random number? This is actually rather difficult to answer exhaustively (especially in such a limited context), so let´s take a look at what is a "bad" random number. As you can easily see from the formulas above x(n+1) is somehow related to x(n). But it can (and most probably will) be also related to x(n-1) and also to x(n-2), etc.... This behavior is called correlation, meaning that not only neighboring elements of the sequence are related but the relation spans over a larger distance. As soon as you have correlation you do not have true randomness anymore. In quantum mechanics (= true randomness) the next state is only related to the current state of a system but not to states it had farther back in time. With computers & random number generators you´ll try to keep correlation as low as possible. One of the tests that random number generators have to pass is a test for correlation, which causes certain repetitive patterns in the sequences. I have heard that rand() in C/C++ is n't a good one but why it isn't a good one, are they lying to me ? Hmm, you should never trust "them" - you know "they" lead to the dark side ;-) Most implementations of rand() suffer from rather strong correlation. See the post of Karl Heinz Buchegger for an explanation. Why do they have to do that ? Why they have to lie? I guess it´s in their nature. Cheers Chris Jul 23 '05 #11
 "Victor Bazarov" wrote in message news:pg*******************@newsread1.mlpsca01.us.t o.verio.net... MConly wrote: Can you tell me what happens inside CPU when I rand() ? You should be able to see the implementation of this function in the source code for the C run-time library. It ships with almost every compiler nowadays. Where can I find the true rand function implemented ? In the source. "Use the Source, Luke!" > I have heard that rand() in C/C++ is n't a good one but why it isn't a good one, are they lying to me ? Who? Why do they have to do that ? Who? They, you know, - beware of the dark side ;-) Chris Jul 23 '05 #12
 "Karl Heinz Buchegger" wrote in message news:42***************@gascad.at... MConly wrote: Can you tell me what happens inside CPU when I rand() ? Nothing special. It is just a formula that gets executed. Where can I find the true rand function implemented ? There is none. The language standards don't specify which formula to use. But usual rand() implementations use a very simple formula. I have heard that rand() in C/C++ is n't a good one but why it isn't a good one, First of all you need to understand that 'randomness' in a computer is just a statistical property. That means: given eg. 1000 such numbers, one can use a statistical test to check if those numbers have the statistical properties of randomness (whereby nobody really knows what randomness really means). [SNIP] To the OP: Actually there is a "definition" of randomness - yes I know that sounds more than awkward ;-) A random process is a physical process having the property, given the present, that the future outcome (determined by a certain probability) is independent of the past. Sounds very complicated and there are many tricky mathematical terms for it ;-) Anyway, it´s in principle what nature shows us in quantum mechanical processes, which have absolutely no correlation. By the implementation of a formula that gives a sequence of numbers, such randomness is impossible to achieve. For a more detailed of the required properties of a RNG the OP might refer to Don Knuth´s excellent book ("The art of computer programming") Volume 2. Cheers Chris Jul 23 '05 #13
 Victor Bazarov wrote in message news:... Who? BRADLEY L. JONES--site manager of CG-- I come to ask exactly what has been written by him (in his another username as "Kevin Halls") at his site, oh well, at where he is a representative for K and B 's joint-venture in close connection with J's corp. You can come there to check it out... Jul 23 '05 #14
 MConly wrote: Victor Bazarov wrote in message news:...Who? BRADLEY L. JONES--site manager of CG-- I come to ask exactly what has been written by him (in his another username as "Kevin Halls") at his site, oh well, at where he is a representative for K and B 's joint-venture in close connection with J's corp. You can come there to check it out... Come where? Jul 23 '05 #15
 Chris Theis wrote: Anyway, randomness is a property which is an implicit property of, e.g., quantum mechanical processes and other processes in nature. However, with a deterministic machine (=computer) there is no way to get "true" randomness. Actually, most modern PCs do have a hardware RNG that provides you with true randomness, using AFAIK something like the thermal noise of a transistor to generate the values. Jul 23 '05 #16
 "Rolf Magnus" wrote in message news:d1*************@news.t-online.com... Chris Theis wrote: Anyway, randomness is a property which is an implicit property of, e.g., quantum mechanical processes and other processes in nature. However, with a deterministic machine (=computer) there is no way to get "true" randomness. Actually, most modern PCs do have a hardware RNG that provides you with true randomness, using AFAIK something like the thermal noise of a transistor to generate the values. True randomness can of course be achieved by thermal noise of a transistor or other electronic devices, which is fed to a Schmitt trigger and sampled. I know of a number of devices that can be plugged into your PC (via USB or whatever port) and create this randomness, which is mostly used in cryptography. However, I doubt (and haven´t seen it until now, but this doesn´t mean anything ;-) ) that a standard computer comes equipped with such a device. Even if it is, it would be a disaster if rand() would use this device instead of a formula ;-) Cheers Chris Jul 23 '05 #17
 "Chris Theis" wrote in message news:d1**********@sunnews.cern.ch... [SNIP] Actually, most modern PCs do have a hardware RNG that provides you with true randomness, using AFAIK something like the thermal noise of a transistor to generate the values. True randomness can of course be achieved by thermal noise of a transistor or other electronic devices, which is fed to a Schmitt trigger and sampled. I know of a number of devices that can be plugged into your PC (via USB or whatever port) and create this randomness, which is mostly used in cryptography. However, I doubt (and haven´t seen it until now, but this doesn´t mean anything ;-) ) that a standard computer comes equipped with such a device. Even if it is, it would be a disaster if rand() would use this device instead of a formula ;-) Cheers Chris I already have to correct myself, just finding out that there are VIA C3 chipsets and Intel chipsets that do supply such hardware RNG´s. My apologies Rolf, ´cause I did not know that they are already available in such standard configurations. To the OP: These chipsets are there but will not be used by the standard rand() implementation, which is actually a good thing. Pseudo-random generators have the kind property of reproducibility, which is extremely important in the business of simulation development. Cheers Chris Jul 23 '05 #18
 Chris Theis wrote: Even if it is, it would be a disaster if rand() would use this device instead of a formula ;-) It also wouldn't conform to the specification, which requires that the same seed generate the same sequence. -- Pete Becker Dinkumware, Ltd. (http://www.dinkumware.com) Jul 23 '05 #19
 "Pete Becker" wrote in message news:Dq********************@giganews.com... Chris Theis wrote: Even if it is, it would be a disaster if rand() would use this device instead of a formula ;-) It also wouldn't conform to the specification, which requires that the same seed generate the same sequence. Exactly, and this would make the life of all simulation developers even harder ;-) Do you happen to know whether there is any specific requirement (or at least some common agreement) regarding the implementation of rand() because in the C++ standard I couldn´t find anything at all. Cheers Chris Jul 23 '05 #20
 Chris Theis wrote: Do you happen to know whether there is any specific requirement (or at least some common agreement) regarding the implementation of rand() because in the C++ standard I couldn´t find anything at all. There's nothing of the sort. The C standard recommended a not particularly good generator, but I don't think there are many libraries out there now that use it. -- Pete Becker Dinkumware, Ltd. (http://www.dinkumware.com) Jul 23 '05 #21
 Chris Theis wrote: "Pete Becker" wrote in message news:Dq********************@giganews.com... Chris Theis wrote: > Even if it is, it would be a disaster if rand() would use > this device instead of a formula ;-) > It also wouldn't conform to the specification, which requires that the same seed generate the same sequence. Exactly, and this would make the life of all simulation developers even harder ;-) Same if you want to do animated graphics with procedural textures (like e.g. a wood texture). If those textures are generated based on random values, the animation will look strange if the look of the texture changes randomly. Jul 23 '05 #22
 "MConly" wrote in message news:7f**************************@posting.google.c om... Can you tell me what happens inside CPU when I rand() ? It generates heat ;-) Where can I find the true rand function implemented ? www.random.org. I have heard that rand() in C/C++ isn't a good one but why it isn't a good one, are they lying to me ? Probably not. Check Don Knuth's "The Art of Computer Programming" for some insight into why random numbers are difficult to generate in truly random fashion. Why do they have to do that ? Q: What is the difference between a computer sales person and a car sales person? A: The latter knows he is lying. dk Jul 23 '05 #23
 "wi******@hotmail.com" wrote in message news:11**********************@o13g2000cwo.googlegr oups.com... Much more on random number generators in the Numerical recipes book. You can buy the C++ edition in the bookstore, or browse the C edition on line at http://www.library.cornell.edu/nr/bookcpdf.html Nope. The best source for random number generators on the net is: www.random.org. (quelle surprise!) dk Jul 23 '05 #24

### This discussion thread is closed

Replies have been disabled for this discussion.