Компактные генераторы равномерного распределения случайных чисел
Страница 2. Минимальный генератор Парка-Миллера
Страница 2 из 4
 

Минимальный генератор Парка-Миллера

Наиболее простая последовательность, которую можно предложить для реализации генератора равномерного распределения:
I(j+1)=a*I(j)(mod m)
при соответствующем выборе констант. Константы были предложены Парком и Миллером:
a=75=16807, m=231-1=2147483647
и протестированы в исследованиях Льюисом, Гудманом и Миллером (1969).

Реализация этого метода возможна на языках ассемблера, но языки высокого уровня могут зафиксировать переполнение. Для обхода этого Шарж предложил метод частичной факторизации модуля. Модуль разлагается в следующее выражение:
m=a*q+r
Если r<q и 0<z<m-1, то при этом величины a*(z mod q) и r*[z/q] всегда лежат в интервале 0,...,m-1. Для умножения (a*z)(mod m) при этом используется алгоритм:

  • t = a(z mod q)-r[z/q]
  • если t<0, то t += m.
  • (a*z)(mod m)=t.

В случае констант Парка-Миллера можно использовать q=12773 и r=2836.

/* Минимальный компактный генератор случайных чисел Парка и Миллера */

/* константы Льюиса-Гудмана-Миллера */
#define IA 16807
#define IM 2147483647
#define AM (1./IM)
/* константы Шаржа */
#define IQ 12773
#define IR 2836
/* Специальная маска (см. ниже) */
#define MASK 123456789

static long dummy;

/* начальное значение для всех генераторов */
void Seed(long dum) {dummy=dum;}

/* возвращает случайное число на промежутке от 0 до 1 */
float unirand0(void) {
 long k;
 float ans;
 dummy^=MASK;/* избегаем dummy==0 */
 k=dummy/IQ;
 if((dummy=IA*(dummy-k*IQ)-IR*k)<0) dummy+=IM;
 ans=AM*dummy;
 dummy^=MASK;/* восстанавливаем dummy */
 return(ans);
}

Использование маски вызвано тем, что специфика алгоритма не позволяет устанавливать счетчик в нуль. Но, как показывает опыт, большинство пользователей счетчиков делают именно так. Маска гарантирует, что установленный счетчик не будет нулем. Если вы очень уверены в том, что человек не допустит подобной ошибки после вашего предупреждения, то можете убрать из программы все инструкции, связанные с маской.
 
« Предыдущая статья   Следующая статья »