Random numbers something insatiable ?

M

MConly

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
 
V

Victor Bazarov

MConly said:
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?
 
K

Karl Heinz Buchegger

MConly said:
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.
 
K

Ken Hagan

MConly said:
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.
 
N

Nick Maclaren

|> > 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.
 
N

Nick Maclaren

|>
|> 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.
 
C

Chris Theis

Victor Bazarov said:
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.


In the source. "Use the Source, Luke!"


Who?

They, you know, - beware of the dark side ;-)

Chris
 
C

Chris Theis

MConly said:
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
 
C

Chris Theis

Karl Heinz Buchegger said:
Nothing special. It is just a formula that gets executed.


There is none.
The language standards don't specify which formula to use.
But usual rand() implementations use a very simple formula.


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
 
M

MConly

Victor Bazarov said:

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...
 
V

Victor Bazarov

MConly said:
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?
 
R

Rolf Magnus

Chris said:
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.
 
C

Chris Theis

Rolf Magnus said:
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
 
C

Chris Theis

[SNIP]
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
 
P

Pete Becker

Chris said:
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.
 
C

Chris Theis

Pete Becker said:
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
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

Forum statistics

Threads
473,744
Messages
2,569,482
Members
44,901
Latest member
Noble71S45

Latest Threads

Top