:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте ::
Путь: Математика » Псевдослучайные последовательности » Быстрый машинозависимый генератор
  Самый быстрый генератор для 32-битового представления целых и действительных чисел



Статья предоставлена
(c) Nikitine Valeri F. 2000,
web: algorithm.narod.ru

В большинстве случаев, число типа unsigned long имеет 32 бита. В этом случае для генерации числа в диапазоне 0 - 232-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;

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