7.7. Быстрый генератор для 32-битового представления целых и действительных чисел

В большинстве случаев, число типа unsigned long имеет 32 бита. В этом случае для генерации числа в диапазоне 0 - 2³²-1 достаточно простого умножения на мультипликатор и сложения с инкрементом. Деление по модулю будет произведено автоматически при переполнении. Значения мультипликатора и инкремента для этого случая получены в исследованиях D. Knuth и H.W. Lewis.

/* генерация целого числа от 0 до 0xFFFFFFFF. */

static unsigned long iran;

...........

iran=1664525L*iran+1013904223L;

Для реализации на этой основе очень быстрого генератора равномерного распределения действительных чисел от 0 до 1 важно, что floating-point single precision numbers (тип float) в большинстве случаев представлены также 32 битами. Кроме того, во многих случаях (включая SUN, ALPHA, Silicon Graphics и IBM PC) представление этого числа отвечает одному стандарту IEEE. Для машины VAX это не так.

Грязным трюком, позволяющим избегнуть деления на действительное число, является маскировка экспоненты и дальнейшее вычитание из числа единицы. Необходимые коэффициенты в программе приведены для IEEE (по умолчанию) и для VAX.

static unsigned long iran;

unsigned long temp;

float fran;

..........

#if !defined(VAX)

static unsigned long jflone=0x3f800000;

static unsigned long jflmsk=0x007fffff;

#else

static unsigned long jflone=0x00004080;

static unsigned long jflmsk=0xffff007f;

#endif

..........

iran=1664525L*iran+1013904223L;

temp=jflone|(jflmsk&iran);

fran=(*(float *)&temp)-1.F;

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

7.8. Алгоритм л'Экюера, комбинирующий две последовательности

В генераторе Парка-Миллера мы находили последовательность так:

I(j+1)=a*I(j)(modm)

где a и m - особым образом выбранные константы.

Прямое приложение этого метода возможно на языках ассемблера, но языки высокого уровня могут при этом зафиксировать переполнение. Для обхода этого Scharge предложил метод частичной факторизации модуля. Модуль разлагается в выражение:

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.

Если требуется число вызовов, превышающее по порядку 10⁸, то для этого случая L'Ecuyer рекомендует комбинировать вывод двух последовательностей с близкими, но отличающимися константами. В его исследованиях хороший результат был получен для значений:

m1=2147483563, a1=40014, q1=53668, r1=12211; m2=2147483399, a2=40692, q2=52774, r2=3791.

При этом для современных компьютеров период генерируемой последовательности становится недостижимым (длина оценивается по порядку как 10¹⁸).

/* L'Ecuyer algorithm for uniform random generator

with practically endless period. Combining 2 sequences. */

/* previous constants, static variables and functions are valid as if

the programs on this page are determined in one module */

#define IM1 2147483563

#define IM2 2147483399

#undef AM

#define AM (1./IM1)

#define IMM1 (IM1-1)

#define IA1 40014

#define IA2 40692

#define IQ1 53668

#define IQ2 52774

#define IR1 12211

#define IR2 3791

#undef NDIV

#define NDIV (1+IMM1/NTAB)

float unirand2(void) {

int j;

long k;

static long dummy2=123456789;

static long iy=0;

static long iv[NTAB];

float temp;

/* initialize the random sequence (first set of coefficients, the

routine close to that in the function above */

if(dummy<=0 || !iy) {

/* avoid negative or zero seed */

if(dummy<0) dummy=-dummy;

else if(dummy==0) dummy=1;

dummy2=dummy;

/* after NWUP warmups, initialize shuffle table */

for(j=NTAB+NWUP-1;j>=0;j--) {

k=dummy/IQ1;

if((dummy=IA1*(dummy-k*IQ1)-IR1*k)<0) dummy+=IM1;

if(j<NTAB) iv[j]=dummy;

}

/* first specimen from the table */

iy=iv[0];

}

/* regular work: generate 2 sequences. */

k=dummy/IQ1;

if((dummy=IA1*(dummy-k*IQ1)-IR1*k)<0) dummy+=IM1;

k=dummy2/IQ2;

if((dummy2=IA2*(dummy2-k*IQ2)-IR2*k)<0) dummy2+=IM2;

/* shuffle output combining 2 sequences */

iy=iv[j=iy/NDIV]-dummy2;iv[j]=dummy;

if(iy<1) iy+=IMM1;

/* return the result, as in the previous function */

if((temp=AM*iy)>RNMX) return(RNMX);

elsereturn(temp);

}

ЗАКЛЮЧЕНИЕ

В учебном пособии по дисциплинам «Методы программирования» и «Средства и методы программирования» рассмотрены вопросы построения эффективных алгоритмов и программ их реализации, включающие:

• оценку сложности алгоритмов;

• построение линейных структур данных;

• сортировку и слияние;

• поиск;

• рекурсию;

• алгоритмы на графах;

• генераторы случайных и псевдослучайных последовательностей.

БИБЛИОГРАФИЧЕСКИЙ СПИСОК

1. Ахо А., Хопкрофт ДЖ. Построение и анализ вычислительных алгоритмов. - М; Мир, 1979. - 536 с.

2. Кнут Д. Искусство программирования для ЭВМ. т.1,2,3, Сортировка и поиск. - М.: Мир,.

3. Кормен. Т., Леверсон Ч., Ртвест Р. Алгоритмы. Построение и анализ.-М.; МЦНМО, 1999, 960 с.

4. Грехем Р., Кнут Д., Поиашник О. Конкретная математика.М.. Мир.,1998, 702 с.

5. Кнут Д. Искусство программирования для ЭВМ. т.3, Сортировка и поиск. - М.: Мир, 1978, ,848с.

6. Мейер Б., Бодуэн К. Методы программирования. т.1, - М.; Мир, 1982г. 362с.

7. Рейнгольд Э., Нивергелд Ю., Део Н.. Комбинаторные алгоритмы. Теория и практика, М., Мир., 1980г., 480с.

8. Нивергельд Ю., Рейнголд Э., Фаррар Дж. Машинный подход к решению математических задач. М. Мир. 1977, 351с.

9. Вирт Н. Алгоритмы и структуры данных. 2-е изд. –СПб.: Невский Диалект. –2001.-352 с.

10. Ахо А., Хопкрофт ДЖ. Структуры данных и алгоритмы. Уч. Пособие. – М.:Вильямс, 2000. – 384 с.

11. Топп У. Форд У. Структуры данных в С++. Пер. с англ. – М.: БИНОМ 2000. – 816 с.

12. Мейер Б., Бодуэн К. Методы программирования. Т.1. – М.: Мир, 1982г. 362 с.

13. Шень А. Программирование: теоремы и задачи. Уч. Пособие. – М.: МЦНМО, 1995. – 263 с.

14. Седжвик. Р. Фундаментальные алгоритмы на С++. Части 1-4. Анализ, структуры данных, сортировка, поиск. – М.: Диасофт, 2001. 687 с.