Change requirements on linear_congruential_engine

[zoecarver]

Summary

This patch changes how linear_congruential_engine picks its randomization algorithm. It adds two restrictions, _OverflowOK and _SchrageOK. _OverflowOK means that m is a power of two so using the classic (a * x + c) % m will create a meaningless overflow. The second checks that Schrage's algorithm will produce results that are in bounds of min and max. This patch fixes 27839.

[zoecarver]

I think it may be good to remove Schrage's algorithm altogether and file an LWG issue for the remaining edge cases. It is very slow and feels out of place in LCG. Additionally, Schrage's algorithm introduces lot's of added complexity and space for bugs.

libcxx/include/random

1676

This static_assert is redundant. Maybe I should remove it.

[zoecarver]

Ping :)

[zoecarver]

Ping.

[zoecarver]

Ping.

[ldionne]

libcxx/include/random

1676

Can this be simplified to static_assert(!_MightOverflow || _OverflowOK || _ShrageOk, "");?

[zoecarver]

libcxx/include/random

1676

Yep :) Thanks.

[zoecarver]

• Rebase off master.
• Fix static_assert (as suggested).

[ldionne]

LGTM after fixing the nitpicks. For full disclosure, I'm relying on the tests a lot here because I am *not* a PRNG expert and I didn't take hours to research the algorithms in use. I'm trusting that you did look at other state of the art.

libcxx/test/std/numerics/rand/rand.eng/rand.eng.lcong/alg.pass.cpp

68

Inconsistent indentation here.

libcxx/test/std/numerics/rand/rand.eng/rand.eng.lcong/params.fail.cpp

17

Not needed.

19

Not needed.

33

Same.

[zoecarver]

For full disclosure, I'm relying on the tests a lot here because I am *not* a PRNG expert and I didn't take hours to research the algorithms in use. I'm trusting that you did look at other state of the art.

Neither am I. Not sure what you mean by "state of the art." I mainly went off the discussion of the bug and various online guides. An important note: this only changes how we pick what algorithm to use, it doesn't change any of the algorithms themselves.

Anyway, I'll fix the comments and land this.

libcxx/include/random

static _LIBCPP_CONSTEXPR const bool value =
               !is_convertible<_Sseq, typename _Engine::result_type>::value &&
               !is_same<typename remove_cv<_Sseq>::type, _Engine>::value;
 };
 
 // linear_congruential_engine
 
 template <unsigned long long __a, unsigned long long __c,
           unsigned long long __m, unsigned long long _Mp,
