Минимальные стандартные генераторы случайных генераторов

Question

Минимальный стандартный генератор случайных чисел.

Я читать о минимальной стандартной генератора чисел, как показано ниже

Учитывая случайное целое число хп, следующее случайное число в случайном последовательности задается путем вычисления хп + 1 = а хп (по модулю т), где a = 7^5 = 16807 и m = 2^31 - 1 = 2147483647; в качестве проверки на вашем исполнении, если x0 = 1, то x10000 = 1043618065.

Парк и Миллер выбрали m как самое крупное Мерсеннское сечение меньше 2^32; наименьший примитивный корень из m равен 7, а так как 5 также простое, 7^5 также является примитивным корнем, следовательно, их выбор a. Так как a - примитивный корень из из m, все значения в диапазоне от 1 до m - 1 включительно будут генерироваться до любого повторения, поэтому генератор случайных чисел имеет полный период . Было показано, что множитель a = 16807 имеет хорошие характеристики случайности .

После их оригинальной работы, Парк и Миллер рекомендовали 48271 как улучшение, и некоторые люди используют 69621, но мы будем продолжать использования 16807. Самым простым способом реализовать это очевидно: просто умножить Побочные текущее значение x и вычислить модуль.

Но это может привести к переполнению промежуточного умножения, неверный результат.

Трюк Линуса Шраге позволяет выполнять умножение без переполнения : вычислить q = ⌊m/a⌋ и r = m (mod a) так, чтобы m = a q + r. Затем

нового х может быть вычислен с помощью Hi = ⌊x/q⌋ с = х (по модулю д), х = а · ли - г · привет, а затем добавить к м х, если х ≤ 0.

Вопрос: каким образом автор вычислил новое значение х в виде hi = floor (x/q) и lo = x (modq). Я ищу шаги здесь. Пожалуйста, подождите.

Answer 1

Давайте упростим обозначение. Положим H = hi и L = lo. Мы имеем m = a * q + r. Простой расчет показывает, что q = 127773 и r = 2836. Мы видим, что a < q.

Теперь дадим x_ {n} и вычислим H = x_ {n}/q и L = x_ {n}% q. Итак, x_ {n} = q * H + L с L < q.

По определению x_ {n + 1} = a * x_ {n} mod m. Вычисляя правую часть (до редукции mod m), получим a * x_ {n} = a * (q * H + L) = a * q * H + a * L = (m - r) * H + a * L = m * H - r * H + a * L.

Теперь рассмотрим r * H. Ясно 0 < = r * H < a * (x_ {n}/q). В качестве x_ {n} < m и, как указано выше, a 44 (44). В частности, он не переполняется.

Аналогичным образом 0 < a * L < a * q < m. Таким образом, снова нет переполнения.

Мы заключаем, что x_ {n + 1} = m * H - r * H + a * L.Уменьшая последнее по модулю m, получим x_ {n + 1} = -r * H + a * L, причем ни одно из двух правых выражений, переполняющих m. Если сумма отрицательна, мы добавим m, и мы закончили.