Библиотека генерации псевдослучайных чисел

lrnd32

Руководство пользователя

11.06.2007 Version v.02

М.В.Якобовский

Назначение

Функции библиотеки lrnd32 предназначены для вычисления элементов последовательности псевдослучайных целых чисел. Обеспечивается вычисление элементов с заданными номерами или быстрое вычисление расположенных подряд элементов, начиная с любого места последовательности. Длина периода последовательности равна . По умолчанию номер первого вычисляемого элемента последовательности равен 0. Номер вычисляемого элемента может быть произвольно изменен. В представленной сокращенной версии библиотеки этот номер может устанавливаться в пределах .

Метод генерации элементов последовательности

Для определения бит i-го псевдослучайного -разрядного числа используются коэффициенты полиномов , где , P -примитивный полином степени над полем двоичных чисел:

Этот метод эквивалентен подходу [1], основанному на использовании рекуррентных соотношений и аналогичен рассмотренным в [2] генераторам Фибоначчи. Эквивалентность следует из [3]. Для определения последовательно идущих степеней используется выражение . Для определения произвольного элемента последовательности используется схема бинарного умножения предварительно вычисленных полиномов вида P [4]. Специальный выбор полинома обеспечивает наличие не более чем отличных от нуля коэффициентов в каждом из полиномов , что значительно сокращает время вычислений. Смещение введено для пропуска начального фрагмента последовательности, содержащего значительное число нулевых элементов.

Литература

1. И.М.Соболь. Численные методы Монте-Карло. – М.: Наука, 1973.

2. Richard P. Brent, Uniform Random Number Generators for Supercomputers, Computer Sciences Laboratory; Australian National University Appeared in Proceedings Fifth Australian Supercomputer Conference (Melbourne, December 1992), 95-104. c 1992, 5ASC Organising Committee.

3. R. P. Brent, On the Periods of Generalized Fibonacci Recurrences, Technical Report TRCS -92-03, Computer Sciences Laboratory, ANU, March 1992.

4. Кнут Дональд Эрвин, искусство программирования, том.2. Получисленные алгоритмы, 3-е издание.: Пер с англ., : Уч пос - М.: Издательский дом <Вильямс>, 2001. - 832 с., ил.

Описание

#include <lrnd32.h>

unsigned long lrnd32(void);

void lrnd32set(unsigned int c1, unsigned int c0);

unsigned long lrnd32direct(unsigned int c1, unsigned int c0);

lrnd32()

Функция lrnd32() возвращает значение очередного элемента последовательности псевдослучайных 32х разрядных целых чисел из отрезка . Длина периода последовательности равна .

lrnd32set(c1,c0)

Вызов функции lrnd32set(c1,c0) устанавливает номер очередного вычисляемого функцией lrnd32()элемента последовательности, равным . Если функция lrnd32set(c1,c0) не вызывалась, то номер элемента, значение которого возвращает первый вызов функции lrnd32() равен 0.

lrnd32direct(c1,c0)

Функция lrnd32direct(c1,c0) возвращает значение элемента последовательности с номером . Последующий вызов функции lrnd32() вернет значение элемента с номером .

Замечания по использованию

Замечание 1

Вызов функции

r=lrnd32direct(c1,c0);

эквивалентен последовательности двух вызовов:

lrnd32set(c1,c0);

r=lrnd32();

Замечание 2

Время выполнения функции lrnd32 значительно меньше, чем время выполнения функций lrnd32direct или lrnd32set. При необходимости генерации набора псевдослучайных чисел, расположенных последовательно, целесообразно многократно использовать функцию lrnd32, установив предварительно, номер начального элемента с помощью lrnd32set.

Примеры использования

Пример № 1. Генерация фрагментов последовательности

#include "stdio.h"

#include "stdlib.h"

#include "lrnd32.h"

int main(int argc, char *argv[])

{

int i;

printf("---The same block -----\n");

// Вывести на печать первые 10 псевдослучайных чисел

for(i=0;i<10;i++)

printf("lrnd[%d]=%lu\n",i,lrnd32());

printf("\n");

// Вывести на печать псевдослучайные числа с номерами 5,6,7,8,9

// с помощью непосредственного указания их номеров

for(i=5;i<10;i++)

printf("lrnd[%d]=%lu\n",i,lrnd32direct(0,i));

printf("\n---The same block -----\n");

// Вывести на печать числа с номерами

// 5299989643717=1234*2^32+453 и

// 5299989643718=1234*2^32+454

lrnd32set(1234,453);

printf("lrnd(1234,453)=%lu\n",lrnd32());

printf("lrnd(1234,454)=%lu\n\n",lrnd32());

// Вывести на печать числа с номерами

// 5299989643717=1234*2^32+453 и

// 5299989643718=1234*2^32+454

printf("lrnd(1234,453)=%lu\n",lrnd32direct(1234,453));

printf("lrnd(1234,454)=%lu\n",lrnd32());

exit(0);

}

Результат выполнения:

---The same block -----

lrnd[0]=1665613936

lrnd[1]=3649307372

lrnd[2]=2045726113

lrnd[3]=300264059

lrnd[4]=2905346817

lrnd[5]=1690496981

lrnd[6]=325436826

lrnd[7]=3062689369

lrnd[8]=1816065497

lrnd[9]=3601173191

lrnd[5]=1690496981

lrnd[6]=325436826

lrnd[7]=3062689369

lrnd[8]=1816065497

lrnd[9]=3601173191

---The same block -----

lrnd(1234,453)=3214048692

lrnd(1234,454)=1229750481

lrnd(1234,453)=3214048692

lrnd(1234,454)=1229750481

Пример № 2. Генерация последовательности вещественных чисел, равномерно распределенных на отрезке

unsigned long r;

for(i=0;i<3;i++)

{

r=lrnd32();

printf("lrnd[%2d]=%11lu = %20.15f\n",

i,r,(double)r/(double)LRND32_MAX);

}

Результат выполнения:

lrnd[ 0]= 1665613936 = 0.387805964888028

lrnd[ 1]= 3649307372 = 0.849670584511401

lrnd[ 2]= 2045726113 = 0.476307727740218

Состав архива

Исходные файлы библиотеки lrnd32

bint.c

bint.h

prand.c

prand.h

lrnd32.c

Заголовочный файл, включаемый в программу пользователя:

lrnd32.h

Файл, содержащий пример использования

main.c

Файл, содержащий руководство пользователя

lrnd32_userman.rtf