-          bool _MightOverflow = (__a != 0 && __m != 0 && __m-1 > (_Mp-__c)/__a)>
+          bool _MightOverflow = (__a != 0 && __m != 0 && __m-1 > (_Mp-__c)/__a),
+          bool _OverflowOK = ((__m|__m-1) > __m), // m = 2^n
+          bool _SchrageOK = (__a != 0 && __m != 0 && __m % __a <= __m / __a)> // r <= q
+struct __lce_alg_picker
+{
+    static_assert(__a != 0 || __m != 0 || !_MightOverflow || _OverflowOK || _SchrageOK,
+                  "The current values of a, c, and m cannot generate a number "
+                  "within bounds of linear_congruential_engine.");
+
+    static _LIBCPP_CONSTEXPR const bool __use_schrage = _MightOverflow &&
+                                                        !_OverflowOK &&
+                                                        _SchrageOK;
+};
+
+template <unsigned long long __a, unsigned long long __c,
+          unsigned long long __m, unsigned long long _Mp,
+          bool _UseSchrage = __lce_alg_picker<__a, __c, __m, _Mp>::__use_schrage>
 struct __lce_ta;
 
 // 64
 
 template <unsigned long long __a, unsigned long long __c, unsigned long long __m>
 struct __lce_ta<__a, __c, __m, (unsigned long long)(~0), true>
 {
     typedef unsigned long long result_type;

 
 private:
     result_type __x_;
 
     static _LIBCPP_CONSTEXPR const result_type _Mp = result_type(~0);
 
     static_assert(__m == 0 || __a < __m, "linear_congruential_engine invalid parameters");
     static_assert(__m == 0 || __c < __m, "linear_congruential_engine invalid parameters");
+    static_assert(_VSTD::is_unsigned<_UIntType>::value, "_UIntType must be unsigned type");
 public:
     static _LIBCPP_CONSTEXPR const result_type _Min = __c == 0u ? 1u: 0u;
     static _LIBCPP_CONSTEXPR const result_type _Max = __m - 1u;
     static_assert(_Min < _Max,           "linear_congruential_engine invalid parameters");
 
     // engine characteristics
     static _LIBCPP_CONSTEXPR const result_type multiplier = __a;
     static _LIBCPP_CONSTEXPR const result_type increment = __c;

libcxx/test/std/numerics/rand/rand.eng/rand.eng.lcong/alg.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+// <random>
+
+// template <class UIntType, UIntType a, UIntType c, UIntType m>
+//   class linear_congruential_engine;
+
+// result_type operator()();
+
+#include <random>
+#include <cassert>
+
+#include "test_macros.h"
+
+int main(int, char**)
+{
+    typedef unsigned long long T;
+
+    // m might overflow, but the overflow is OK so it shouldn't use schrage's algorithm
+    typedef std::linear_congruential_engine<T, 25214903917ull, 1, (1ull<<48)> E1;
+    E1 e1;
+    // make sure the right algorithm was used
+    assert(e1() == 25214903918);
+    assert(e1() == 205774354444503);
+    assert(e1() == 158051849450892);
+    // make sure result is in bounds
+    assert(e1() < (1ull<<48));
+    assert(e1() < (1ull<<48));
+    assert(e1() < (1ull<<48));
+    assert(e1() < (1ull<<48));
+    assert(e1() < (1ull<<48));
+
+    // m might overflow. The overflow is not OK and result will be in bounds
+    // so we should use shrage's algorithm
+    typedef std::linear_congruential_engine<T, (1ull<<2), 0, (1ull<<63) + 1> E2;
+    E2 e2;
+    // make sure shrage's algorithm is used (it would be 0s otherwise)
+    assert(e2() == 4);
+    assert(e2() == 16);
+    assert(e2() == 64);
+    // make sure result is in bounds
+    assert(e2() < (1ull<<48) + 1);
+    assert(e2() < (1ull<<48) + 1);
+    assert(e2() < (1ull<<48) + 1);
+    assert(e2() < (1ull<<48) + 1);
+    assert(e2() < (1ull<<48) + 1);
+
+    // m will not overflow so we should not use shrage's algorithm
+    typedef std::linear_congruential_engine<T, 1ull, 1, (1ull<<48)> E3;
+    E3 e3;
+    // make sure the correct algorithm was used
+    assert(e3() == 2);
+    assert(e3() == 3);
+    assert(e3() == 4);
+    // make sure result is in bounds
+    assert(e3() < (1ull<<48));
+    assert(e3() < (1ull<<48));
+    assert(e3() < (1ull<<48));
+    assert(e3() < (1ull<<48));
+    assert(e2() < (1ull<<48));
+
+  return 0;
+}
 No newline at end of file

libcxx/test/std/numerics/rand/rand.eng/rand.eng.lcong/params.fail.cpp

+//===----------------------------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+// <random>
+
+// template <class UIntType, UIntType a, UIntType c, UIntType m>
+//   class linear_congruential_engine;
+
+// requirements on parameters
+
+#include <random>
+#include <cassert>
+
+#include "test_macros.h"
+
+int main(int, char**)
+{
+    typedef unsigned long long T;
+
+    // expected-error@random:* {{static_assert failed due to requirement '1ULL == 0 || 1ULL < 1ULL' "linear_congruential_engine invalid parameters"}}
+    std::linear_congruential_engine<T, 0, 0, 0> e2;
+    // expected-error@random:* {{static_assert failed due to requirement '1ULL == 0 || 1ULL < 1ULL' "linear_congruential_engine invalid parameters"}}
+    std::linear_congruential_engine<T, 0, 1, 1> e3;
+    std::linear_congruential_engine<T, 1, 0, 1> e4;
+    // expected-error@random:* {{static_assert failed due to requirement 'std::__1::is_unsigned<int>::value' "_UIntType must be unsigned type"}}
+    std::linear_congruential_engine<int, 0, 0, 0> e5;
+
+  return 0;
+}
 No newline at end of file