Jens Maurer <Jens.Maurer@gmx.net>
2003-10-30
Document N1544=03-0127

$Id: issues.html,v 1.11 2003/10/30 21:28:42 jmaurer Exp $

Comments about Issues with Random Number Generators

Numeric issue numbers refer to N1535, Jxx issue numbers are new issues described in this paper.

Minor typo fixes

Issue 21: linear_congruential::linear_congruential(In&, In) -- Garbled Requires Clause

Subsumed by proposed resolution for issue 19 (see below).

Issue J1: More garbled pieces

There are some places where the TR draft contains garbled characters. This issue points out the places where editorial changes to rectify this need to be performed.

Issue J2: class vs. type

Proposed resolution:

Replace in section 5.1.1 [tr.rand.req], last paragraph

In the following subclauses, a template parameter named UniformRandomNumberGenerator shall denote a class type that satisfies all the requirements of a uniform random number generator.
[This aligns the wording with the subsequent sentences in the same paragraph.]

Issue J3: Fix section reference

Proposed resolution:

Replace in section 5.1.4 [tr.rand.eng], second paragraph

The class templates specified in this section satisfy all the requirements of a pseudo-random number engine (given in tables in section x.x 5.1.1 [tr.rand.req]), except where specified otherwise. Descriptions are provided here only for operations on the engines that are not described in one of these tables or for operations where there is additional semantic information.

Issue J4: Avoid confusion for "ell" and "one"

[See issue 19 for another issue that touches these words.]

Proposed resolution:

Replace in 5.4.1.2 [tr.rand.eng.mers]

Effects: With a linear congruential generator l(i) having parameters ml = 232, al = 69069, cl = 0, and l(0) = value, sets x(-n) ... x(-1) to l(1) ... l(n), respectively.
by
Effects: With a linear congruential generator lcg(i) having parameters mlcg = 232, alcg = 69069, clcg = 0, and lcg(0) = value, sets x(-n) ... x(-1) to lcg(1) ... lcg(n), respectively.
Replace in 5.4.1.3 [tr.rand.eng.sub]
Effects: With a linear congruential generator l(i) having parameters ml = 2147483563, al = 40014, cl = 0, and l(0) = value, sets x(-r) ... x(-1) to l(1) mod m ... l(r) mod m, respectively. If x(-1) == 0, sets carry(-1) = 1, else sets carry(-1) = 0.
by
Effects: With a linear congruential generator lcg(i) having parameters mlcg = 2147483563, alcg = 40014, clcg = 0, and lcg(0) = value, sets x(-r) ... x(-1) to lcg(1) mod m ... lcg(r) mod m, respectively. If x(-1) == 0, sets carry(-1) = 1, else sets carry(-1) = 0.
Replace in 5.4.1.4 [tr.rand.eng.sub1]
Effects: With a linear congruential generator l(i) having parameters m = 2147483563, a = 40014, c = 0, and l(0) = value, sets x(-r) ... x(-1) to (l(1)*2-w) mod 1 ... (l(r)*2-w) mod 1, respectively. If x(-1) == 0, sets carry(-1) = 2-w, else sets carry(-1) = 0.
by
Effects: With a linear congruential generator lcg(i) having parameters mlcg = 2147483563, alcg = 40014, clcg = 0, and lcg(0) = value, sets x(-r) ... x(-1) to (lcg(1)*2-w) mod 1 ... (lcg(r)*2-w) mod 1, respectively. If x(-1) == 0, sets carry(-1) = 2-w, else sets carry(-1) = 0.

Issue J5: xor_combine: fix typo

Proposed resolution:

Replace in 5.1.4.6 [tr.rand.eng.xor]

The template parameters UniformRandomNumberGenerator1 and UniformRandomNumberGenerator1 2 shall denote classes that satisfy all the requirements of a uniform random number generator, ...
[Replace "1" by "2" once.]

Requirements Definitions

Issue 1: Confusing Text in Description of v.min()

Proposed Resolution:

Change the first sentence of the description of v.min() in 5.1.1 [tr.rand.req], Table 5.2 (Uniform random number generator requirements) from:

Returns some l where l is less than or equal to all values potentially returned by operator().

to:

