¿Cuál es la mejor manera de generar bools aleatorios?

Algunos puntos de referencia rápidos (código):

   647921509 RandomizerXorshiftPlus
   821202158 BoolGenerator2 (reusing the same buffer)
  1065582517 modified Randomizer
  1130958451 BoolGenerator2 (creating a new buffer as needed)
  1140139042 xorshift128plus
  2738780431 xorshift1024star
  4629217068 std::mt19937
  6613608092 rand()
  8606805191 std::bernoulli_distribution
 11454538279 BoolGenerator
 19288820587 std::uniform_int_distribution

Para aquellos que quieren código listo para usar, les presento XorShift128PlusBitShifterPseudoRandomBooleanGenerator, una versión modificada de RandomizerXorshiftPlus del enlace anterior. En mi máquina, es casi tan rápido como la solución de @SergeRogatch, pero consistentemente alrededor de 10-20% más rápido cuando el conteo de bucles es alto (≳100,000), y hasta ~30% más lento con recuentos de bucles más pequeños.

class XorShift128PlusBitShifterPseudoRandomBooleanGenerator {
public:
  bool randBool() {
    if (counter == 0) {
      counter = sizeof(GeneratorType::result_type) * CHAR_BIT;
      random_integer = generator();
    }
    return (random_integer >> --counter) & 1;
  }

private:
  class XorShift128Plus {
  public:
    using result_type = uint64_t;

    XorShift128Plus() {
      std::random_device rd;
      state[0] = rd();
      state[1] = rd();
    }

    result_type operator()() {
      auto x = state[0];
      auto y = state[1];
      state[0] = y;
      x ^= x << 23;
      state[1] = x ^ y ^ (x >> 17) ^ (y >> 26);
      return state[1] + y;
    }

  private:
    result_type state[2];
  };

  using GeneratorType = XorShift128Plus;

  GeneratorType generator;
  GeneratorType::result_type random_integer;
  int counter = 0;
};

Una forma sería simplemente generar un unsigned long long por cada 64 llamadas aleatorias como se indica en los comentarios. Un ejemplo:

#include <random>
class Randomizer
{
public:
    Randomizer() : m_rand(0), counter(0), randomizer(0, std::numeric_limits<unsigned long long>::max()) {}

    bool RandomBool()
    {
        if (!counter)
        {
            m_rand = randomizer(std::mt19937(rd()));
            counter = sizeof(unsigned long long) * 8;

        }
        return (m_rand >> --counter) & 1;
    }
private:
    std::random_device  rd;
    std::uniform_int_distribution<unsigned long long> randomizer;
    unsigned long long m_rand;
    int counter;
};

Rellenaría previamente un búfer (lo suficientemente largo) (circular) de valores aleatorios de 64 bits, y luego tomaría muy rápidamente un bit a la vez cuando necesite un valor aleatorio booleano

#include <stdint.h>

class BoolGenerator {
  private:
  const int BUFFER_SIZE = 65536;
  uint64_t randomBuffer[BUFFER_SIZE];
  uint64_t mask;
  int counter;

  void advanceCounter {
    counter++;
    if (counter == BUFFER_SIZE) {
        counter = 0;
    }
  }

  public:
  BoolGenerator() {
    //HERE FILL YOUR BUFFER WITH A RANDOM GENERATOR
    mask = 1;
    counter = 0;
  }

  bool generate() {
    mask <<= 1;
    if (!mask) { //After 64 shifts the mask becomes zero
        mask = 1;//reset mask
        advanceCounter();//get the next value in the buffer
    }
    return randomBuffer[counter] & mask;
  }
}

Por supuesto, la clase se puede hacer general para el tamaño del búfer, el generador aleatorio, el tipo base (no necesariamente tiene que ser uint64_t), etc.

Accediendo al buffer solo una vez cada 64 llamadas:

#include <stdint.h> //...and much more

class BoolGenerator {
  private:
  static const int BUFFER_SIZE = 65536;
  uint64_t randomBuffer[BUFFER_SIZE];
  uint64_t currValue;
  int bufferCounter;
  int bitCounter;

  void advanceBufferCounter() {
    bufferCounter++;
    if (bufferCounter == BUFFER_SIZE) {
        bufferCounter = 0;
    }
  }

  void getNextValue() {
      currValue = randomBuffer[bufferCounter];
      bitCounter = sizeof(uint64_t) * 8;
      advanceBufferCounter();
  }

  //HERE FILL YOUR BUFFER WITH A RANDOM GENERATOR
  void initializeBuffer() {
  //Anything will do, taken from here: http://stackoverflow.com/a/19728404/2436175
      std::random_device rd;
      std::mt19937 rng(rd());
      std::uniform_int_distribution<uint64_t> uni(0,std::numeric_limits<uint64_t>::max());
      for (int i = 0; i < BUFFER_SIZE; i++ ) {
          randomBuffer[i] = uni(rng);
      }
  }

