Re: [boost] [random] new threefry random engine

Subject: Re: [boost] [random] new threefry random engine
From: Steven Watanabe (watanabesj_at_[hidden])
Date: 2014-04-22 12:25:03

AMDG

On 04/22/2014 08:51 AM, John Salmon wrote:
> <snip>
> With sequential
> generators, a sufficiently motivated and careful user can use the
> discard() function to initialize multiple generators in parallel.
> For most generators, discard(N) is O(N), defeating its use for this
> purpose, but for a few (including Threefry), discard(N) is O(1) making
> this a practical, but hardly elegant or natural approach to
> parallelism.
> 

FWIW, discard isn't inherently O(N) for most generators.
Faster algorithms exist, but are not widely implemented.

> <snip>
> A better approach is to devise a trivial, application-specific mapping
> of time (iteration number) plus some stable aspect your logical
> elements (e.g., atom id) into unique 128-bit inputs.  You can now
> obtain the random values you need, wherever and whenever you need them
> simply by generating a unique 128-bit input and calling the
> RandomFunction.  There is no space overhead.  If your parallel
> algorithm dictates that you need the same random value, e.g., to
> perform an "update" in two different threads or nodes, you just call
> the RandomFunction with the appropriate arguments wherever you need it
> and you get the results you need, where you need them.  In parallel
> applications this is much more natural than trying to divvy up a
> single stream into multiple substreams by 'discarding' or 'jumping' an
> inherently sequential state.  It is cheaper and easier than
> associating a stateful generator with each of your logical objects and
> worrying about the storage and bandwidth to keep them in-sync across
> the threads/nodes of a parallel computation.
> 

The problem I have with this, basically comes down
to encapsulation.

- distributions consume an unspecified number
  of random values.  I have no idea how to make
  the distributions work with a RandomFunction,
  besides requiring them to use a 1-to-1 mapping.
  Even with 64-bit values, this limits the precision
  of the random variates.
- Taking this one step farther, how can I write
  a generic function which uses an arbitrary
  RandomFunction to generate a sequence of k
  random variates? There's no way to know a
  priori how many unique inputs I would need.
  Even if k is constant, it still depends on
  the block size of the RandomFunction.
- A RandomFunction is strictly a PRNG interface.
  It doesn't work very well for expressing other
  sources of random values, such as /dev/urandom,
  specialized devices, and www.random.org.

I think that we can get most of the benefits of a
RandomFunction without going away from the Engine
concept, if we add a couple of extra guarantees
for engines intended for parallel use:
- seeding a new engine is fast
- distinct seeds (within some limits)
  produce uncorrelated sequences.
Both of these properties are trivial for Engines based
on RandomFunctions.

In Christ,
Steven Watanabe