Безопасно ли взять всего несколько битов из числа, полученного с помощью Вихря Мерсенна?

Мне приходится работать с кодом, созданным сотрудником, который сейчас на пенсии, и у меня есть несколько странных вещей, связанных со случайными числами. В некоторых точках он сдвигал значение, возвращаемое PRNG, на 10 бит вправо, а затем использовал маску для этого значения.

Я уже видел в Интернете, что некоторые PRNG имеют плохие свойства случайности с некоторыми битами в числе, которое они генерируют (например, последний, просто чередующийся между 1 и 0), но я искал, существует ли какой-либо мусор для таких проблем на Мерсенн Твистер, но я не нашел ни одного. Кто-нибудь что-нибудь знает об этом?


c random mersenne-twister prng
person Loufylouf    schedule 25.11.2014    source источник
comment
Основная часть этого кода заключается в генерации гауссового шума, поэтому rau берется из таблицы релея, где индекс представляет собой номер сдвига и маски, а teta берется из того же случайного числа, но на этот раз только замаскированного, а не сдвинутого.   -  person Loufylouf    schedule 25.11.2014
comment
в С++ 11 объявление чистого гауссовского генератора занимает две строки кода. Если С++ 11 является вариантом, замена всех ваших старых, не отказоустойчивых, пользовательских генераторов на STL может быть хорошим вариантом.   -  person galinette    schedule 25.11.2014
comment
Приятно смотреть: channel9.msdn.com/Events/GoingNative/2013/   -  person galinette    schedule 25.11.2014
comment
Спасибо, я посмотрю это из любопытства, но мы должны оставить это на C. Было решено, что хранить такие вещи, не зная, в чем их идея, было бы нехорошо. Так что мне придется модифицировать его и написать кое-какую документацию, чтобы избежать подобных ситуаций в будущем. Спасибо всем за ваши ответы.   -  person Loufylouf    schedule 28.11.2014

Ответы (2)


arrow_upward
1
arrow_downward

В норме любой бит должен быть случайным, это свойство твистера Мерсенна.

Однако (я не очень глубоко знаю МП) у вас может быть долговременная зависимость между некоторыми битами. Рекомендуется использовать библиотечные функции для установки целочисленного диапазона, а не упорядочивать биты самостоятельно, иначе вы никогда не знаете, какие сложные свойства он может получить.

Если вы используете стандартную библиотеку С++ 11, просто используйте std::mt19937 вместе с std::uniform_int_distribution.

person galinette    schedule 25.11.2014

arrow_upward
-1
arrow_downward

Я не уверен, в частности, о вихре Мерсенна, но на ум приходит типичный совет, который можно получить при попытке получить случайное целое число в диапазоне [0, n). Если у вас есть PRNG, возвращающий целые числа с большим диапазоном, чем n, вы никогда не должны использовать модуль для уменьшения диапазона, например

x = rand() % n;

но следует масштабировать число

x = (int) floor(((double) rand()) / ((double) RAND_MAX)) * n);

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

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

person ANSI C Mastah    schedule 25.11.2014
comment
Я предполагаю, что он знал, что использует PRNG с плохими свойствами случайности для первых нескольких битов, поэтому он сдвинул это число, чтобы использовать маску для самых случайных битов числа. Но это, к сожалению, только предположение. - person Loufylouf; 25.11.2014
comment
Это относится только к абсолютно дерьмовым ГПСЧ (которым обычно и является rand()). Но правильный выбор — перейти на лучший PRNG вместо полировки какашки. Даже с посредственными PRNG, такими как Mersenne Twister, это не проблема. - person CodesInChaos; 25.11.2014
comment
Я просто пытаюсь помочь ответить на вопрос. Вопрос касается C и другого сотрудника вышел на пенсию, поэтому предположение, что PRNG может быть не самым лучшим, верно. Что касается предложений по обновлению/написанию нового кода, я бы просто предложил использовать такую ​​библиотеку, как GSL. - person ANSI C Mastah; 25.11.2014
comment
ДВ: С x = rand() % n;, x < n. Но с x = (int) floor(((double) rand()) / ((double) RAND_MAX)) * n);, x <= n. - person chux - Reinstate Monica; 14.01.2018