Re: possible additions to 26.4 [random number generation]

Walter E Brown wrote:


[snip]


Thanks for the explanation.


I understand that something has to be expected to be useful before it can be
considered for inclusion into the standard. So, allow me to strengthen my
case by presenting a few other possible use cases, which I think are harder
to deal with using only means that are currently proposed.

Consider the following simulation of diffusion:

int main ( void ) {
  std::tr1::mt19937 urng;
  /*
    Setup: we are given two boxes A and B and n kinds of items.
    Box A contains a_1, a2_, ..., a_n items of each kind and
    box B contains b_1, b_2, ..., b_n items of each kind. At each
    step an item is picked at random and moved to the other box.
  */
  // We model the case n = 4;
  // The following vector is the vector a_1,...,a_n,b1,...,b_n
  // We start with all items in box A.
  std::vector< unsigned long > counts;
  counts.push_back( 200000 );
  counts.push_back( 150000 );
  counts.push_back( 4000000 );
  counts.push_back( 50000 );
  counts.push_back( 0 );
  counts.push_back( 0 );
  counts.push_back( 0 );
  counts.push_back( 0 );
  dynamic_discrete_distribution< unsigned long > two_row_grid
    ( counts.begin(), counts.end() );
  while ( true ) {
    for ( int i = 0; i < 1000; ++i ) {
      unsigned long index = two_row_grid( urng );
      unsigned long where_to_put = ( index + 4 ) % 8;
      two_row_grid.weight( index,
                           two_row_grid.weight( index ) -1 );
      two_row_grid.weight( where_to_put,
                           two_row_grid.weight( where_to_put ) + 1 );
    }
    for ( int i = 0; i < 4; ++i ) {
      std::cout << std::setw(8) << two_row_grid.weight( i ) << " ";
    }
    std::cout << std::endl;
    for ( int i = 4; i < 8; ++i ) {
      std::cout << std::setw(8) << two_row_grid.weight( i ) << " ";
    }
    std::cout << std::endl;
    std::cout << std::endl;
  }
}

If you did this using 4,000,000+200,000 + 150,000 + 50,000 = 4,400,000
objects in a vector, each keeping track in which box it currently is, the
program would use much more resources and spend most of the time computing
totals for reporting.

I think that a discrete distribution with modifiable weights would be a very
useful building block in simulations where items move around, die or
procreate, and the number of items is large enough to warant not modeling
them individually but using counts. Think of colored dots moving within a
graph where the probabilities of a dot being chosen for some action
(possibly involving moving to a neighbor) depend on how many dots of each
color are present at the given vertex. For more complicated graphs, it
becomes less and less obvious how to model that using standard containers
and random draws and shuffles. Here is a simple random walk simulation to
illustrate the point:

int main ( void ) {
  std::tr1::mt19937 urng;
  /*
    Simple random walk with destruction at either right end.

    We have n sites arranged in a line. At each step an object
    is chosen at random. It then moves to the left or right
    with equal probability. If it leaves the range, it drops
    out.
  */
  // Setup:
  unsigned int const num_sites = 10;
  std::vector< unsigned long > counts;
  for ( unsigned int i = 0; i < num_sites; ++i ) {
    counts.push_back( 1000 );
  }
  bernouli_distribution coin;
  dynamic_discrete_distribution< unsigned int > walk
    ( counts.begin(), counts.end() );

  // Simulation:
  while ( walk.total() > 0 ) {
    unsigned int site = walk( urng );
    walk.weight( site, walk.weight( site ) - 1 );
    bool left = coin( urng );
    if ( left ) {
      if ( site > 0 ) {
        --site;
        walk.weight( site, walk.weight( site ) + 1 );
      }
    } else {
      if ( site < walk.max() ) {
        ++site;
        walk.weight( site, walk.weight( site ) + 1 );
      }
    }
    for ( unsigned int i = 0; i < num_sites; ++i ) {
      std::cout << walk.weight( i ) << " ";
    }
    std::cout << std::endl;
  }
}

Note: when such a stochastic model arises from discretization of a
continuous phenomenon (like heat), the number of sites can easily grow
large, and the number of items moving around can be huge.

More complex use cases also exist where the weights are not just item
counts, e.g., a battle simulation where rifles and machine guns are
involved. Simulating each bullet, the firing frequencies will determine the
probability of the bullet coming from a machine gun or a riffle. Thus, the
weight change for a party depends on whether a riffle or a machine gun
carrier got hit.

Also, even in the simple drawing from a box example one can already see a
certain space overhead in the vector+shuffle solution. If the number of
objects is huge, that can be a drawback.

(BTW: the use cases so far suggest that changing the weight is more useful
than setting the weight. So, the interface is up for debate, I guess.)


I see. Which papers should I read to get up to speed in this Concepts issue?

As for the requirements, I had in mind that the SeedType would be either any
arithmetic type or seed_seq. This way, the constructors would be largely
parallel to the constructors of engines.

With regard to the ArithmeticType, I had in mind that integer and floating
point types should be allowed. Maybe, in view of the general requirements
clause 26.4.1.1 one could specify that by splitting the case into the
following signatures:
 
     template < typename IntType >
     IntType operator() ( IntType bound );

  requires: bound > 0;
  returns: a random integer evenly distributed in [0,bound)

     template < typename RealType >
     RealType operator() ( RealType bound );
  
  requires: bound > 0;
  returns: a random real evenly distributed in [0,bound)


Sounds good.

Thanks

Kai-Uwe Bux

---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html ]