Re: Random Seeding



Keith Thompson wrote On 05/15/06 16:13,:
porterboy76@xxxxxxxxx writes:

(ignores all the possible data after this)?.

this should have read:

(ignores all the possible "starting points" after this)?.


I would suggest that your possibly get 2^32 sequences with 2^19937-1
number of elements in each.

That's kind of what I thought. It seems fairly limited.
However, I just realised the Mersenne Twister c code
provided by it's inventors allows for longer seeds.

"Those who need initial seed with more than 32-bit
length may use init_by_array() for initialization which
admits an array of arbitrary length as seeds"

I guess you could use an array seeded with the time,
the process ID, and some compressed info from
/dev/random or /dev/audio. Still I imagine it would
still be very difficult to guarantee starting points
distibuted uniformly around the ring of numbers?


<OT>
If you have /dev/random, why would you bother with the time, the
process ID, or /dev/audio?

For that matter, if you have /dev/random, it's not entirely clear you
need to bother with a Mersenne Twister (but the question is beyond my
expertise).
</OT>

<OT>

A reproducible seed (and a subsequent reproducible
sequence) can be of value. Consider testing a module by
throwing pseudo-random data at it; when a failure turns
up you'd like to be able to regenerate the exact same data
as part of verifying your fix.

For the second matter, data rate is generally the issue.
It takes a significant amount of time for a physical source
to generate random data and pass it through assorted bias-
removing filters. If you try to read a zillion random numbers
from such a source, you may need to wait quite a while. It's
more common to use /dev/random or whatever to concoct a "truly
random" seed for a deterministic pseudo-random generator that
can generate subsequent numbers at computer speeds. For even
less predictability, the "truly random" source can also be
used to perturb the deterministic generator now and then.

Oddly enough, D.H. Lehmer used something very like this
perturbation technique in his original (and oft-criticized)
linear congruential generator. According to Knuth:

It is not fair to blame Lehmer for using a "bad"
random-number generator in 1948, since his actual
use of the generator was quite valid. The ENIAC
computer was a highly parallel machine, programmed
by means of a plugboard; Lehmer set it up so that
one of its accumulators was repeatedly multiplying
its own contents by 23, mod 10^8+1, yielding a new
value every few microseconds. Since this multiplier
23 is too small, we know that each value obtained
by this process was too strongly related to the
preceding value to be considered sufficiently random;
but the durations of time between actual uses of the
values in the special accumulator by the accompanying
program were comparatively long and subject to some
fluctuation. So the effective multiplier was 23^k
for large, varying values of k!

-- "The Art of Computer Programming, Volume II:
Seminumerical Algorithms," section 3.3.1

Similar techniques can be found nowadays in games, where
it is common to generate and discard a pseudo-random value
each time the program polls its input devices; the eventual
sequence used in the main part of the program thus depends in
part on the delays in keystroke, mouse, or joystick timings,
generally considered unpredictable if not downright twitchy.

</OT>

--
Eric.Sosman@xxxxxxx

.

Relevant Pages

  • Re: Math.random
    ... I would definitely set 2 much higher, since there are many PRNGs available ... My suggestion is to replace Lehmer, e.g., by Marsaglia's KISS32. ... UUID generator, to which this discussion is related - but apparently ...
    (comp.lang.javascript)
  • Re: Math.random
    ... methods other than Lehmer. ... An IEEE Double with a regular alternating pattern in its LSB, ... a smaller one can perhaps be an odd multiple of 2^-54. ...
    (comp.lang.javascript)
  • Re: Random number generation IP Sharp APL?
    ... The built in random number generator in every APL implementation that I have ... In general, in a linear congruential sequence, the next member of the sequence ... Usually this is done by choosing the modulus first, ... You achieve this by picking four seeds that are far ...
    (comp.lang.apl)
  • Re: 8 bit white noise algorithm
    ... The multiplier ... I would instead recommend a CRC generator, in hardware ... The Xilinx SRL16 makes it very easy to generate long LFSR ...
    (comp.dsp)
  • Re: random numbers in fortran
    ... I make sure that I have a generator capabable of producing any of the ... I understand also that with a short cycle, ... Generally in practice then, could I not compensate for a short cycle by ... The sample driver here prompts for N and 3 seeds. ...
    (comp.lang.fortran)