Returns a value that is less than or equal to all values potentially returned by operator().

Issue 2: Confusing and Incorrect Text in Description of v.max()

Proposed Resolution:

Change the first sentence of the description of v.max() in 5.1.1 [tr.rand.req], Table 5.2 (Uniform random number generator requirements) from:

If std::numeric_limits<T>::is_integer, returns l where l is less than or equal to all values potentially returned by operator(), otherwise, returns l where l is strictly less than all values potentially returned by operator().

to:

If std::numeric_limits<T>::is_integer, returns a value that is greater than or equal to all values potentially returned by operator(), otherwise, returns a value that is strictly greater than all values potentially returned by operator().

Issue 3: Table "Number Generator Requirements" Unnecessary

Proposed Resolution:

Copy the description of X::result_type from 5.1.1 [tr.rand.req], Table 5.1 (Number generator requirements) to 5.1.1 [tr.rand.req], Table 5.2 (Uniform random number generator requirements) and to 5.1.1 [tr.rand.req], Table 5.4 (Random distribution requirements) and remove 5.1.1 [tr.rand.req], Table 5.1 (Number generator requirements).

Issue J6: Require additional properties for Engine result_type

Currently, there are no restrictions on UniformRandomNumberGenerator::result_type, although variate_generator is supposed to possibly convert between integer and floating-point types.

Proposed resolution:

In 5.1.1 [tr.rand.req], replace the pre/post-condition for result_type (fold with resolution for issue 3):

std::numeric_limits<T>::is_specialized is true
by
T is an arithmetic type [basic.fundamental]

Issue J12: No complexity specification for copy construction and copy assignment

In 5.1.1 [tr.rand.req], add a new paragraph after table 5.3 (pseudo-random number generator):
Additional requirements: The complexity of both copy construction and assignment is O(size of state).

General

Issue 8: Should the Template Arguments Be Restricted to Built-in Types?

Because of the difficulty of good specification and in alignment with complex, I agree to restrict the types to built-in types, with the option to later expand it to user-defined types. The choice of required special functions for the user-defined type might restrict the choice of algorithms for the distribution.

Proposed resolution:

Replace in 5.1.1 [tr.rand.req], last paragraph

Furthermore, a template parameter named RealType shall denote a type that holds an approximation to a real number. This type shall meet the requirements for a numeric type (26.1 [lib.numeric.requirements]), the binary operators +, -, *, / shall be applicable to it, a conversion from double shall exist, and function signatures corresponding to those for type double in subclause 26.5 [lib.c.math] shall be available by argument-dependent lookup (3.4.2 [basic.lookup.koenig]). [Note: The built-in floating-point types float and double meet these requirements.]
by
Furthermore, the effect of instantiating a template that has a template type parameter named RealType is undefined unless that type is one of float, double, or long double.
Delete from 5.1.7 [tr.rand.dist]
A template parameter named IntType shall denote a type that represents an integer number. This type shall meet the requirements for a numeric type (26.1 [lib.numeric.requirements]), the binary operators +, -, *, /, % shall be applicable to it, and a conversion from int shall exist. [Footnote: The built-in types int and long meet these requirements.]

[...]

No function described in this section throws an exception, unless an operation on values of IntType or RealType throws an exception. [Note: Then, the effects are undefined, see [lib.numeric.requirements]. ]

Add after 5.1.1 [tr.rand.req], last paragraph
The effect of instantiating a template that has a template type parameter named IntType is undefined unless that type is one of short, int, long, or their unsigned variants.

The effect of instantiating a template that has a template type parameter named UIntType is undefined unless that type is one of unsigned short, unsigned int, or unsigned long.

[This last change also prevents questions that random number engines / distributions have to be usable with IntType = bool and other atrocities.]

variate_generator

Issue 4: Should a variate_generator Holding a Reference Be Assignable?

Proposed Resolution:

Change the first two sentences of the third paragraph of 5.1.3 [tr.rand.var] from:

Specializations of variate_generator satisfy the requirements of CopyConstructible. They also satisfy the requirements of Assignable unless the template parameter Engine is of the form U&.

to:

Specializations of variate_generator satisfy the requirements of CopyConstructible and Assignable.

Issue 10: Unclear Complexity Requirements for variate_generator

