512. Seeding subtract_with_carry_01 from a single unsigned long

Section: 29.5.4 [rand.eng], 99 [tr.rand.eng.sub1] Status: NAD Editorial Submitter: Walter Brown Opened: 2005-07-03 Last modified: 2016-01-28

Priority: Not Prioritized

View all other issues in [rand.eng].

View all issues with NAD Editorial status.

Discussion:

Paragraph 8 specifies the algorithm by which a subtract_with_carry_01 engine is to be seeded given a single unsigned long. This algorithm is seriously flawed in the case where the engine parameter w (also known as word_size) exceeds 31 [bits]. The key part of the paragraph reads:

sets x(-r) ... x(-1) to (lcg(1)*2**(-w)) mod 1

and so forth.

Since the specified linear congruential engine, lcg, delivers numbers with a maximum of 2147483563 (just a shade under 31 bits), then when w is, for example, 48, each of the x(i) will be less than 2**-17. The consequence is that roughly the first 400 numbers delivered will be conspicuously close to either zero or one.

Unfortunately, this is not an innocuous flaw: One of the predefined engines in [tr.rand.predef], namely ranlux64_base_01, has w = 48 and would exhibit this poor behavior, while the original N1378 proposal states that these pre-defined engines are intended to be of "known good properties."

Proposed resolution:

In 5.1.4.4 [tr.rand.eng.sub1], replace the "effects" clause for void seed(unsigned long value = 19780503) by

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 carry(-1) and x(-r) … x(-1) as if executing

linear_congruential<unsigned long, 40014, 0, 2147483563> lcg(value);
seed(lcg);

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.

[ Jens provided revised wording post Mont Tremblant. ]

[ Berlin: N1932 adopts the originally-proposed resolution of the issue. Jens's supplied wording is a clearer description of what is intended. Moved to Ready. ]

Rationale:

Jens: I'm using an explicit type here, because fixing the prose would probably not qualify for the (with issue 504 even stricter) requirements we have for seed(Gen&).

[ Portland: Subsumed by N2111. ]