OS X libc++ std::uniform_real_distribution bug

Question

I'm seeing some strange behavior using the C++ 11's std::uniform_real_distribution compiling with Apple LLVM version 7.0.2 (clang-700.1.81). Calling to operator() renders results outside the distribution range. The minimal sample program below reproduces the trouble

// Example program
#include <random>
#include <iostream>
#include <string>

template< int power >
constexpr uint64_t power_of_two(){
  return 2 * power_of_two< power - 1 >();
}

template< >
constexpr uint64_t power_of_two< 0 >(){
  return 1;
}

std::linear_congruential_engine
< uint64_t, 273673163155, 13, power_of_two< 48 >() >
rng;

std::uniform_real_distribution< double > angle_cosine(-1, 1);

int main()
{
    std::cout << angle_cosine.a() << " " << angle_cosine.b() << '\n' << std::endl;

    for (int i = 0; i < 4; ++i){
        std::cout << angle_cosine(rng) << std::endl;
    }
}

Compiling and running online (presumably with g++) renders reasonable results

-1 1

-0.529254
-0.599452
0.513316
-0.604338

However, compiling and running locally renders unreasonable results.

-1 1

130349
37439.4
42270.5
45335.4

Have I overlooked something or have I encountered a bug in libc++? If the latter is the case, is anyone aware of a work around?

Answer 1

It's a bug in the LLVM linear congruential generator rather than in the uniform real distribution. The uniform real distribution assumes that the number returned by the generator is between the generator's min and max values (inclusive). That's a requirement for any generator. The LLVM linear congruential generator with this set of numbers fails to satisfy that requirement.

The LLVM linear congruential generator uses an old algorithm to avoid overflow called Schrage's algorithm instead of (a*x+c)%m for your set of numbers. The LLVM implementation of that algorithm virtually guarantees that your set of a, c, m will generate numbers larger than m.

You can see the LLVM code here: https://llvm.org/svn/llvm-project/libcxx/trunk/include/random . Search for 'Schrage's algorithm'. Your choice of a, c, and m invoke the first of the four occurrences of that term.

By the way, there's a bug in your code, also. Those magic numbers 273673163155 and 13 are supposed to be base 8. Those are the numbers used by drand48. Randomly picking values for a, c, and m is almost certain to result in a bad random number generator.

I recommend switching to std::mt19937 or std::mt19937_64.