Proposed resolution:

Replace in 5.1.3 [tr.rand.var]

The complexity of all functions specified in this section is constant.
by
Except where specified otherwise, the complexity of all functions specified in this section is constant.
Add for variate_generator(engine_type e, distribution_type d)
Complexity: Sum of the complexities of the copy construtors of engine_type and distribution_type.
Add for result_type operator()()
Complexity: Amortized constant.
Add for result_type operator()(T value)
Complexity: Amortized constant.

Issue J7: Garbled precondition for min()

Proposed resolution:

In 5.1.3 [tr.rand.var], add the highlighted text for min():

Precondition: distribution().min() is well-formed

Engines

Issue J8: xor_combine: Require additional properties for base*_type::result_type

There are no restrictions on UniformRandomNumberGenerator1::result_type and UniformRandomNumberGenerator2::result_type that would ensure that << and ^ are available on them. That's well defined for unsigned integral types.

Proposed resolution:

Add in 5.1.4.6 [tr.rand.eng.xor] in the paragraph after the class definition

Both UniformRandomNumberGenerator1::result_type and UniformRandomNumberGenerator2::result_type shall denote (possibly different) unsigned integral types. The size of the state ...

Issue 12: xor_combine::result_type incorrectly specified

Proposed resolution:

In 5.1.4.6 [tr.rand.eng.xor] replace

typedef typename base_type::result_type result_type;
by
typedef /* see below */ result_type;
and add at the end of the paragraph below the class definition
The member result_type is defined to that type of UniformRandomNumberGenerator1::result_type and UniformRandomNumberGenerator2::result_type that provides the most storage [basic.fundamental].

Issue J14: Insufficient preconditions on xor_combine

xor_combine does not have any requirements for s1 and s2 template parameters.

Proposed resolution:

Add in 5.1.4.6 [tr.rand.eng.xor], paragraph after the class definition, before "The size of the state ..."

The following relation shall hold: 0 <= s1 and 0 <= s2.

Issue J9: Be precise about the size of the state of xor_combine

It is unclear what the "size of b1" and the "size of b2" mean, we only talk about the "size of the state".

Proposed resolution:

Add in 5.1.4.6 [tr.rand.eng.xor] in the paragraph after the class definition:

The size of the state is the size of the state of b1 plus the size of the state of b2.

Issue 13: subtract_with_carry's IntType overspecified

Proposed resolution:

In 5.1.4.3 [tr.rand.eng.sub], replace

The template parameter IntType shall denote a signed integral type large enough to store values up to m-1.
by
The template parameter IntType shall denote an integral type large enough to store values up to m.

Issue 14: subtract_with_carry_01::seed(unsigned) Missing Constraint

Subsumed by proposed resolution to issue 19.

Issue 15: subtract_with_carry_01::seed(unsigned) Produces Bad Values

Proposed resolution:

Replace in 5.1.4.4 [tr.rand.eng.sub1] [signature was changed in issue 16, "l" was changed to "lcg" in issue J4, this contains the consolidated edits as far as overlaps are concerned] 

    void seed(unsigned int value = 19780503)
Effects: With a linear congruential generator l(i) having parameters m = 2147483563, a = 40014, c = 0, and l(0) = value, sets x(-r) ... x(-1) to (l(1)*2-w) mod 1 ... (l(r)*2-w) mod 1, respectively. If x(-1) == 0, sets carry(-1) = 2-w, else sets carry(-1) = 0.
Complexity: O(r)
by 
 void seed(unsigned long value = 19780503ul)
Effects: With n=(w+31)/32 (rounded downward) and given an iterator range [first, last) that refers to the sequence of values lcg(1) ... lcg(n*r) obtained from a linear congruential generator lcg(i) having parameters mlcg = 2147483563, alcg = 40014, clcg = 0, and lcg(0) = value, invoke seed(first,last) .
Complexity: O(r*n)

Issue 16: subtract_with_carry_01::seed(unsigned) Argument Type Too Small

All of mersenne_twister, subtract_with_carry, and subtract_with_carry_01 need to be changed (the value supplied for the linear congruential engine-helper for initialization has nothing to do with the final result type of the engine), here are the consolidated changes:

