Масштабирование равномерного случайного диапазона Int в двойной

На самом деле, у меня есть несколько взаимосвязанных вопросов. (Если это имеет значение, я использую C#.)

Первый. У меня есть prng, который генерирует случайные числа в диапазоне UInt32, от 0 до UInt32.Max включительно. Я хочу максимально сохранить единообразие. Какова основная идея получения [a,b], (a,b) двойных диапазонов (например, [0,1], [0,1), (0,1), [-2,4], (- 10,10))?

Меня беспокоит следующее. У меня есть 4 294 967 296 исходов prng. Чисел в двойном диапазоне [0,1] меньше — 2^53. Итак, я составляю 4 294 967 296-значное число из 2 цифр, которое является случайным и однородным в [0, 4294967295 * 4294967296 + 4294967295]. Это максимальное значение больше, чем 2 ^ 53 на 1, поэтому, если кто-то его получит, выбросьте его, пересчитайте, используйте мод 2 ^ 53 и получите универсальное число, например, [0,1]. Здесь я должен представить максимальное значение как double (пусть нет типа Int64) — есть ли в этом недостатки?

Теперь, если я хочу получить [0,1), я считаю, что количество результатов равно (2 ^ 53) - 1. Добавление к последнему результату 1/(2 ^ 53) даст случайное двойное число в (0,1] , Чтобы получить (0,1), я считаю (2 ^ 53) - 2 новых результата и добавляю 1/(2 ^ 53) к результату, основанному на 0. Все ли это правильно?

Но как получить двойные диапазоны, близкие или равные всему двойному диапазону? Даже если я создам n-арное число, как указано выше, оно может стать больше, чем Double.Max. Может быть, возможен какой-то подход с битовыми сдвигами/битовыми масками?

Второй. Теперь есть двойной prng с результатами в [0,1) возможно ли получить диапазон [Double.Min, Double.Max]? Сколько двойных чисел вообще? Если есть полный двойной диапазон prng, как лучше всего получить диапазон UInt — отобразить «напрямую» или масштабировать до [0,1] раньше?

В третьих. Я нашел этот код (http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/MT2002/CODES/mt19937ar.c):

 /* generates a random number on [0,1) with 53-bit resolution*/
 double genrand_res53(void) 
 { 
     unsigned long a=genrand_int32()>>5, b=genrand_int32()>>6; 
     return(a*67108864.0+b)*(1.0/9007199254740992.0); 
 }

Почему a и b сдвигаются на 5 и 6 и почему после этого a*67108864.0+b равномерна?

Спасибо.


random algorithm prng
person Yuri    schedule 29.03.2011    source источник

Ответы (1)


arrow_upward
1
arrow_downward

Хорошие генераторы случайных чисел производят случайные биты во всех позициях. Некоторые классы плохих дают плохую случайность в младших разрядах. Таким образом, если вам нужно 53 бита, а сгенерировать 64, вы хотите выбросить 11 младших битов — в случае кода, который вы опубликовали, 5 из одного числа и 6 из другого. Теперь у вас есть 26-битное число и 27-битное число; 2^26 — это 67108864, а 2^53 — это 9007199254740992, что должно объяснить, почему эти константы используются для масштабирования этих чисел до [0,1). (Это смешанное число: 67108864-ary для первой цифры и 134217728-ary для второй.)

(Причина, по которой 53 бита часто используются, заключается в том, что это делает числа симметричными при вычитании, иначе значения между 2^-53 и 2^-64 исчезнут, когда вы вычтете их из 1.)

Кроме того, вы не должны выполнять повторную выборку, когда у вас слишком много битов — просто выбросьте лишние биты (если у вас их меньше одного).

В любом случае, очевидный метод дает вам [0,1). Если вы хотите (0,1], то это 1 - [0,1]. Если вы хотите (0,1), повторите выборку, если вы получаете и a=0, и b=0. Если вы хотите [0,1], обратите внимание, что существует 1 из (2^53+1) шансов получить 1, иначе у вас есть [0,1). Вы можете аппроксимировать это, получив случайное число в [0,1) и проверив, равно ли оно нулю, и выбрав 1 в качестве ответа, если да, или снова выбрав из [0,1), если нет. Ваш генератор случайных чисел, вероятно, не имеет достаточно длительного периода, чтобы быть более точным.

person Rex Kerr    schedule 29.03.2011