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