Proposed resolution:

In 5.1.4.2 [tr.rand.eng.mers], change the signature of a constructor and a seed function from 

    explicit mersenne_twister(result_type value);
    void seed(result_type value);
to 
    explicit mersenne_twister(unsigned long value);
    void seed(unsigned long value);
In 5.1.4.3 [tr.rand.eng.sub], change the signature of a constructor and a seed function from 
    explicit subtract_with_carry(IntType value);
    void seed(IntType value = 19780503);
to 
    explicit subtract_with_carry(unsigned long value);
    void seed(unsigned long value = 19780503ul);
In 5.1.4.4 [tr.rand.eng.sub1], change the signature of a constructor and a seed function from 
    subtract_with_carry_01(unsigned int value);
    void seed(unsigned int value = 19780503);
to: 
    subtract_with_carry_01(unsigned long value);
    void seed(unsigned long value = 19780503ul);

Issue 17: subtract_with_carry::seed(In&, In) Required Sequence Length Too Long

Proposed Resolution:

Change

With n=w/32+1 (rounded downward) and given the values z0 ... zn*r-1

to

With n=(w+31)/32 (rounded downward) and given the values z0 ... zn*r-1

in the description of subtract_with_carry::seed(In& first, In last) in 5.1.4.3 [tr.rand.eng.sub] and in the description of subtract_with_carry_01::seed(In& first, In last) in 5.1.4.4 [tr.rand.eng.sub1].

Issue 18: linear_congruential -- Giving Meaning to a Modulus of 0

Proposed resolution:

Replace in 5.1.4.1 [tr.rand.eng.lcong], in the paragraph after the class definition

If the template parameter m is 0, the behaviour is implementation-defined.
by
If the template parameter m is 0, the modulus m used throughout this section is std::numeric_limits<IntType>::max() plus 1. [Note: The result is not representable as a value of type IntType.]

Issue 19: linear_congruential::seed(IntType) -- Modify Seed Value When c == 0?

Proposed resolution:

Replace in 5.1.4.1 [tr.rand.eng.lcong] 

    explicit linear_congruential(IntType x0 = 1)
Requires: c > 0 || (x0 % m) > 0
Effects: Constructs a linear_congruential engine with state x(0) := x0 mod m. 
    void seed(IntType x0 = 1)
Requires: c > 0 || (x0 % m) > 0
Effects: Sets the state x(i) of the engine to x0 mod m. 
    template linear_congruential(In& first, In last)
Requires: c > 0 || *first > 0
Effects: Sets the state x(i) of the engine to *first mod m.
Complexity: Exactly one dereference of *first.
by 
    explicit linear_congruential(IntType x0 = 1)
Effects: Constructs a linear_congruential engine and invokes seed(x0). 
    void seed(IntType x0 = 1)
Effects: If c mod m = 0 and x0 mod m = 0, sets the state x(i) of the engine to 1 mod m, else sets the state x(i) of the engine to x0 mod m. 
    template linear_congruential(In& first, In last)
Effects: If c mod m = 0 and *first mod m = 0, sets the state x(i) of the engine to 1 mod m, else sets the state x(i) of the engine to *first mod m.
Complexity: Exactly one dereference of *first.
Replace in 5.1.4.2 [tr.rand.eng.mers] [see issue J4 for the change to "lcg"] 
    void seed()
Effects: Invokes seed(4357). 
    void seed(result_type value)
Requires: value > 0
Effects: With a linear congruential generator l(i) having parameters ml = 232, al = 69069, cl = 0, and l(0) = value, sets x(-n) ... x(-1) to l(1) ... l(n), respectively.
Complexity: O(n)
by 
    void seed()
Effects: Invokes seed(0). 
    void seed(result_type value)
Effects: If value == 0, sets value to 4357. In any case, with a linear congruential generator lcg(i) having parameters mlcg = 232, alcg = 69069, clcg = 0, and lcg(0) = value, sets x(-n) ... x(-1) to lcg(1) ... lcg(n), respectively.
Complexity: O(n)
Replace in 5.4.1.3 [tr.rand.eng.sub] [see issue J4 for the change to "lcg"] [see issue 16 for the change to "unsigned long"] 
    void seed(unsigned int value = 19780503)
