Random output different between implementations

5
votes

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?

2
c++c++11random
Why do you expect diffrerent implementations of random number generation to produce equal values? – lisyarus
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
The exact same algorithm should produce the same values given the same seed, should it not? Your arguments don't make sense. – user5368921
@rlbond It is not the Mersenne Twister but rather std::uniform_int_distribution – NathanOliver
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

2 Answers

10
votes

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.

3
votes

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.