Proposed extension to random library

[nobody]

I suggest adding the following utility function to
the random library (with perhaps a name change):

// PURPOSE: Sample from a set of N values given the
// sequence p[1], p[1] + p[2], p[1] + p[2] + p[3], ...
// of cumulative probabilities.
//
// REQUIRE:
// - Type Incrementer supports the pre-increment
//   operation and equality comparison.  Typically,
//   Incrementer will be an integral type or a
//   forward iterator.
// - Pre-incrementing i some finite number of times
//   -- say, N -- makes it equal to iend.
// - cumprob_it "points" at a nondecreasing sequence
//   of at least N nonnegative numbers, with the N-th
//   value in the sequence being equal to 1.0.
//
// RETURNS:
// A random value in the interval [i, iend), with
// cumprob_it defining the sequence of cumulative
// probabilities.

template <typename InputIterator,
          typename Incrementer,
          class UniformRandomNumberGenerator>
Incrementer
rand(Incrementer i, Incrementer iend,
     InputIterator cumprob_it,
     UniformRandomNumberGenerator & rng)
{
  typedef
    std::iterator_traits<InputIterator>::value_type
    number_t;
  uniform_01<UniformRandomNumberGenerator, number_t>
    urng(rng);
  number_t p = urng();
  for ( ; p >= *cumprob_it; ++cumprob_t) {
    ++i;
    assert(!(i == iend));
  }
  return i;
}

-- Kevin S. Van Horn (Kevin_VanHorn@ndsu.nodak.edu)

[nobody]

Logged In: NO 

These types of sampled probability distributions are very 
useful. In my field of work they are now more important 
then the classical functional distributions like Gaussians.
The advantage is of course that to arbitary precission they 
can represent any distribution.
I would suggest a common name such 
as 'parametric_distribution' or 'sampled_distribution'
The sort of distribution can be represented in many ways 
the two major (and interchangable) are as sorted 
probabilties or as cumulative probabilites.

One problem with this concept (a single draw from a 
distribution) is that it is O(n) where n is parameter table 
size. However multiple draws can be simplified, by sorting 
and then searching in the parameter table. At present boot 
random has no concept for multiple draws. Because of the 
complexity issue the paramertised_distribution doesn't seem 
that useful without also a multiple draw concept.

In summary either add both or none!

[Steven Watanabe]

The new standard will contain a discrete_distribution, which returns an integer given a sequence of weights.

[Steven Watanabe]

Fixed in [63180].