30

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;
    };
};
13
  • 2
    What's the problem? Is it not compiling? Is it giving the wrong output?
    – flight
    Jul 16, 2012 at 4:56
  • 12
    system_clock::now() and now please tell me how this call could ever happen at compile-time.
    – Xeo
    Jul 16, 2012 at 4:59
  • 5
    You also need to read up on how constexpr functions have to be structured, they're basically only allowed to be a single return statement. Also, please refrain from using namespace std;. :)
    – Xeo
    Jul 16, 2012 at 5:02
  • 2
    Unrelated to your problem, but why the initial lambda call? Why not just call cout directly instead of by a lambda? Jul 16, 2012 at 5:08
  • 3
    @MichaelGraczyk Don't hope for it. This won't be built into compilers anytime soon, because: #1 it's not in the standard, and won't be anytime soon because #2 constexpr is already incredibly hard to implement as is, and isn't likely to change anytime soon (just ask compiler implementers about it), and #3 generating random numbers at compile-time is far from a common necessity (and personally, I can't think of a real use case for them, but that may be some bias). Jul 16, 2012 at 8:38

7 Answers 7

29

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.

6
  • would seeding the random library the alternative way with out chronos work? say from the answer to this question stackoverflow.com/questions/7114043/…
    – pyCthon
    Jul 16, 2012 at 5:09
  • 3
    or use the tedious but known method of template-meta-programming to implement a compile-time SRNG. Jul 16, 2012 at 5:12
  • @refp any reference's or link's?
    – pyCthon
    Jul 16, 2012 at 5:14
  • @pyCthon nope, but I could write you a working example and post it if you'd like.. with proper information on how it works. Jul 16, 2012 at 5:18
  • 2
    @pyCthon What does that Q&A have to do with seeding? You can seed with any data you have available, but need to seed with something, and __TIME__ the only viable candidate. There is no need for templates here, only constexpr, and you might also want __COUNTER__ or stackoverflow.com/questions/6166337/… . But I don't know of a prefab solution. It's a somewhat obscure problem. Jul 16, 2012 at 5:42
9

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.

5

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.

3
5

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;
}
2
  • 4
    Although your answer is valid in general, the code you wrote does nothing at compile time.
    – einpoklum
    May 29, 2021 at 17:15
  • 2
    The question is asking a compile time function, instead of runtime function. Seed-generation is the least to worry about.
    – Nick Huang
    Jun 21, 2021 at 19:17
4

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.

3

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.

3
  • i got rid of chronos now , thanks will update with out it , would it be possible to make the return type an entire c++ vector?
    – pyCthon
    Jul 16, 2012 at 5:11
  • You can only call constexpr functions from your code, so if the vector functions are constexpr, you can.
    – Cicada
    Jul 16, 2012 at 5:21
  • ok so I can't use constexpr but would my ideas work with std templates?
    – pyCthon
    Jul 16, 2012 at 5:30
1

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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.