Способ генерации случайного битового массива с равномерным распределением

Question

Как я могу сгенерировать битовый набор, длина которого кратна 8 (соответствует стандартным типам данных), где каждый бит равен 0 или 1 с равной вероятностью?

Answer 1

Следующие работы.

• Выберите ПСЧ с хорошими статистическими свойствами
• Seed это хорошо
• Генерированием целого чисел более инклюзивным диапазоном, включая минимум и максимум целочисленного типа.
• Поскольку целые числа равномерно распределены по всему их диапазону, каждое представление бит должно быть равновероятным. Поскольку все представления битов присутствуют, каждый бит одинаково похож на включение или выключение.

Следующий код выполняет это:

#include <cstdint> 
#include <iostream> 
#include <random> 
#include <algorithm> 
#include <functional> 
#include <bitset> 

//Generate the goodness 
template<class T> 
T uniform_bits(std::mt19937& g){ 
    std::uniform_int_distribution<T> dist(std::numeric_limits<T>::lowest(),std::numeric_limits<T>::max()); 
    return dist(g); 
} 

int main(){ 
    //std::default_random_engine can be anything, including an engine with short 
    //periods and bad statistical properties. Rather than cross my finers and pray 
    //that it'll somehow be okay, I'm going to rely on an engine whose strengths 
    //and weaknesses I know. 
    std::mt19937 engine; 

    //You'll see a lot of people write `engine.seed(std::random_device{}())`. This 
    //is bad. The Mersenne Twister has an internal state of 624 bytes. A single 
    //call to std::random_device() will give us 4 bytes: woefully inadequate. The 
    //following method should be slightly better, though, sadly, 
    //std::random_device may still return deterministic, poorly distributed 
    //numbers. 
    std::uint_fast32_t seed_data[std::mt19937::state_size]; 
    std::random_device r; 
    std::generate_n(seed_data, std::mt19937::state_size, std::ref(r)); 
    std::seed_seq q(std::begin(seed_data), std::end(seed_data)); 
    engine.seed(q); 

    //Use bitset to print the numbers for analysis 
    for(int i=0;i<50000;i++) 
    std::cout<<std::bitset<64>(uniform_bits<uint64_t>(engine))<<std::endl; 

    return 0; 
} 

Мы можем проверить вывод путем компиляции (g++ -O3 test.cpp) и делать некоторые статистические данные с:

./a.out | sed -E 's/(.)/ \1/g' | sed 's/^ //' | numsum -c | tr " " "\n" | awk '{print $1/25000}' | tr "\n" " " 

Результат является:

1.00368 1.00788 1.00416 1.0036 0.99224 1.00632 1.00532 0.99336 0.99768 0.99952 0.99424 1.00276 1.00272 0.99636 0.99728 0.99524 0.99464 0.99424 0.99644 1.0076 0.99548 0.99732 1.00348 1.00268 1.00656 0.99748 0.99404 0.99888 0.99832 0.99204 0.99832 1.00196 1.005 0.99796 1.00612 1.00112 0.997 0.99988 0.99396 0.9946 1.00032 0.99824 1.00196 1.00612 0.99372 1.00064 0.99848 1.00008 0.99848 0.9914 1.00008 1.00416 0.99716 1.00868 0.993 1.00468 0.99908 1.003 1.00384 1.00296 1.0034 0.99264 1 1.00036 

Поскольку все значения являются «c теряют "одно, мы заключаем, что наша миссия выполнена.

Answer 2

Вот хорошая функция для достижения этой цели:

template<typename T, std::size_t N = sizeof(T) * CHAR_BIT> //CHAR_BIT is 8 on most 
                  //architectures 
auto randomBitset() { 
    std::uniform_int_distribution<int> dis(0, 1); 
    std::mt19937 mt{ std::random_device{}() }; 

    std::string values; 
    for (std::size_t i = 0; i < N; ++i) 
     values += dis(mt) + '0'; 

    return std::bitset<N>{ values }; 
}