Как проверить std::bitset на случайность?

Question

Я создаю случайные наборы битов с помощью следующего кода ниже. Теперь я хочу написать какой-нибудь тест и спросить себя, как проверить случайность наборов битов? Есть ли хорошее решение этой проблемы?

Поскольку битовые наборы не могут быть представлены в виде чисел AFAIK, я не знаю, стоит ли применять какой-то тест, такой как хи-квадрат или что-то еще.

Должен ли я считать вхождения 1 и 0, как

 1001
+0101
+1110
+0010
 ----
 2222 = good as half of 4 (bitsets) equal 2

Есть ли другие способы?

template <size_t N>
using bitset_t = std::bitset<N>;

а также

template <size_t N>
struct random_bitset_t
{
  static_assert(N % 64 == 0, "random_bitset_t<N> only with N % 64 == 0");

  std::bitset<N> operator()() const;
};

template <size_t N>
std::bitset<N> random_bitset_t<N>::operator()() const
{
  static thread_local std::mt19937 g{std::random_device{}()};

  static thread_local std::uniform_int_distribution<uint64_t> d;

  std::bitset<N> bitset;

  for (int i=0,j=N/64; i<j; ++i)
  {
    bitset <<= 64;

    bitset |= std::bitset<N>(d(g));
  }
  return bitset;
}

а также

template <size_t N>
using bitsets_t = std::vector<bitset_t<N>>;

а также

template <size_t N>
struct random_bitsets_t
{
  random_bitsets_t(size_t);

  bitsets_t<N> operator()() const;

  size_t size;
};

template <size_t N>
random_bitsets_t<N>::random_bitsets_t(size_t size)
: size(size)
{}

template <size_t N>
bitsets_t<N> random_bitsets_t<N>::operator()() const
{
  bitsets_t<N> bitsets;

  bitsets.reserve(size);

  std::generate_n(std::back_inserter(bitsets),size,random_bitset_t<N>());

  return bitsets;
}

Answer 1

Запишите (последовательно) все биты из множества циклов в двоичный файл. Попробуйте написать около 500 КБ данных. Затем научитесь использовать существующие инструменты, такие как Ent. Вы бы сделали ent -b имя файла и посмотреть, если вы получите хорошие результаты. Это стандартный тест.

Когда тебе станет лучше, попробуй Diehard. Для этого требуется около 10 МБ тестовых данных, но достовернее понять их гораздо сложнее.

Предостережение.

Так как вы используете Mersenne Twister, вам нужно только проверить свою процедуру создания набора битов. Реализация Twister уже должна была быть проверена. Вам не нужен Diehard, так как ваш генератор битов будет достаточно протестирован Ent.