Чому uniform_int_distribution <uintmax_t> працює для 62 бітних чисел, але не для 63 або 64 бітових?

I'm having difficulty understanding why this code, an attempt to use the new header in C++11, is correctly generating random numbers in [0, 2**62 - 1] but not [0, 2**63 - 1] or [0, 2**64 - 1].

#include 
#include 
#include 
#include 
#include 

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 distribution(0, max);

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

Тепер трохи більше копання показує std :: mt19937_64 , що має правильну поведінку, але чи може хто-небудь пояснити мені, чому те, що працює для 62-бітового номера, не працює для 64-бітового?

Edit: Sorry, I didn't even specify the problem. The problem is that for 63 and 64 bit max values, the output is consistently a number in the range [0, 2**32 - 1], e.g.:

% ./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       

Edit 2: I'm using clang++ (Apple clang version 2.1 (tags/Apple/clang-163.7.1)) and "libc++". I can't easily test the above with GCC as my version doesn't have c++0x support.

20
Розглянемо, може, просто невдачу :)
додано Автор Dani, джерело
З GCC4.6.1 всі три тести (62/63/64 біти) повертають 64-бітні значення.
додано Автор Mike Seymour, джерело
З GCC4.5.1 всі три тести (62/63/64 біти) повертають 32-бітні значення. ideone.com/3GZ9S
додано Автор interjay, джерело
Що саме робить це несподівано? Тобто, як саме він представляє вам результати, які відрізняються від ваших очікувань?
додано Автор andand, джерело
Крім того, яку стандартну бібліотеку ви використовуєте?
додано Автор Fanael, джерело

2 Відповіді

Ви виявили помилку в 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.

23
додано
Не знаю. Алгоритм вказано в стандартній специфікації для independent_bits_engine.
додано Автор Howard Hinnant, джерело
Чи використовує цей алгоритм, який використовується в libc ++, якесь відому назву, щоб прочитати про це?
додано Автор Mateusz Drost, джерело
Вау, швидка робота! Спасибі Ховарду.
додано Автор Qchmqs, джерело

Оскільки std :: mt19937 є 32-розрядною версією, швидше за все, що відбувається, це робить припущення про те, які біти роблять і не мають значення у "робочому просторі" під час створення наступного числа. Це призводить до переповнення під час створення номерів, які можуть включати останні два біти. Я підозрюю, що ви знайдете, що фактичний розподіл насправді не є однорідним з макс числами більше, ніж 2 ** 32 - 1 на 32-розрядному движку.

0
додано
Навіть якщо mt19937 повертає 32-розрядні номери, не слід uniform_int_distribution декілька разів викликати створення 62/63/64-розрядних чисел?
додано Автор interjay, джерело
Не впевнений у цьому. Короткі дослідження дозволяють припустити, що розподіл є рівномірним або приблизно так званим з максимальною кількістю 2 ** 62 - 1 , що базується на 1 000 000 цілих чисел.
додано Автор Qchmqs, джерело
IT KPI C/С++ новым годом
IT KPI C/С++ новым годом
747 учасників

Чат обсуждения С/С++. - Вопросы "напишите за меня лабу" - это оффтоп. - Оффтоп, флуд, оскорбления и вбросы здесь не приняты. - За нарушение - предупреждение или mute на неделю. - За спам и рекламу - ban. Все чаты IT KPI: https://t.me/itkpi/1147