Title
Seeding subtract_with_carry_01 from a single unsigned long
Status
nad editorial
Section
[rand.eng][tr.rand.eng.sub1]
Submitter
Walter Brown

Created on 2005-07-03.00:00:00 last changed 163 months ago

Messages

Date: 2010-10-21.18:28:33

[ Portland: Subsumed by N2111. ]

Date: 2010-10-21.18:28:33

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&).

Date: 2010-10-21.18:28:33

[ 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. ]

Date: 2010-10-21.18:28:33

[ Jens provided revised wording post Mont Tremblant. ]

Date: 2010-10-21.18:28:33

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.

Date: 2005-07-03.00:00:00

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."

History
Date User Action Args
2010-10-21 18:28:33adminsetmessages: + msg2901
2010-10-21 18:28:33adminsetmessages: + msg2900
2010-10-21 18:28:33adminsetmessages: + msg2899
2010-10-21 18:28:33adminsetmessages: + msg2898
2010-10-21 18:28:33adminsetmessages: + msg2897
2005-07-03 00:00:00admincreate