5

I've tried this program with libstdc++, libc++ and dinkumware:

#include <iostream>
#include <algorithm>
#include <vector>
#include <random>
#include <functional>
#include <limits>

int main()
{
    std::vector<int> v(10);

    std::mt19937 rand{0};
    std::uniform_int_distribution<> dist(
        1, 10
    );

    std::generate_n(v.begin(), v.size(),
        std::bind(dist, rand));

    for (auto i : v)
        std::cout << i << " ";
}

Output respectively is:

6 6 8 9 7 9 6 9 5 7 

6 1 4 4 8 10 4 6 3 5 

5 10 4 1 4 10 8 4 8 4

The output is consistent for each run but as you can see, they're different. Explain?

Barry
  • 286,269
  • 29
  • 621
  • 977
user5368921
  • 53
  • 3
  • 4
    Why do you expect diffrerent implementations of *random number generation* to produce equal values? – lisyarus Sep 23 '15 at 17:43
  • 6
    Explain *what*? Consistency between runs? Or inconsistency between implementations? Different implementations are allowed to produce different pseudo-random sequences from the same seed. This is exactly what you observed. – AnT stands with Russia Sep 23 '15 at 17:44
  • The exact same algorithm should produce the same values given the same seed, should it not? Your arguments don't make sense. – user5368921 Sep 23 '15 at 17:50
  • This is a really good question. The difference means you can't use the library as a random source for things like Minecraft world seeds. Your program would need to include its own random generator. But, as it is obviously true, we just have to live with it. – Zan Lynx Sep 23 '15 at 17:50
  • @user5368921: You may be seeing differences in the distribution implementations, not the engines. – Blastfurnace Sep 23 '15 at 17:51
  • I'm not sure the above comments are correct. The Mersenne Twister is a pretty well-known algorithm. If all the parameters are the same, and the seed is the same, the output should be the same as well. It's possible, however, that the different implementations have different default template arguments, or that they are using one of the "fast" MT variants. https://en.wikipedia.org/wiki/Mersenne_Twister – rlbond Sep 23 '15 at 17:58
  • 3
    @rlbond It is not the Mersenne Twister but rather `std::uniform_int_distribution` – NathanOliver Sep 23 '15 at 17:59
  • @Blastfurnace Correct. The first two comments surprise me that people believe that the exact same algorithm should produce different results. – user5368921 Sep 23 '15 at 18:00
  • In fact, the standard even says: "Required behavior: The 10000 th consecutive invocation of a default-constructed object of type mt19937 shall produce the value 4123659995." in section 26.5.5.3. – rlbond Sep 23 '15 at 18:01
  • @rlbond If the implementation is conforming, it will use the parameters defined by the standard. I'm not sure on the legality of it providing variants though, but with `std::mt19937` it should be exactly the same. – user5368921 Sep 23 '15 at 18:02
  • @NathanOliver ah, I overlooked that. You are correct, there has to be a difference in implementation. If OP called `operator()` for `rand` he would see the same sequence. – rlbond Sep 23 '15 at 18:02
  • 2
    Personally I think it would be funny if someone implemented `mt19937` in such a way that it counted the number of invocations and simply returned 4123659995 if the count was 10,000, and the rest of the time just used a different algorithm. – rlbond Sep 23 '15 at 18:04

2 Answers2

10

There is no required implementation for uniform_int_distribution<>. [rand.dist.general] specifies that:

The algorithms for producing each of the specified distributions are implementation-defined.

All that [rand.dist.uni.int] states is:

A uniform_int_distribution random number distribution produces random integers i, a <= i <= b, distributed according to the constant discrete probability function P(i | a, b) = 1/(b − a + 1) .

Each implementation is free to achieve this distribution how it wishes. What you are seeing is apparently three different implementations.

Barry
  • 286,269
  • 29
  • 621
  • 977
  • Wow. This is extremely unintuitive. I would have also expected given the same seed the value of every consecutive call is well defined. Which C++11 random number algorithm defines that behavior (if any)? – David Sep 23 '15 at 17:54
  • The standard defines how mersenne twister should be implemented in `[rand.eng.mers]`. – user5368921 Sep 23 '15 at 17:56
  • Yes, the first part of your answer is the key. If I get rid of the `uniform_int_distribution`, the results are identical across implementations. – user5368921 Sep 23 '15 at 17:58
  • @David yes there is http://www.cplusplus.com/reference/random/linear_congruential_engine/ – Hatted Rooster Sep 23 '15 at 18:00
3

To be clear: the random number generators themselves are specified quite tightly--including the input parameters and results. To be technical, what's specified is the 10000th result from a default-constructed generator, but for any practical purpose a match on this result from a generator that's at least reasonably close to correct otherwise essentially guarantees that the generator is working correctly, and its outputs will match ever other similar generator for a given seed.

For example, a quick test:

#include <random>
#include <iostream>

int main() { 
    std::mt19937 r;

    for (int i=0; i<10000-2; i++)
        r();
    for (int i=0; i<3; i++)
        std::cout << r() << "\n";
}

...shows identical results with every (recent) compiler I have handy:

1211010839
4123659995
725333953

The second of those three is the value required by the standard.

More leeway is given, however, in the distribution templates. A uniform_int_distribution has to map inputs to outputs uniformly, but there are different ways of doing that, and no requirement about which of those ways to use.

If you really need to produce a sequence of integers within a range that's not only uniformly distributed, but consistent between implementations, you'll probably have to implement your own distribution code. Doing this well isn't quite as trivial as most people initially think. You might want to look at one of my previous answers for a working implementation along with some explanation and a bit of test code.

Community
  • 1
  • 1
Jerry Coffin
  • 476,176
  • 80
  • 629
  • 1,111
  • By the way, uniform_int_distribution is not even required to draw just one number from the generator, and some (libgcc?) draw two to output just one number. – Kostas Sep 17 '21 at 09:14