Будет ли разница между RAND_MAX и UINT_MAX?

Question

Моя домашняя работа заключается в создании случайных целых чисел от 0 до 2^30.Теперь, в прошлом мы узнали, что rand() возвращает только целые числа до RAND_MAX, что это меньше, чем UINT_MAX, и что мы можем использовать битовое смещение, чтобы заполнить эту емкость UINT_MAX.Из некоторого чтения, которое я сделал (здесь, на SO), я понимаю, что это может быть не очень хорошей идеей, если распределение этих чисел имеет значение для меня.Сказав это, мой профессор определил этот метод.

Мой вопрос, на сколько сдвинуть бит?Будет ли разница между RAND_MAX и UINT_MAX всегда такой, чтобы существовала безопасная константа для сдвига битов?Или есть какое-то начальное исследование, которое необходимо выполнить, чтобы определить число, на которое нужно сдвинуть бит?Должен ли я просто немного сдвигать биты и проверять по UINT_MAX?

Причина, по которой я спрашиваю, состоит в том, что UINT_MAX определено как минимум определенное число (65535), но намоя машина UINT_MAX намного больше (4294967295).Это беспокоило меня, что я могу закончить свою домашнюю работу в выходные, прийти в школу и обнаружить, что все не работает достаточно хорошо, чтобы отправить.

Спасибо!

Ссылки:

Я прочитал пару похожих вопросов, но не смог получить от них ответа.

Значение RAND_MAX всегда (2^n)-1?

, генерирующее случайное число в диапазоне от 0 до n, где nможет быть > RAND_MAX

На самом деле, второй вопрос выше заставляет меня задуматься о том, стоит ли вообще это делать?

Answer 1

Ваш вопрос касается того, имеют ли RAND_MAX и UINT_MAX сдвиг между ними. Это сводится к вопросу о том, имеют ли UINT_MAX и RAND_MAX форму 2^k - 1. UINT_MAX почти наверняка будет на любом компьютере с двоичной системой счисления. Если sizeof(int)=32 битов, то k=32, если sizeof(int)=64 bit, то k=64 и т. Д. Теперь мы можем перейти к рассмотрению RAND_MAX. В большинстве реализаций ответ таков: RAND_MAX почти всегда будет иметь форму 2^k - 1. Зачем? Нам нужно рассмотреть, как на самом деле работает большинство реализаций rand().

1. rand() обычно использует линейный конгруэнтный генератор (см. http://en.wikipedia.org/wiki/Linear_congruential_generator или Кнут «Искусство программиста, часть 2: полуколичественные алгоритмы»). В основном случайное число представляет собой последовательность с seed

   x (k + 1) = (a x (k) + c)% m

(то есть библиотека C хранит последнюю итерацию x(k), а когда вы вызываете rand(), она возвращает x(k+1))

1. Для обеспечения хорошего качества параметры генератора (a, c и m) должны быть тщательно выбраны. Качество обычно подразумевает, сколько раз до того, как последовательность повторяется, и т. Д. Одно из ограничений при выборе этих параметров состоит в том, чтобы сделать m как можно ближе к UINT_MAX, чтобы избежать потери случайных битов. Если вы изучаете генераторы, обычно правильный выбор - сделать m несколько меньше, чем UINT_MAX. Вам также нужно сделать m простым числом.

2. Обычно вы хотите, чтобы rand() был максимально быстрым, поэтому вы хотите, чтобы эти операции были дешевыми. Самый дешевый mod для вычисления - это один из вариантов foo % (2^k - 1), потому что он может быть реализован как foo & (1<<k-1). За специальный выбор k вы получите простое число Мерсенна.

Например, общий выбор - k=31, который дает простое число 2^31-1 = 2147483647. Это типичный выбор для 32-разрядных целых чисел, где UINT_MAX=2^32-1 = 4294967295. Для 64-битных чисел каждый имеет UINT_MAX=2^64-1=18446744073709551615, и выбор для RAND_MAX будет 2^61-1 = 2305843009213693951.

Итак, в заключение, чтобы ответить на ваш вопрос: в большинстве реализаций вы можете предположить, что есть простой сдвиг битов, однако реальной гарантии нет. По крайней мере, вы должны выполнить тест во время выполнения программы init. Если вы используете C ++, лучше использовать static_assert для определения во время компиляции, верны ли ваши предположения и не компилируются ли они, если это не так. Boost обладает таким статическим утверждением, как и недавно утвержденный стандарт C ++ 11 ... то есть, что можно сделать (хотя для написания статической версии is_power_of_two_minus_one может потребоваться некоторая работа:

unsigned int myrand()
{
        static_assert(sizeof(int)==4,"sizeof(unsigned int) != 4");
        static_assert(is_power_of_two_minus_one(RAND_MAX),"RAND_MAX not a power of two minus one");
        static_assert(is_power_of_two_minus_one(UINT_MAX),"UINT_MAX not power of two minus one");
        unsigned int raw_rand=rand();
        // do your bit shift to adjust raw_rand
        return raw_rand;
}

Answer 2

На самом деле, второй вопрос выше заставляет меня задуматься о том, стоит ли вообще это делать?

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

Для RAND_MAX, являющегося 2^n - 1, я бы вообще так предположил. Способ, которым компьютеры генерируют случайные числа, представляет собой заданное количество битов за раз, поэтому, если максимальное значение не было 2^n - 1, либо не все числа в диапазоне могут быть возвращены, либо энтропия будет потрачена впустую.

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

И вы не можете зайти на школьный сервер, на котором вы (в конце концов) запустите это?