On 12/06/2015 13:21, Konrad Hinsen wrote:
On 12/06/15 09:15, Michael Titke wrote:
In my understanding the pseudo random number generator is deterministic.
That means for the same input seed /random/ will always return the same
value. This is why one usually has to set a new state for each call of
random.
No, quite on the contrary.
Before going on, please note that I never looked at the specific
random generator used by Racket. I assume it's one of the popular
random number generator algorithms. For what follows, it doesn't even
matter which one.
All pseudorandom generators produce a sequence of numbers. The
intention is that the sequence should have as little detectable
correlation as possible. The algorithms differ in how they define this
goal exactly, and how well they reach it.
Right, it should not be the same number on every call to random but the
same sequence of numbers for each and every seed. Whenever I use the
same seed I will get the same sequence of random numbers for the
sequence of calls to random.
The principle behind all these generators is a chaotic dynamic process
that transforms the current state of the generator (some finite number
of bits) into a new state, which is used for the next call. The
returned value is some function of the state. Setting a new seed
changes to state to some function of the seed value.
Seeding is provided for two use cases: 1) Reproducibility, mainly for
software testing. If you set the seed to some constant at the start of
your program, it will behave exactly the same way whenever it is run.
2) "Real" randomization, by setting the seed from some unpredictable
source, such as the system time. In both cases, the idea is to set the
seed once at the beginning of a program run.
With your idea in #2 I would reliably produce known sequences depending
on only 256 original states. Using as much entropy from the pool as my
current implementation is uncommon but it definitely does not create the
bias. I "abuse" the pseudo random number generator only to map these 256
possibilities onto the list (mathematical vector) of 65 characters.
Racket's implementation somehow introduces that bias. But IMHO a
function random (n state/generator) should guarantee a common saturation
of the destination space.
From the Guile reference:
Note that the initial value of `*random-state*' is the same every
time Guile starts up. Therefore, if you don't pass a STATE parameter
to the above procedures, and you don't set `*random-state*' to
`(seed->random-state your-seed)', where `your-seed' is something that
_isn't_ the same every time, you'll get the same sequence of "random"
numbers on every run.
The current system time is highly predictable.
The statistical properties of the pseudo-random sequence hold only for
an unperturbed sequence, i.e. without changing the seed. If you set
the seed every time you ask for a random number, your random sequence
becomes simply some complicated function of your input seed, whose
statistical properties are hard to predict and most probably not what
you want.
That does not explain the bias, I guess. I repeat: But IMHO a function
(random n state/generator) should guarantee a common saturation of the
destination space when the current state is filled with real randomness.
Do you really think that seeding with numbers from an entropy pool would
create such a strong bias. I don't think so. On the contrary it does
away with the predictable sequences of the 256 original states won by
using the pure result of reading the randomness device.
If you want to look at the system and do a black box test then the
result would be:
true randomness / noise -> Racket's randomness implementation with a new
state each time -> strongly biased noise
true randomness / noise -> Racket's randomness implementation with one
initial state -> one of 256 known sequences
true randomness / noise -> GNU-Guile's randomness implementation -> noise
BTW the basic formula of cryptography is: Message |+| Randomness ->
Randomness
Now replace Randomness with Racket and try to ...
--
You received this message because you are subscribed to the Google Groups "Racket
Users" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
For more options, visit https://groups.google.com/d/optout.