Requires: value > 0
Effects: With a linear congruential generator l(i) having parameters ml = 2147483563, al = 40014, cl = 0, and l(0) = value, sets x(-r) ... x(-1) to l(1) mod m ... l(r) mod m, respectively. If x(-1) == 0, sets carry(-1) = 1, else sets carry(-1) = 0.
Complexity: O(r)
by 
 void seed(unsigned long value = 19780503ul)
Effects: If value == 0, sets value to 19780503. In any case, with a linear congruential generator lcg(i) having parameters mlcg = 2147483563, alcg = 40014, clcg = 0, and lcg(0) = value, sets x(-r) ... x(-1) to lcg(1) mod m ... lcg(r) mod m, respectively. If x(-1) == 0, sets carry(-1) = 1, else sets carry(-1) = 0.
Complexity: O(r)
Replace in 5.4.1.4 [tr.rand.eng.sub1] [see issue J4 for the change to "lcg"] [see issue 16 for the change to "unsigned long"] 
 void seed(unsigned int value = 19780503)
Effects: With a linear congruential generator l(i) having parameters m = 2147483563, a = 40014, c = 0, and l(0) = value, sets x(-r) ... x(-1) to (l(1)*2-w) mod 1 ... (l(r)*2-w) mod 1, respectively. If x(-1) == 0, sets carry(-1) = 2-w, else sets carry(-1) = 0.
Complexity: O(r)
by 
 void seed(unsigned long value = 19780503ul)
Effects: If value == 0, sets value to 19780503. In any case, with a linear congruential generator lcg(i) having parameters mlcg = 2147483563, alcg = 40014, clcg = 0, and lcg(0) = value, sets x(-r) ... x(-1) to lcg(1) mod m ... lcg(r) mod m, respectively. If x(-1) == 0, sets
Complexity: O(r)

Issue 20: linear_congruential -- Should the Template Arguments Be Unsigned?

Proposed Resolution:

In clause 5.1.4.1 [tr.rand.eng.lcong] replace every occurrence of IntType with UIntType and change the first sentence after the definition of the template from:

The template parameter IntType shall denote an integral type large enough to store values up to (m-1).

to:

The template parameter UIntType shall denote an unsigned integral type large enough to store values up to (m-1).

J13: Insufficient preconditions on discard_block

discard_block does not have sufficient requirements on the r and p template parameters.

Proposed resolution:

Replace in 5.1.4.5 [tr.rand.eng.disc]

r <= q
by
The following relation shall hold: 0 <= r <= p.

Distributions

Issue 22: bernoulli_distribution Isn't Really a Template

Proposed resolution:

In 5.1.7.2 [tr.rand.dist.bern], change the section heading to "Class bernoulli_distribution", remove template <class RealType = double> from the declaration of bernoulli_distribtion, change the declaration of the constructor from:

    explicit bernoulli_distribution(const RealType& p = RealType(0.5));

to:

    explicit bernoulli_distribution(double p = 0.5);

and change the header for the subclause describing the constructor from:

    bernoulli_distribution(const RealType& p = RealType(0.5))

to:

    bernoulli_distribution(double p = 0.5)

Issue J11: uniform_real should return open interval?

uniform_real was specified with a closed interval [min, max] range, but it should have a half-open interval [min, max) range to avoid lots of special cases in more complex distributions. (The boost implementation and documentation does this since ever.)

Proposed resolution:

In 5.1.7.6 [tr.rand.dist.runif], replace

min <= x <= max
by
min <= x < max
[The half-open interval should be used to avoid various special cases in derived distributions, this is (and always was) correct in the boost documentation.]

Issue 5: Normal Distribution Incorrectly Specified

Proposed Resolution:

Change the first paragraph of 5.1.7.8 [tr.rand.dist.norm] from:

A normal_distribution random distribution produces random numbers x distributed with probability density function (1/sqrt(2*pi*sigma))e-(x-mean)2/(2*sigma2), where mean and sigma are the parameters of the distribution.

to:

A normal_distribution random distribution produces random numbers x distributed with probability density function (1/(sqrt(2*pi)*sigma))e-(x-mean)2/(2*sigma2), where mean and sigma are the parameters of the distribution.