467,075 Members | 988 Online
Bytes | Developer Community
Ask Question

Home New Posts Topics Members FAQ

Post your question to a community of 467,075 developers. It's quick & easy.

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 <d1*******************@news.demon.co.uk>,
Ken Hagan <K.*****@thermoteknix.co.uk> 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" <ma**********@gmail.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" <no****@digitalraid.com> 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" <no****@digitalraid.com> 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" <As***@techemail.com> 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" <v.********@comAcast.net> 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" <kb******@gascad.at> 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 <v.********@comAcast.net> wrote in message news:<pg*******************@newsread1.mlpsca01.us. to.verio.net>...
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 <v.********@comAcast.net> wrote in message news:<pg*******************@newsread1.mlpsca01.us. to.verio.net>...
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" <ra******@t-online.de> 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" <Ch*********@no-spam.cern.ch> 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" <pe********@acm.org> 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" <pe********@acm.org> 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" <As***@techemail.com> 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" <ma**********@gmail.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.

Similar topics

10 posts views Thread by Leon | last post: by
104 posts views Thread by fieldfallow | last post: by
12 posts views Thread by Jim Michaels | last post: by
22 posts views Thread by gagan.singh.arora@gmail.com | last post: by
8 posts views Thread by Daniel | last post: by
21 posts views Thread by chico_yallin@yahoo.com | last post: by
7 posts views Thread by bipi | last post: by
14 posts views Thread by kittikun@gmail.com | last post: by
24 posts views Thread by pereges | last post: by
By using this site, you agree to our Privacy Policy and Terms of Use.