Generating Random Numbers/ru
│
Deutsch (de) │
English (en) │
suomi (fi) │
français (fr) │
polski (pl) │
русский (ru) │
Случайные числа являются важными ресурсами для научных приложений, образования, разработки игр и визуализации. Они играют ключевую роль в численном моделировании.
Генерируемые алгоритмом случайные числа являются псевдослучайными числами. Они принадлежат (большому) набору повторяющихся чисел, последовательность которых невозможно или, по крайней мере, трудно предсказать. В отличие от Delphi, в котором используется линейный конгруэнтный генератор (см. Delphi compatible LCG Random), Free Pascal использует алгоритм MersenneTwister для своей стандартной random
функции, определенной в RTL. Перед первым использованием генератор случайных чисел FPC должен быть проинициализирован единичным вызовом функции randomize
, которая устанавливает начальное число генератора. Предпочтительнее это делать на этапе запуска программы.
Кроме того, в системах на основе Unix и Linux доступны виртуальные устройства /dev/random
и /dev/urandom
. Они генерируют (псевдо) случайные числа на основе оборудования.
Третий вариант - использовать случайные числа из внешних источников, либо из специализированных аппаратных устройств, либо из общедоступных источников, например. на основе данных радиоактивного распада.
Равномерное распределение
Непрерывное равномерное распределение (также называемое прямоугольным распределением) представляет собой семейство симметричных вероятностных распределений. Здесь для каждого члена семьи все интервалы одинаковой длины в поддержке распределения одинаково вероятны.
Стандартная функция RTL random
генерирует случайные числа с равномерным распределением. При вызове без параметра random
выдает псевдослучайное число с плавающей запятой в интервале [0, 1), т.е. 0 <= result < 1. Если random
вызывается с аргументом longint L, возвращается случайное значение longint в интервале [0, L).
Дополнительный набор равномерно распределенных генераторов случайных чисел представлен в генераторах псевдослучайных чисел Марсальи.
Равномерно распределенные случайные числа полезны не для каждого приложения. Для создания случайных чисел других распределений необходимы специальные алгоритмы.
Нормальное (гауссово) распределение
Одним из наиболее распространенных алгоритмов получения нормально распределенных случайных чисел из равномерно распределенных случайных чисел является преобразование Бокса-Мюллера. Следующая функция вычисляет распределенные по Гауссу случайные числа:
function rnorm (mean, sd: real): real;
{Вычисляет гауссовы случайные числа в соответствии с преобразованием Бокса-Мюллера}
var
u1, u2: real;
begin
u1 := random;
u2 := random;
rnorm := mean * abs(1 + sqrt(-2 * (ln(u1))) * cos(2 * pi * u2) * sd);
end;
Тот же алгоритм используется функцией randg randg из модуля RTL math:
function randg(mean,stddev: float): float;
Экспоненциальное распределение
Экспоненциальное распределение часто встречается в реальных задачах. Классическим примером является распределение времени ожидания между независимыми пуассоновскими случайными событиями, например, радиоактивный распад ядер [Press et al. 1989].
Следующая функция возвращает одно действительное случайное число из экспоненциального распределения. Rate является обратным к среднему значению, а константа RESOLUTION определяет гранулярность генерируемых случайных чисел.
function randomExp(a, rate: real): real;
const
RESOLUTION = 1000;
var
unif: real;
begin
if rate = 0 then
randomExp := NaN
else
begin
repeat
unif := random(RESOLUTION) / RESOLUTION;
until unif <> 0;
randomExp := a - rate * ln(unif);
end;
end;
Gamma Distribution
The gamma distribution is a two-parameter family of continuous random distributions. It is a generalization of both the exponential distribution and the Erlang distribution. Possible applications of the gamma distribution include modelling and simulation of waiting lines, or queues, and actuarial science.
The following function delivers a single real random number out of a gamma distribution. The shape of the distribution is defined by the parameters a, b and c. The function makes use of the function randomExp as defined above.
function randomGamma(a, b, c: real): real;
const
RESOLUTION = 1000;
T = 4.5;
D = 1 + ln(T);
var
unif: real;
A2, B2, C2, Q, p, y: real;
p1, p2, v, w, z: real;
found: boolean;
begin
A2 := 1 / sqrt(2 * c - 1);
B2 := c - ln(4);
Q := c + 1 / A2;
C2 := 1 + c / exp(1);
found := False;
if c < 1 then
begin
repeat
repeat
unif := random(RESOLUTION) / RESOLUTION;
until unif > 0;
p := C2 * unif;
if p > 1 then
begin
repeat
unif := random(RESOLUTION) / RESOLUTION;
until unif > 0;
y := -ln((C2 - p) / c);
if unif <= power(y, c - 1) then
begin
randomGamma := a + b * y;
found := True;
end;
end
else
begin
y := power(p, 1 / c);
if unif <= exp(-y) then
begin
randomGamma := a + b * y;
found := True;
end;
end;
until found;
end
else if c = 1 then
{ Gamma distribution becomes exponential distribution, if c = 1 }
begin
randomGamma := randomExp(a, b);
end
else
begin
repeat
repeat
p1 := random(RESOLUTION) / RESOLUTION;
until p1 > 0;
repeat
p2 := random(RESOLUTION) / RESOLUTION;
until p2 > 0;
v := A2 * ln(p1 / (1 - p1));
y := c * exp(v);
z := p1 * p1 * p2;
w := B2 + Q * v - y;
if (w + D - T * z >= 0) or (w >= ln(z)) then
begin
randomGamma := a + b * y;
found := True;
end;
until found;
end;
end;
Erlang Distribution
The Erlang distribution is a two parameter family of continuous probability distributions. It is a generalization of the exponential distribution and a special case of the gamma distribution, where c is an integer. The Erlang distribution has been first described by Agner Krarup Erlang in order to model the time interval between telephone calls. It is used for queuing theory and for simulating waiting lines.
function randomErlang(mean: real; k: integer): real;
const
RESOLUTION = 1000;
var
i: integer;
unif, prod: real;
begin
if (mean <= 0) or (k < 1) then
randomErlang := NaN
else
begin
prod := 1;
for i := 1 to k do
begin
repeat
unif := random(RESOLUTION) / RESOLUTION;
until unif <> 0;
prod := prod * unif;
end;
randomErlang := -mean * ln(prod);
end;
end;
Poisson Distribution
The Poisson distribution applies to integer values. It represents the probability of k successes, when the probability of a success in each trial is small and the rate of occurrence (the mean value) is constant.
function randomPoisson(mean: integer): integer;
{ Generator for Poisson distribution (Donald Knuth's algorithm) }
const
RESOLUTION = 1000;
var
k: integer;
b, l: real;
begin
assert(mean > 0, 'mean < 1');
k := 0;
b := 1;
l := exp(-mean);
while b > l do
begin
k := k + 1;
b := b * random(RESOLUTION) / RESOLUTION;
end;
randomPoisson := k - 1;
end;
t Distribution
The t distribution (also referred to a Student's t distribution, since it was published by William Sealy Gosset in 1908 under the pseudonym Student) is a continuous probability distribution. Its shape is defined by one parameter, the degrees of freedom (df). In statistics, many estimators are t distributed. Therefore, Student's t-distribution plays a major role in a number of widely used statistical analyses, including Student's t-test for assessing the statistical significance of the difference between two sample means, the construction of confidence intervals for the difference between two population means, and in linear regression analysis. The t-distribution also arises in Bayesian analysis of data from a normal family.
The following algorithm depends on the RTL function random
and on the randomChisq function
function randomT(df: integer): real;
{ Generator for Student's t distribution }
begin
if df < 1 then
randomT := NaN
else begin
randomT := randg(0, 1) / sqrt(randomChisq(df) / df);
end;
end;
Chi Squared Distribution
The chi squared distribution is a continuous distribution of random numbers with df degrees of freedom. It is the distribution of a sum of the squares of df independent standard normal random variables. The chi squared distribution has numerous applications in inferential statistics, e.g. in estimating variances and for chi-squared tests. It is a special gamma distribution with c = df/ 2 and b = 2. Therefore the following function depends on the function randomGamma.
function randomChisq(df: integer): real;
begin
if df < 1 then
randomChisq := NaN
else
randomChisq := randomGamma(0, 2, 0.5 * df);
end;
F Distribution
The F distribution, also referred to as Fisher-Snedecor distribution, is a continuous probability distribution. It is used for F Test and ANOVA. It has two degrees of freedom that serve as shape parameters v and w and that are positive integers. The following function randomF makes use of randomChisq.
function randomF(v, w: integer): real;
begin
if (v < 1) or (w < 1) then
randomF := NaN
else
randomF := randomChisq(v) / v / (randomChisq(w) / w);
end;
See also
- Dev random
- Functions for descriptive statistics
- Marsaglia's pseudo random number generators
- A simple implementation of the Mersenne twister
- Delphi compatible LCG Random
References
- G. E. P. Box and Mervin E. Muller, A Note on the Generation of Random Normal Deviates, The Annals of Mathematical Statistics (1958), Vol. 29, No. 2 pp. 610–611
- Dietrich, J. W. (2002). Der Hypophysen-Schilddrüsen-Regelkreis. Berlin, Germany: Logos-Verlag Berlin. ISBN 978-3-89722-850-4. OCLC 50451543.
- Press, W. H., B. P. Flannery, S. A. Teukolsky, W. T. Vetterling (1989). Numerical Recipes in Pascal. The Art of Scientific Computing, Cambridge University Press, ISBN 0-521-37516-9.
- Richard Saucier, Computer Generation of Statistical Distributions, ARL-TR-2168, US Army Research Laboratory, Aberdeen Proving Ground, MD, 21005-5068, March 2000.
- R.U. Seydel, Generating Random Numbers with Specified Distributions. In: Tools for Computational Finance, Universitext, DOI 10.1007/978-1-4471-2993-6_2, © Springer-Verlag London Limited 2012
- Christian Walck, Hand-book on STATISTICAL DISTRIBUTIONS for experimentalists, Internal Report SUF–PFY/96–01, University of Stockholm 2007