4014. LWG 3809 changes behavior of some existing std::subtract_with_carry_engine code

Section: 29.5.4.4 [rand.eng.sub] Status: Ready Submitter: Matt Stephanson Opened: 2023-11-15 Last modified: 2024-10-09

Priority: 2

View all other issues in [rand.eng.sub].

View all issues with Ready status.

Discussion:

Issue 3809 pointed out that subtract_with_carry_engine<T> can be seeded with values from a linear_congruential_engine<T, 40014u, 0u, 2147483563u> object, which results in narrowing when T is less than 32 bits. Part of the resolution was to modify the LCG seed sequence as follows:

explicit subtract_with_carry_engine(result_type value);

-7- Effects: Sets the values of $X_{-r},\dots ,X_{-1}$, in that order, as specified below. If $X_{-1}$ is then $0$, sets $c$ to $1$; otherwise sets $c$ to $0$.

     To set the values $X_k$, first construct e, a linear_congruential_engine object, as if by the following definition:

linear_congruential_engine<result_typeuint_least32_t,
                           40014u,0u,2147483563u> e(value == 0u ? default_seed : value);

     Then, to set each $X_k$, obtain new values $z_0,\dots ,z_{n-1}$ from $n=\lceil w/32\rceil$ successive invocations of e. Set $X_k$ to $({\sum }_{j=0}^{n-1}{z}_j\bullet 2^{32j})modm$.

Inside linear_congruential_engine, the seed is reduced modulo 2147483563, so uint_least32_t is fine from that point on. This resolution, however, forces value, the user-provided seed, to be truncated from result_type to uint_least32_t before the reduction, which generally will change the result. It also breaks the existing behavior that two seeds are equivalent if they're in the same congruence class modulo the divisor.

[2024-01-11; Reflector poll]

Set priority to 2 after reflector poll.

[2024-01-11; Jonathan comments]

More precisely, the resolution forces value to be converted to uint_least32_t, which doesn't necessarily truncate, and if it does truncate, it doesn't necessarily change the value. But it will truncate whenever value_type is wider than uint_least32_t, e.g. for 32-bit uint_least32_t you get a different result for std::ranlux48_base(UINT_MAX + 1LL)(). The new proposed resolution below restores the old behaviour for that type.

[2024-10-09; LWG telecon: Move to Ready]

Proposed resolution:

This wording is relative to N4964 after the wording changes applied by LWG 3809, which had been accepted into the working paper during the Kona 2023-11 meeting.

1. Modify 29.5.4.4 [rand.eng.sub] as indicated:

   explicit subtract_with_carry_engine(result_type value);

   -7- Effects: Sets the values of $X_{-r},\dots ,X_{-1}$, in that order, as specified below. If $X_{-1}$ is then $0$, sets $c$ to $1$; otherwise sets $c$ to $0$.

        To set the values $X_k$, first construct e, a linear_congruential_engine object, as if by the following definition:

   linear_congruential_engine<uint_least32_t,
                              40014u,0u,2147483563u> e(value == 0u ? default_seed :
                              static_cast<uint_least32_t>(value % 2147483563u));
   

        Then, to set each $X_k$, obtain new values $z_0,\dots ,z_{n-1}$ from $n=\lceil w/32\rceil$ successive invocations of e. Set $X_k$ to $({\sum }_{j=0}^{n-1}{z}_j\bullet 2^{32j})modm$.