std::rand replacement, revision 1

Changes since N3796

• Seeding utility seed_init based on SG6’s preference.
• Variants for std::shuffle and std::experimental::sample.
• Naming candidate rand_int.
• Some outdated discussions are removed.

Motivation

We want to deprecate the std::rand friends, while “deprecation without a replacement” is a valid concern. This paper

1. Proposes replacement to the std::rand friends. Despite of the security issues, std::rand is considered both handy and useful as a global uniform random number generator.

2. Exposes the most widely-used combo in C++11 <random> without pushing the users to learn the whole design. Smoothing the learning curve can usually optimize the acceptance.

Design Decisions

std::rand is a self-contained interface, so its replacement should be independent as well. In addition, I expect the interface to correctly expose the functionalities of <random> and lead to more robust and secure programs. The proposed replacement is

• Distribution based. RNG must be used with a distribution; std::rand is a wrong design.

• Randomly seeded before being used. Improper seeding, rand(time(0)) for instance, results in vulnerabilities.

• Per-thread engine. Minimal interface should minimize astonishment, wrt. thread-safety and performance.

• Manually seedable. User can observe repeatability in a given thread, which is a typical demand for debugging.

• Type-safe. No integral promotion. For a given invocation, the inputs and the result have the same type.

Two variants for the shuffling and sampling algorithms without the explicit URNG parameter are also proposed.

Example

std::randint(0, 6);  // randomly seeded

// in another thread
std::seed_init();    // default_seed
std::shuffle(begin(v), end(v));

Wording

Change 26.5.2 rand.synopsis:

namespace std {

…

 // 26.5.7.2, function template generate_canonical
 template<class RealType, size_t bits, class URNG>
   RealType generate_canonical(URNG& g);

 // 26.5.8.2.1, class template uniform_int_distribution
 template<class IntType = int>
   class uniform_int_distribution;

…

} // namespace std

New section 26.5.7.3 rand.util.randint:

26.5.7.3 function template randint

All functions instantiated from the template described in this section share the same default_random_engine for a given execution of a thread; the random engine is non-deterministically seeded during the initialization if no call to any function described in section 26.5.7.4 in the same thread is sequenced before the random engine generating the first result. Such a random engine shall be maintained separately for each thread. [Note: The call expressions from different threads shall not be able to observe the same pseudo random number sequence in a deterministic way. –end note]

template<class IntType>
  IntType randint(IntType a, IntType b);

Requires: a ≤ b

Effects: Produce a random integer i, a ≤ i ≤ b, from a uniform_int_distribution<IntType> (26.5.8.2.1).

Returns: i.

New section 26.5.7.4 rand.util.seed_init:

26.5.7.4 seeding the per-thread engine

void seed_init();
void seed_init(default_random_engine::result_type value);

Requires: The random engine defined in section 26.5.7.3 in the same thread has not been seeded.

Effects: The first form seeds the engine with default_random_engine::default_seed. The second form seeds the engine with value.

Change 25.1 algorithms.general:

Header <algorithm> synopsis

…

 // 25.3.12, shuffle:

 template<class RandomAccessIterator, class UniformRandomNumberGenerator>
   void shuffle(RandomAccessIterator first,
                RandomAccessIterator last,
                UniformRandomNumberGenerator&& g);

Change 25.3.12 alg.random.shuffle:

 template<class RandomAccessIterator, class UniformRandomNumberGenerator>
   void shuffle(RandomAccessIterator first,
                RandomAccessIterator last,
                UniformRandomNumberGenerator&& g);

…

Remarks: To the extent that the implementation of this function makes use of random numbers, the object g shall serve as the implementation’s source of randomness in the second form, so does the random engine defined in section 26.5.7.3 in the same thread for the first form.

The following wording is relative to N4082 fund.ts.

Change 10.3 alg.random.sample:

 template<class PopulationIterator, class SampleIterator,
          class Distance, class UniformRandomNumberGenerator>
 SampleIterator sample(PopulationIterator first, PopulationIterator last,
                       SampleIterator out, Distance n,
                       UniformRandomNumberGenerator&& g);

…

Remarks:

• Stable if and only if PopulationIterator meets the requirements of a ForwardIterator type.
• To the extent that the implementation of this function makes use of random numbers, the object g shall serve as the implementation’s source of randomness in the second form, so does the random engine defined in section 26.5.7.3 in the same thread for the first form.

Sample Implementation

A sample implementation is available at https://github.com/lichray/randint.

Bikeshedding

First of all, overloading std::rand is not an option. User may deem std::rand() as a “safe” variant to the new interface.

Collected so far:

• randint, from Python[2]
• rand_int, by Nicolai and Andy Sawyer
• random_int, by STL
• pick_int, by me, inspired by WEB[1]
• randi, by Howard

Acknowledgments

Hans Boehm, who emphasized the importance of enforcing the per-thread random engine more than once.

Stephan T. Lavavej, who carefully reviewed this paper and provided many corrections.

Walter E. Brown, who drafted the paper[1] which contains basically the same thought.

And many others who joined the std::rand related discussions on c++std-lib and c++std-lib-ext mailing lists.

References

[1] Brown, Walter E. N3742 Three <random>-related Proposals, v2. http://www.open-std.org/JTC1/SC22/WG21/docs/papers/2013/n3742.pdf

[2] random – Generate pseudo-random numbers. “The Python Standard Library”. http://docs.python.org/2/library/random.html