  public:
  BoolGenerator() {
      initializeBuffer();
      bufferCounter = 0;
      getNextValue();
  }

  bool generate() {
      if (!bitCounter) {
           getNextValue();
      }
      //A variation of other methods seen around
      bitCounter--;
      bool retVal = currValue & 0x01;
      currValue >>= 1;
      return retVal;
  }
};

A menos que tenga más restricciones sobre la aleatoriedad que necesita, la forma más rápida de generar un bool aleatorio es:

bool RandomBool() { return false; }

Para ser más específico, hay miles de formas de generar números booleanos aleatorios, todos satisfaciendo diferentes restricciones, y muchos de ellos no entregan números aleatorios "verdaderamente" (eso incluye todas las otras respuestas hasta ahora). La palabra "aleatorio" por sí sola no le dice a nadie qué propiedades realmente necesita.

Si el rendimiento es su único criterio, entonces la respuesta es:

bool get_random()
{
    return true; // chosen by fair coin flip.
                 // guaranteed to be random.
}

Desafortunadamente, la entropía de este número aleatorio es cero, pero el rendimiento es bastante rápido.

Dado que sospecho que este generador de números aleatorios no es muy útil para usted, necesitará cuantificar qué tan aleatorio desea que sean sus booleanos. ¿Qué tal un ciclo de 2048? Un millón? 2^19937-1? Hasta el fin del universo?

Sospecho que, ya que explícitamente declaró que el rendimiento es su máxima preocupación, entonces un buen generador congruente lineal a la antigua podría ser "lo suficientemente bueno". Basado en este artículo , supongo que el período de este generador está alrededor 32*((2^31)-5), o alrededor de 68 billones de iteraciones. Si eso no es" lo suficientemente bueno", puede agregar cualquier generador compatible con C++11 que desee en lugar de minstd_rand.

Para obtener crédito adicional, y un pequeño éxito de rendimiento, modifique el siguiente código para usar el algoritmo de moneda sesgada para eliminar el sesgo en el generador.

#include <iostream>
#include <random>

bool get_random()
{
    typedef std::minstd_rand generator_type;
    typedef generator_type::result_type result_type;

    static generator_type generator;
    static unsigned int bits_remaining = 0;
    static result_type random_bits;

    if ( bits_remaining == 0 )
    {
        random_bits = generator();
        bits_remaining = sizeof( result_type ) * CHAR_BIT - 1;
    }

    return ( ( random_bits & ( 1 << bits_remaining-- ) ) != 0 );
}

int main()
{
    for ( unsigned int i = 0; i < 1000; i++ )
    {
        std::cout << " Choice " << i << ": ";
        if ( get_random() )
            std::cout << "true";
        else
            std::cout << "false";

        std::cout << std::endl;
    }
}

Si el rendimiento es importante, tal vez sea una buena idea generar un número aleatorio de 32 bits y usar cada bit separado de él, algo como esto:

bool getRandBool() {
    static uint32_t randomnumber;
    static int i=0;
    if (i==0) {
        randomnumber = <whatever your favorite randonnumbergenerator is>;
        i=32;
    }
    return (randomnumber & 1<<--i); 
 }

De esta manera la generación solo impacta cada llamada 32

Creo que la mejor manera es un uso de matriz aleatoria precalculada:

uint8_t g_rand[UINT16_MAX];
bool InitRand()
{
    for (size_t i = 0, n = UINT16_MAX; i < n; ++i)
        g_rand[i] = ::rand() & 1;
    return true;
}
bool g_inited = InitRand();
inline const uint8_t * Rand()
{
    return g_rand + (::rand()&INT16_MAX);
}

Se usa para llenar algún array dst [size]:

const size_t size = 10000;
bool dst[size];
for (size_t i = 0; i < size; i += INT16_MAX)
     memcpy(dst + i, Rand(), std::min<size_t>(INT16_MAX, size - col));

Por supuesto, puede inicializar una matriz pre-calculada con el uso de otra función aleatoria.

Aparentemente tengo que agregar otra respuesta. Acabo de descubrir que a partir de Ivy Bridge arquitectura Intel agregó RdRand la instrucción de CPU y AMD la agregó más tarde en junio de 2015. Entonces, si está apuntando a un procesador que es lo suficientemente nuevo y no le importa usar ensamblado (en línea), la forma más rápida de generar bools aleatorios debería ser llamando a RdRand Instrucciones de CPU para obtener un número aleatorio de 64 bits como se describe aquí (desplácese aproximadamente a la mitad de la página para ver el código ejemplos) (en ese enlace también hay un ejemplo de código para comprobar la compatibilidad de la CPU actual con la instrucción RdRand, y ver también la Wikipedia para una explicación de cómo hacer esto con la instrucción CPUID), y luego usar los bits de ese número para booleanos como se describe en mi Respuesta basada en Xorshit+ .