Почему uniform_int_distribution <uintmax_t> работает для 62-битных номеров, но не для 63 или 64-битных?
Мне трудно понять, почему этот код, попытка использовать новый заголовок <random>
в С++ 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)
) и "libС++". Я не могу легко протестировать выше с помощью GCC, так как моя версия не поддерживает c++0x
.
Ответы
Ответ 1
Вы нашли ошибку в libС++. Спасибо!!!
Я совершил следующее исправление для ревизии 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;
Это исправление не требует перекомпиляции двоичного libС++. dylib.
Ответ 2
Так как std::mt19937
- это 32-разрядная версия, скорее всего, что происходит, она делает предположения о том, какие биты выполняют и не имеют значения в своем "рабочем пространстве" при генерации следующего числа. Это приводит к переполнению при генерации чисел, которые могут включать в себя эти последние два бита. Я подозреваю, что вы обнаружите, что фактическое распределение не очень однородно с максимальными значениями, превышающими 2**32 - 1
на 32-битном движке.