Библиотека генерации
псевдослучайных чисел
lrnd32
Copyright © M.Iakobovski
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() вернет значение элемента с номером .
Вызов функции
r=lrnd32direct(c1,c0);
эквивалентен последовательности двух вызовов:
lrnd32set(c1,c0);
r=lrnd32();
Время выполнения функции lrnd32
значительно меньше, чем время выполнения функций lrnd32direct или lrnd32set. При необходимости генерации набора
псевдослучайных чисел, расположенных последовательно, целесообразно многократно
использовать функцию lrnd32, установив предварительно, номер начального элемента с помощью lrnd32set.
#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
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