Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C Programming > Random Seeding

Reply
Thread Tools

Random Seeding

 
 
porterboy76@yahoo.com
Guest
Posts: n/a
 
      05-16-2006
> 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.


Agreed. I intend testing my algorithms and simulations
using a fixed unchanging seed, so I can see how changes
affect the system. However, once I am satisfied that all is
well, I would like to switch in a more unpredictable seed, to
expand my range of possible tested sequences.

/* for your info I am doing simulation of card playing
strategies. At first I will deal the same sequence of hands
over and over to a lot of different strategies. Once I have
identified what is a good strategy and why (by examining
reproducible data from a fixed seed) I will then move onto
unreproducible data to see how the strategies fare in the
"real world". */

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


I hadn't thought of user input as a seed, although for a fixed
set of actions (such as typing a few inputs) the variance of the
seed could be limited.

Now that I think of it, if I am not trying to be cryptographically
secure, then maybe operations on <time.h> functions will
suffice for my needs, since I will always be guaranteed to
advance through the Mersenne Twister sequence
as the time always increases... I think that solves my problem.

 
Reply With Quote
 
 
 
 
websnarf@gmail.com
Guest
Posts: n/a
 
      05-16-2006
http://www.velocityreviews.com/forums/(E-Mail Removed) wrote:
> If you only use a 32 bit seed for a random number generator,
> does that mean you can only ever produce a maximum of
> 2^32 (approx 4 billion) different sequences?
>
> What about the Mersenne Twister, with it's massive period
> of 2^19937-1. Will you only ever have access to a tiny
> portion of this ring of numbers, if you only use a 32-bit seed?
> Will this set of sequences be confined to the beginning of the
> period, ie, your sequence will have to start at some place
> between index number 1 and 4 billion of the period (ignores
> all the possible data after this)?.


The Mersenne Twister starts with a massively large cycled sequence of
2^19937-1 numbers (it repeats after requesting that many random numbers
in order.) The way it is seeded, each one of the possible 2^32 seeds
is mapped to its own starting point within this cycle. So there are
2^32 sequences, each of which is 2^19937-1 in length, and in fact are
just shifted version of each other. BTW, (2^19937-1) / 2^32 is still
really huge, but I don't know that any pair of seeds doesn't overlap a
lot sooner -- maybe there is more information in the original paper
describing it.

So the seed does not embody the entire internal entropy which generates
the output.

--
Paul Hsieh
http://www.pobox.com/~qed/
http://bstring.sf.net/

 
Reply With Quote
 
 
 
 
websnarf@gmail.com
Guest
Posts: n/a
 
      05-16-2006
Keith Thompson wrote:
> (E-Mail Removed) 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?


http://www.pinkas.net/PAPERS/gpr06.pdf

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


Because Entropy is typically slow/expensive to obtain, while PRNGs are
generally very fast. Most typically you can only get new entropy a
some slow rate like no more than 10 samples per second (if, say, you
are tracking mouse movement, or key presses) while a PRNG can be
computed with speeds proportional to the speed of the CPU. So its like
asking what you need a disk for if you have lots of memory.

Its actually kind of curious -- CPU manufacturers have actually been
looking at building circuit-level entropy generators, which of course,
would completely nullify the problem, but software solutions have been
getting better over time to the point, where direct hardware support
may be overkill.

--
Paul Hsieh
http://www.pobox.com/~qed/
http://bstring.sf.net/

 
Reply With Quote
 
Eric Sosman
Guest
Posts: n/a
 
      05-16-2006


(E-Mail Removed) wrote On 05/16/06 03:38,:
>> 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.

>
>
> Agreed. I intend testing my algorithms and simulations
> using a fixed unchanging seed, so I can see how changes
> affect the system. However, once I am satisfied that all is
> well, I would like to switch in a more unpredictable seed, to
> expand my range of possible tested sequences.
>
> /* for your info I am doing simulation of card playing
> strategies. At first I will deal the same sequence of hands
> over and over to a lot of different strategies. Once I have
> identified what is a good strategy and why (by examining
> reproducible data from a fixed seed) I will then move onto
> unreproducible data to see how the strategies fare in the
> "real world". */
>
>
>> 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.

>
>
> I hadn't thought of user input as a seed, although for a fixed
> set of actions (such as typing a few inputs) the variance of the
> seed could be limited.


I think you've misunderstood: The idea isn't to use these
little timing variations as seeds, but as perturbations to a
deterministic sequence that's seeded elsewhere. By throwing
away an unpredictable quantity of numbers every so often,
you change the deterministic sequence

X1, X2, X3, X4, ...

into the much less predictable

X1, X2, X9, X10, X11, X42, ...

--
(E-Mail Removed)

 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Seeding random number generator hepmehepme@comcast.net VHDL 3 05-07-2009 09:54 PM
seeding random numbers (-Peter-) Java 18 02-22-2008 01:37 AM
Seeding Random Numbers in Multiple Threads? HumanJHawkins C++ 2 11-30-2006 09:20 PM
Random Number Not Seeding Jack C++ 4 08-18-2005 12:34 AM
Random number generator and seeding Joe C++ 2 11-19-2004 07:38 PM



Advertisments