-
Notifications
You must be signed in to change notification settings - Fork 10.9k
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Linear congruential generator produces different values than gcc and msvc #33554
Comments
The gzipped attachment is a small code snippet which might as well be pasted inline here: #include <random>
#include <iostream>
int main()
{
std::linear_congruential_engine<std::uint_fast64_t, 0x5DEECE66Dull, 0xBull, 1ull << 48> gen;
for (int n=0; n<3; ++n)
std::cout << gen() << ' ';
} |
It looks like this specific instance of |
I found another example where libc++ produces the wrong values: #include <random>
#include <iostream>
int main()
{
std::linear_congruential_engine<std::uint64_t, 0x18000001ull, 0x12347ull, 3ull << 56> gen;
for (int n=0; n<3; ++n)
std::cout << gen() << ' ';
std::cout << std::endl;
return 0;
} https://godbolt.org/z/8Ma5nE1hf The third output value onwards differs in libc++ due to integer overflow. This example should be fixed in #81080. |
Edit: I'm just repeating what the comment above already says, so removed. |
Oh, I've just realised who @LRFLEW is 😹 |
I looked at the original comment, and it was different enough that it's still worth mentioning. For the record the comment brought up that this construction also gives incorrect values in libc++: This is slightly different from the example I gave above in terms of why libc++ is giving the wrong result. The example in my previous comment was caused by libc++ recognizing it could use Schrage's algorithm, but incorrectly thinking it didn't need to. This example is caused by libc++ recognizing that Schrage's algorithm cannot be used here, but due to a broken static assert, ends up using the standard And yes @jwakely, I figured it was you from the GCC bug report because of your username. I ended up here because the mention of #28213 caused me to realize that issue was supposedly fixed, and looking into how it was addressed led me to finding the problems I'm addressing with #81080. |
This fixes two major mistakes in the implementation of `linear_congruential_engine` that allowed it to produce incorrect output. Specifically, these mistakes are in `__lce_alg_picker`, which is used to determine whether Schrage's algorithm is valid and needed. The first mistake is in the definition of `_OverflowOK`. The code comment and the description of [D65041](https://reviews.llvm.org/D65041) both indicate that it's supposed to be true iff `m` is a power of two. However, the definition used does not work out to that, and instead is true whenever `m` is even. This could result in `linear_congruential_engine` using an invalid implementation, as it would incorrectly assume that any integer overflow can't change the result. I changed the implementation to one that accurately checks if `m` is a power of two. Technically, this implementation has an edge case where it considers `0` to be a power of two, but in this case this is actually accurate behavior, as `m = 0` indicates a modulus of 2^w where w is the size of `result_type` in bits, which *is* a power of two. The second mistake is in the static assert. The original static assert erroneously included an unnecessary `a != 0 || m != 0`. Combined with the `|| !_MightOverflow`, this actually resulted in the static assert being impossible to fail. Applying De Morgan's law and expanding `_MightOverflow` gives that the only way this static assert can be triggered is if `a == 0 && m == 0 && a != 0 && m != 0 && ...`, which clearly cannot be true. I simply removed the explicit checks against `a` and `m`, as the intended checks are already included in `_MightOverflow` and `_SchrageOK`, and their inclusion doesn't provide any obvious semantic benefit. This should fix all the current instances where `linear_congruential_engine` uses an invalid implementation. This technically isn't a complete implementation, though, since the static assert will cause some instantiations of `linear_congruential_engine` not disallowed by the standard from compiling. However, this should still be an improvement, as all compiling instantiations of `linear_congruential_engine` should use a valid implementation. Fixing the cases where the static assert triggers will require adding additional implementations, some of which will be fairly non-trivial, so I'd rather leave those for another PR so they don't hold up these more important fixes. Fixes #33554
Extended Description
To my understanding the C++ standard does not mandate the algorithms for random number distributions but it does mandate the algorithms for random number generators like linear_congruential_engine. So one should be able to generate consistent random values across all platforms/compilers.
However, i stumbled upon inconsistent values between various compilers and verified this observation with online compilers. I am not sure which compiler is right, but at least gcc and msvc agree on their results.
Please find attached a code snippet to reproduce the observed behavior.
I put this code snippet into Rextester:
http://rextester.com/l/cpp_online_compiler_gcc (g++ 5.4.0)
http://rextester.com/l/cpp_online_compiler_clang (clang 3.8.0)
http://rextester.com/l/cpp_online_compiler_visual (Microsoft 19.00.23506 for x86)
Output:
25214903928 206026503483683 245470556921330 (gcc)
25214903928 18444698300399350051 8295313034219953650 (clang)
25214903928 206026503483683 245470556921330 (msvc)
I also put this code snippet into a Compiler Explorer project. It illustrates that Clang 3.8 and Clang trunk produce exactly the same code/values.
https://godbolt.org/g/rBSjaS
A possibly somehow related issue:
#28213
The text was updated successfully, but these errors were encountered: