Generate random numbers in C++ at compile time

Question

I'm trying to precompute random values using C++11's random library at compile time. I'm mostly following examples. What am I doing wrong here?

using namespace std;
#include <iostream>
#include <vector>
#include <random>

vector<double> rands;
typedef std::mt19937_64 RNG;
uint64_t seed_val;
RNG rng; 

void initialize() {
     rng.seed(seed_val);
}

constexpr vector<double> generate_random( )                 //size_t numbers)
{   
    int numbers = 1000;
    std::uniform_real_distribution<double> zero_one(0.0, 1.0);
        for (unsigned int i = 0; i < numbers; i++) { 
             double rand_num = zero_one(rng);
             rands.push_back( rand_num );
    }
    return rands;
}

int main()
{
    cout << "TMP rands";
    for_each( rands.begin(), rands.end(), [] (double value)
    {
        cout<<value<<endl;
    });
}

Here's an example compile-time random number generator shamelessly stolen from here, but thought it might be useful for anyone who looks this up:

template<u32 S, u32 A = 16807UL, u32 C = 0UL, u32 M = (1UL<<31)-1>
struct LinearGenerator {
    static const u32 state = ((u64)S * A + C) % M;
    static const u32 value = state;
    typedef LinearGenerator<state> next;
    struct Split { // Leapfrog
        typedef LinearGenerator< state, A*A, 0, M> Gen1;
        typedef LinearGenerator<next::state, A*A, 0, M> Gen2;
    };
};

Answer 1

Only constexpr functions and constant expressions may be evaluated at compile time. That rules out <chrono> and <random>.

What you can do is access the __TIME__ preprocessor macro and define your own PRNG composed of one-line, constexpr functions.

Answer 2

There is a research paper on the topic: Random number generator for C++ template metaprograms containing code snippet for the __TIME__ trick. It also talks about supporting different random number engines and distributions as orthogonal choices.

Answer 3

I know this question is five years old, and already has an accepted answer. Even so, I would like to add that it certainly is possible to generate random numbers at compile time, with the understanding that you'll get the same sequence of random numbers each time you run the program. To put it simply, if the seed is known at compile time, the compiler is allowed to figure out what random numbers will be output, and just turn the program into "output this sequence of numbers."

Compilers will have limits to how aggressively they optimize, so I can't promise that they will always make this substitution, and I doubt any compiler would be able to make the substitution for something as complex as the Mersenne Twister, but something simpler like linear_congruential_engine has a chance (also, the only way to be sure that it happened would be to have the compiler output assembly code, and then you look at the assembly code).

I know this is possible because I implemented a random generator modeled after random_device that used Marsaglia's Xorshift algorithm. Since Marsaglia's paper actually included multiple related algorithms, I had the class take a template parameter to select which shift pattern to use. I wanted to know if the compiler would optimize out the switch statement I used. I forgot to pass a seed, so the compiler used the default, i.e., the seed was known at compile time. When I looked at the assembly code, not only was the switch gone, but GCC had optimized the program into "output these three numbers."

The final version of the program listed in the question never actually called the functions to generate the sequence of numbers, and never called the function to seed the generator. This version will do that, but I doubt it will be turned into "print this sequence of random numbers."

#include <algorithm>
#include <cstdlib>
#include <iostream>
#include <iterator>
#include <random>

int get_seed()
{
    int hour = std::atoi(__TIME__);
    int min = std::atoi(__TIME__ + 3);
    int sec = std::atoi(__TIME__ + 6);
    return 10000 * hour + 100 * min + sec;
}

int main()
{
    // get_seed() returns an int based on __TIME__ (a string literal
    // set by the preprocessor), which is known at compile time.
    //
    // Also, w/r/t the engines in <random>: not setting a seed explicitly
    // will use a default seed, which is known at compile time.  So if
    // you're OK getting the same sequence of numbers for any compilation,
    // then "std::mt19937_64 rng;" may be all you need.
    std::mt19937_64 rng(get_seed());
    std::uniform_real_distribution<double> zero_one(0.0, 1.0);
    const int COUNT = 1000;
    std::generate_n(std::ostream_iterator<double>(std::cout, "\n"), COUNT,
        [&rng, &zero_one]() { return zero_one(rng); });
    return 0;
}

Answer 4

I would try pulling it in from an external source. A very simple example is to compile your program with defined macro variables in the compile command. Here $RANDOM is a special built-in variable in unix/linux systems that automatically returns a random 16-bit number.

g++ -D__RANDOM__=$RANDOM yourprog.cpp -o yourprog

//yourprog.cpp
#include <iostream>
int main() {
  std::cout << "Random variable " << __RANDOM__ << std::endl;
  return 0;
}

You can also write your own script or executable to assign to your macro variable.

//DevRandomGenerator.cpp
#include <iostream>
#include <fstream>

class DevRandom {
private:
    std::ifstream stream;
public:

    DevRandom() {
        stream.open("/dev/urandom",std::ios::in|std::ios::binary);
    }

    unsigned int unsignedInt() {
        unsigned int u = 0;
        stream.read((char*)&u, sizeof(unsigned int));
        return u;
    }
};

int main() {
  DevRandom rand;
  std::cout << rand.unsignedInt() << std::endl;
  return 0;
}

then compile as:

g++ DevRandomGenerator.cpp -o DevRandomGenerator
g++ -D__RANDOM__="$(./DevRandomGenerator)" yourprog.cpp -o yourprog

A better random generator would be to write a program that uses audio and visual inputs.

Answer 5

This question may now be nine years old but I still did not find any satisfying solution so I implemented a reliable compile time random generator as a single header library myself. It uses KISS random generator and represents its internal state as a parameterized type. The state is pseudo remembered using the counter macro. CTRandomTimeSeed is an attempt to implement a varring seed between multiple compilations. Additionally a custom seed can be defined using DYNLEC_CUSTOM_RANDOM_SEED.

#pragma once

#include <cstdint>

// all numbers are generated randomly at compile time. the internal state is pseudo
// remembered using the counter macro. the seed is based on time using the timestamp
// and time macro. additionally a custom random seed can be specified to fully rely

#ifndef DYNLEC_CUSTOM_RANDOM_SEED
#define DYNLEC_CUSTOM_RANDOM_SEED 0xbdacf99b3f7a1bb4ULL
#endif

// just iterating over the macros will always result in same
// number because the internal state is only updated for each occurance
// of the following macros

// generates a random number seeded with time and the custom seed
#define DYC_RAND_NEXT (::Dynlec::CTRandomGeneratorValueSeeded<__COUNTER__>)
// generates a random number seeded with time and the custom seed between min and max ( [min, max[ )
#define DYC_RAND_NEXT_BETWEEN(min, max) (min + (::Dynlec::CTRandomGeneratorValueSeeded<__COUNTER__> % (max - min)))
// generates a random number seeded with time and the custom seed with a limit ( [0, limit[ )
#define DYC_RAND_NEXT_LIMIT(limit) DYC_RAND_NEXT_BETWEEN(0, limit)
// helper macro for non repetetive indexed values
#define DYC_RAND_INDEXED(index) (::Dynlec::CTRandomGeneratorValue<index, ::Dynlec::CTRandomSeed ^ DYC_RAND_NEXT>)
// helper macro for non repetetive random streams
#define DYC_RAND_STREAM(n, callback) (::Dynlec::CTRandomStream<n, ::Dynlec::CTRandomSeed ^ DYC_RAND_NEXT>)

namespace Dynlec
{
    // the random generator internal state is represented by
    // the CTRandomGeneratorRaw type with each of its values
    // x, y, z and c
    template <
        uint64_t x, 
        uint64_t y, 
        uint64_t z, 
        uint64_t c>
    class CTRandomGeneratorRaw
    {
        static_assert(y != 0, 
            "CompileTimeRandom can not be used with 'y' equals 0");
        static_assert(z != 0 || c != 0,
            "CompileTimeRandom can not be used with 'z' and 'c' equals 0");
    public:
        typedef CTRandomGeneratorRaw<
            6906969069ULL * x + 1234567ULL,
            ((y ^ (y << 13)) ^ ((y ^ (y << 13)) >> 17)) ^ (((y ^ (y << 13)) ^ ((y ^ (y << 13)) >> 17)) << 43),
            z + ((z << 58) + c),
            ((z + ((z << 58) + c)) >> 6) + (z + ((z << 58) + c) < ((z << 58) + c))> Next;

        constexpr static uint64_t Value = x + y + z;
    };

    // to prevent any accidental selection of invalid parameters
    // these values are omitted
    template <
        uint64_t x,
        uint64_t y,
        uint64_t z,
        uint64_t c>
    class CTRandomGeneratorRawSafe
        :
        public CTRandomGeneratorRaw<
            x, (y == 0) ? 1 : y, (z == 0 && c == 0) ? 1 : z, c>
    {
    };

    // CTRandomGenerator is used to quickly compute the nth iteration
    // of CTRandomGeneratorSafeRaw based on a single uint64_t seed
    template <uint64_t iterations, uint64_t seed>
    class CTRandomGenerator
    {
        friend CTRandomGenerator<iterations + 1, seed>;
        typedef typename CTRandomGenerator<iterations - 1, seed>::Current::Next Current;

    public:
        constexpr static uint64_t Value = Current::Value;
    };

    template <uint64_t seed>
    class CTRandomGenerator<0ULL, seed>
    {
        friend CTRandomGenerator<1ULL, seed>;

        typedef typename CTRandomGeneratorRawSafe<
            seed ^ 1066149217761810ULL,
            seed ^ 362436362436362436ULL,
            seed ^ 1234567890987654321ULL,
            seed ^ 123456123456123456ULL>::Next Current;

    public:
        constexpr static uint64_t Value = Current::Value;
    };

    template <uint64_t iteration, uint64_t seed>
    constexpr static uint64_t CTRandomGeneratorValue = CTRandomGenerator<iteration, seed>::Value;

    const uint64_t CTRandomTimeSeed = 
        CTRandomGeneratorValue<0, (__TIME__[0]) ^
        CTRandomGeneratorValue<0, (__TIME__[1]) ^
        CTRandomGeneratorValue<0, (__TIME__[3]) ^
        CTRandomGeneratorValue<0, (__TIME__[4]) ^
        CTRandomGeneratorValue<0, (__TIME__[6]) ^
        CTRandomGeneratorValue<0, (__TIME__[7])>>>>>> ^
        CTRandomGeneratorValue<0, (__TIMESTAMP__[0]) ^
        CTRandomGeneratorValue<0, (__TIMESTAMP__[1]) ^
        CTRandomGeneratorValue<0, (__TIMESTAMP__[2]) ^
        CTRandomGeneratorValue<0, (__TIMESTAMP__[4]) ^
        CTRandomGeneratorValue<0, (__TIMESTAMP__[5]) ^
        CTRandomGeneratorValue<0, (__TIMESTAMP__[6])>>>>>> ^
        CTRandomGeneratorValue<0, (__TIMESTAMP__[8]) ^
        CTRandomGeneratorValue<0, (__TIMESTAMP__[9]) ^
        CTRandomGeneratorValue<0, (__TIMESTAMP__[20]) ^
        CTRandomGeneratorValue<0, (__TIMESTAMP__[21]) ^
        CTRandomGeneratorValue<0, (__TIMESTAMP__[22]) ^
        CTRandomGeneratorValue<0, (__TIMESTAMP__[23])>>>>>>;

    const uint64_t CTRandomSeed = (DYNLEC_CUSTOM_RANDOM_SEED ^ CTRandomTimeSeed);

    template <uint64_t iteration>
    constexpr static uint64_t CTRandomGeneratorValueSeeded = CTRandomGeneratorValue<iteration, CTRandomSeed>;

    template <uint64_t n, uint64_t seed = ::Dynlec::CTRandomSeed>
    struct CTRandomStream
    {
        // callback(uint64_t index [0;n[, uint64_t random_number)
        template <typename T>
        static void Call(T callback)
        {
            CTRandomStream<n - 1, seed>::Call(callback);
            callback(n - 1, CTRandomGeneratorValue<n, seed>);
        }
    };

    template <uint64_t seed>
    struct CTRandomStream<0, seed>
    {
        template <typename T>
        static void Call(T callback) { }
    };
}

Usage example:

// random 64 bit number
std::cout << DYC_RAND_NEXT << std::endl;

// random 64 bit number between [0 and 10[
std::cout << DYC_RAND_NEXT_LIMIT(10) << std::endl;

// random 64 bit number between [1 and 10]
std::cout << DYC_RAND_NEXT_BETWEEN(1, 11) << std::endl;

// initialize array with random numbers
int array[50];

Dynlec::CTRandomStream<50>::Call([&array](uint64_t index, uint64_t n)
    { 
        array[index] = n;
    });

Link to the github project containing the project.

Answer 6

Not just is system_clock::now() not compile-time knowable, but your function is labeled as returning a bool, but has no return statement anywhere.

Answer 7

As per the error message:

cpp11tmprands.cpp:22:15: error: ‘rands’ was not declared in this scope

The variable rands is not declared in the scope of main. Make it a global variable instead of local in generate_random and that error will go away.