一様分布のランダムビットセットを生成する方法

Question

長さが8の倍数（標準データ型に対応）のビットセットを生成するにはどうすればよいですか？各ビットは等しい確率で0または1ですか？

Answer 1

次のように動作します。

• 良好な統計的特性を有するPRNGを選択シードはそれが十分
• 整数型の最小値と最大値を含む包含範囲にわたる整数を生成します。
• 整数が範囲全体に均等に分散されているため、各ビット表現は等しくなる可能性があります。すべてのビット表現が存在するため、各ビットは同じようにオンまたはオフになります。

次のコードは、これを実現：

#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 }; 
}