2327. Non-power-of-two URNGs should be forbidden

Section: 29.5.3.3 [rand.req.urng] Status: NAD Submitter: Stephan T. Lavavej Opened: 2013-09-21 Last modified: 2016-01-28

Priority: Not Prioritized

View all other issues in [rand.req.urng].

View all issues with NAD status.

Discussion:

29.5.3.3 [rand.req.urng] allows URNGs with non-power-of-two (NPOT) ranges, like [0, 1729]. This is unnecessarily permissive (I cannot imagine a realistic source of randomness that would generate such a range) and has real costs for implementers, as uniform_int_distribution must be prepared to accept such URNGs. The most efficient way to accumulate randomness is to concatenate random bits, so NPOT randomness is not just useless, it is actively harmful (to avoid bias, if a URNG generates a random number outside of a power-of-two range, the number must be discarded).

Forbidding NPOT URNGs wouldn't affect users, and would simplify Standard Library implementations. It would be nice to require min() to be 0, but this is not necessary; it is simple for implementations to say g() - G::min() and this will optimize away if min() is 0. (It is vaguely plausible for a URNG to have a nonzero minimum; I can imagine something that simply masks off low-order bits without shifting the rest downwards.) What is important is for the entire range to have a power-of-two width; [1729, 1984] is acceptable as its size is 256.

[2013-10-12: Howard presents a counterexample]

Consider:

#include <random>
#include <string>
#include <iostream>

template <class Int>
bool is_power_2m1(Int i)
{
  return (i & (i + 1)) == 0;
}

template <class URNG>
void test(const std::string& urng)
{
  using namespace std;
  typename URNG::result_type rng = URNG::max() - URNG::min();
  if (!is_power_2m1(rng))
  {
    cout << hex;
    cout << urng << " : min = " << URNG::min() << ", max = " << URNG::max()
         << ", max-min = " << rng << '\n';
  }
};

int main()
{
    using namespace std;
    test<minstd_rand0>("minstd_rand0");
    test<minstd_rand>("minstd_rand");
    test<mt19937>("mt19937");
    test<mt19937_64>("mt19937_64");
    test<ranlux24_base>("ranlux24_base");
    test<ranlux48_base>("ranlux48_base");
    test<ranlux24>("ranlux24");
    test<ranlux48>("ranlux48");
    test<knuth_b>("knuth_b");
}

Which for me outputs:

minstd_rand0 : min = 1, max = 7ffffffe, max-min = 7ffffffd
minstd_rand : min = 1, max = 7ffffffe, max-min = 7ffffffd
knuth_b : min = 1, max = 7ffffffe, max-min = 7ffffffd

We do not want to outlaw these three URNG's, and the proposed wording would do that.

[Issaquah 2014-02-10: Moved to NAD]

STL withdraws the issue, non-power-of-2 URNGs are used in the field, it is too late to consider removing them.

Proposed resolution:

This wording is relative to N3691.

1. Add a new paragraph at the end of 29.5.3.3 [rand.req.urng] as indicated:

   -3- The following relation shall hold: G::min() < G::max().

   -?- G::max() - G::min() shall be 2ⁿ - 1 for some n > 0.