Почему равномерная_д_дистрибуцияработать для 62-битных чисел, но не для 63 или 64-битных? - PullRequest
Новая
       30

Почему равномерная_д_дистрибуцияработать для 62-битных чисел, но не для 63 или 64-битных?

20 голосов
/ 27 октября 2011

Мне трудно понять, почему этот код, попытка использовать новый заголовок <random> в C ++ 11, правильно генерирует случайные числа в [0, 2**62 - 1], но не [0, 2**63 - 1] или [0, 2**64 - 1]. 

#include <iostream>
#include <stdint.h>
#include <random>
#include <functional>
#include <ctime>

static std::mt19937 engine; // Mersenne twister MT19937

void print_n_random_bits (unsigned int n);

int main (void) {
  engine.seed(time(0));
  print_n_random_bits(64);
  print_n_random_bits(63);
  print_n_random_bits(62);
  return 0;
}

void print_n_random_bits (unsigned int n)
{
  uintmax_t max;

  if (n == 8 * sizeof(uintmax_t)) {
    max = 0;
  } else {
    max = 1;
    max <<= n;
  }
  --max;

  std::uniform_int_distribution<uintmax_t> distribution(0, max);

  std::cout << n << " bits, max: " << max << std::endl;
  std::cout << distribution(engine) << std::endl;
}

Теперь, немного больше копания показывает std::mt19937_64, который имеет правильное поведение, но может ли кто-нибудь объяснить мне, почему то, что работает для 62-битного числа, не работает для 64-битного?

Редактировать : Извините, я даже не указал проблему. Проблема состоит в том, что для 63 и 64-битных максимальных значений выходной сигнал последовательно представляет собой число в диапазоне [0, 2**32 - 1], например ::

% ./rand                       
64 bits, max: 18446744073709551615
1803260654
63 bits, max: 9223372036854775807
3178301365
62 bits, max: 4611686018427387903
2943926730538475327

% ./rand                                
64 bits, max: 18446744073709551615
1525658116
63 bits, max: 9223372036854775807
2093351390
62 bits, max: 4611686018427387903
1513326512211312260

% ./rand                                                       
64 bits, max: 18446744073709551615
884934896
63 bits, max: 9223372036854775807
683284805
62 bits, max: 4611686018427387903
2333288494897435595

Редактировать 2 : я использую clang++ (Apple clang version 2.1 (tags/Apple/clang-163.7.1)) и "libc ++". Я не могу легко протестировать вышеупомянутое с GCC, поскольку моя версия не имеет поддержки c++0x.

Ответы [ 2 ]

23 голосов
/ 27 октября 2011

Вы нашли ошибку в libc ++. Спасибо !!!

Я зафиксировал следующее исправление для ревизии 143104 с острием ствола: 

Index: include/algorithm
===================================================================
--- include/algorithm   (revision 143102)
+++ include/algorithm   (working copy)
@@ -2548,7 +2548,7 @@
         {
             __u = __e_() - _Engine::min();
         } while (__u >= __y0_);
-        if (__w0_ < _EDt)
+        if (__w0_ < _WDt)
             _S <<= __w0_;
         else
             _S = 0;
@@ -2561,7 +2561,7 @@
         {
             __u = __e_() - _Engine::min();
         } while (__u >= __y1_);
-        if (__w0_ < _EDt - 1)
+        if (__w0_ < _WDt - 1)
             _S <<= __w0_ + 1;
         else
             _S = 0;

Это исправление не требует перекомпиляции двоичного libc ++. Dylib.

0 голосов
/ 27 октября 2011

Поскольку std::mt19937 является 32-битной версией, наиболее вероятно, что она делает предположения о том, какие биты имеют значение и не имеют значения в его «рабочем пространстве» при создании следующего числа.Это приводит к переполнению при генерации чисел, которые могут включать эти последние два бита.Я подозреваю, что вы обнаружите, что фактическое распределение не является действительно равномерным с максимальными числами, превышающими 2**32 - 1 на 32-битном движке.

...