Generating Random Numbers/pl: what changed
Revision 3 to 4. Removed lines have a minus sign; added lines have a plus sign.
| Old | New | Line | |
|---|---|---|---|
| 1 | - | ||
| 2 | - | ||
| 3 | - | ||
| 4 | - | ||
| 5 | - | ||
| 1 | + |  | |
| 6 | 2 | ||
| 7 | - | ||
| 3 | + | **Liczby losowe** są ważnymi zasobami do zastosowań naukowych, edukacji, tworzenia gier i wizualizacji. Odgrywają kluczową rolę w symulacji numerycznej. | |
| 8 | 4 | ||
| 9 | - | ||
| 5 | + | Liczby losowe generowane przez algorytm to liczby pseudolosowe. Należą do (dużego) zbioru powtarzających się liczb, których kolejność jest niemożliwa lub przynajmniej trudna do przewidzenia. W przeciwieństwie do Delphi, który używa liniowego generatora kongruencjalnego (patrz [[Delphi compatible LCG Random|LCG Random kompatybilny z Delphi]]), Free Pascal używa algorytmu MersenneTwister dla swojej standardowej funkcji losowej [[doc:rtl/system/random.html|random]] zdefiniowanej w RTL. Przed pierwszym użyciem generator liczb losowych FPC musi zostać zainicjowany pojedynczym wywołaniem funkcji [[doc:rtl/system/randomize.html|randomize]], która ustawia ziarno generatora. Najlepiej jest to zrobić w fazie uruchamiania programu. | |
| 10 | 6 | ||
| 11 | - | ||
| 7 | + | Alternatywnie w systemach opartych na systemach Unix i Linux dostępne są urządzenia wirtualne [[Dev random|/dev/random]] i `/dev/urandom`. Generują liczby (pseudo) losowe na podstawie sprzętu. | |
| 12 | 8 | ||
| 13 | - | ||
| 14 | - | ||
| 15 | - | ||
| 16 | - | ||
| 17 | - | ||
| 18 | - | ||
| 19 | - | ||
| 20 | - | ||
| 21 | - | ||
| 22 | - | ||
| 23 | - | ||
| 9 | + | Trzecią możliwością jest użycie liczb losowych ze źródeł zewnętrznych, albo ze specjalistycznych urządzeń sprzętowych, albo ze źródeł publicznych, np. na podstawie danych dotyczących rozpadu promieniotwórczego. | |
| 24 | 10 | ||
| 25 | 11 | ## Jednorodny rozkład | |
| 26 | 12 | ||
| 27 | - | ||
| 13 | + | Ciągły rozkład jednorodny (nazywany również rozkładem prostokątnym) reprezentuje rodzinę symetrycznych rozkładów prawdopodobieństwa. Tutaj dla każdego członka rodziny wszystkie przedziały tej samej długości na nośniku rozkładu są jednakowo prawdopodobne. | |
| 28 | 14 | ||
| 29 | - | ||
| 15 | + | Standardowa funkcja [[RTL]] [[doc:rtl/system/random.html|random]] generuje liczby losowe, które mają jednolity rozkład. Jeśli zostanie wywoływana bez parametru zwróci pseudolosową liczbę zmiennoprzecinkową w przedziale \[0, 1), tj. 0 \<= wynik \< 1. Jeśli random jest wywoływana z argumentem longint L, dostarcza losową liczbę zmiennoprzecinkową w przedziale \[0, L). | |
| 30 | 16 | ||
| 31 | - | ||
| 17 | + | Kolejny zestaw generatorów liczb losowych o równomiernym rozkładzie jest przedstawiony w [[Marsaglia&|generatorach liczb pseudolosowych Marsaglii]]. | |
| 32 | 18 | ||
| 33 | - | ||
| 19 | + | Jednolicie rozmieszczone liczby losowe nie są przydatne w żadnej aplikacji. Do tworzenia liczb losowych z innych rozkładów potrzebne są specjalne algorytmy: | |
| 34 | 20 | ||
| 35 | 21 | ## Normal (Gaussian) Distribution | |
| 36 | 22 | ||
| 37 | - | ||
| 38 | - | ||
| 39 | - | ||
| 40 | - | ||
| 41 | - | ||
| 42 | - | ||
| 43 | - | ||
| 44 | - | ||
| 45 | - | ||
| 46 | - | ||
| 47 | - | ||
| 48 | - | ||
| 23 | + | One of the more common algorithms to produce normally distributed random numbers from uniformly distributed random numbers is the [Box-Müller approach](http://en.wikipedia.org/wiki/Box–Muller_transform). The following function calculates Gaussian-distributed random numbers: | |
| 49 | 24 | ||
| 50 | - | ||
| 25 | + | ``` pascal | |
| 26 | + | function rnorm (mean, sd: real): real; | |
| 27 | + | {Calculates Gaussian random numbers according to the Box-Müller approach} | |
| 28 | + | var | |
| 29 | + | u1, u2: real; | |
| 30 | + | begin | |
| 31 | + | u1 := random; | |
| 32 | + | u2 := random; | |
| 33 | + | rnorm := mean * abs(1 + sqrt(-2 * (ln(u1))) * cos(2 * pi * u2) * sd); | |
| 34 | + | end; | |
| 51 | 35 | ``` | |
| 36 | + | ||
| 37 | + | The same algorithm is used by the [[doc:rtl/math/randg.html|randg]] randg function from the [[RTL]] [[doc:rtl/math/index.html|math]] unit: | |
| 38 | + | ||
| 39 | + | ``` pascal | |
| 52 | 40 | function randg(mean,stddev: float): float; | |
| 53 | 41 | ``` | |
| 54 | 42 | ||
| 55 | 43 | ## Exponential Distribution | |
| 56 | 44 | ||
| 57 | - | ||
| 45 | + | An exponential distribution occurs frequently in real-world problems. A classical example is the distribution of waiting times between independent Poisson-random events, e.g. the radioactive decay of nuclei \[Press et al. 1989\]. | |
| 58 | 46 | ||
| 59 | - | ||
| 60 | - | ||
| 47 | + | The following function delivers a single real random number out of an exponential distribution. *Rate* is the inverse of the mean, and the constant *RESOLUTION* determines the granularity of generated random numbers. | |
| 48 | + | ||
| 49 | + | ``` pascal | |
| 61 | 50 | function randomExp(a, rate: real): real; | |
| 62 | - | ||
| 63 | - | ||
| 64 | - | ||
| 65 | - | ||
| 66 | - | ||
| 67 | - | ||
| 68 | - | ||
| 69 | - | ||
| 70 | - | ||
| 71 | - | ||
| 72 | - | ||
| 73 | - | ||
| 74 | - | ||
| 75 | - | ||
| 76 | - | ||
| 51 | + | const | |
| 52 | + | RESOLUTION = 1000; | |
| 53 | + | var | |
| 54 | + | unif: real; | |
| 55 | + | begin | |
| 56 | + | if rate = 0 then | |
| 57 | + | randomExp := NaN | |
| 58 | + | else | |
| 59 | + | begin | |
| 60 | + | repeat | |
| 61 | + | unif := random(RESOLUTION) / RESOLUTION; | |
| 62 | + | until unif <> 0; | |
| 63 | + | randomExp := a - rate * ln(unif); | |
| 64 | + | end; | |
| 65 | + | end; | |
| 77 | 66 | ``` | |
| 78 | 67 | ||
| 79 | 68 | ## Gamma Distribution | |
| 80 | 69 | ||
| 81 | - | ||
| 70 | + | 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. | |
| 82 | 71 | ||
| 83 | - | ||
| 84 | - | ||
| 72 | + | 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. | |
| 73 | + | ||
| 74 | + | ``` pascal | |
| 85 | 75 | function randomGamma(a, b, c: real): real; | |
| 86 | - | ||
| 87 | - | ||
| 88 | - | ||
| 89 | - | ||
| 90 | - | ||
| 91 | - | ||
| 92 | - | ||
| 93 | - | ||
| 94 | - | ||
| 95 | - | ||
| 96 | - | ||
| 97 | - | ||
| 98 | - | ||
| 99 | - | ||
| 100 | - | ||
| 101 | - | ||
| 76 | + | const | |
| 77 | + | RESOLUTION = 1000; | |
| 78 | + | T = 4.5; | |
| 79 | + | D = 1 + ln(T); | |
| 80 | + | var | |
| 81 | + | unif: real; | |
| 82 | + | A2, B2, C2, Q, p, y: real; | |
| 83 | + | p1, p2, v, w, z: real; | |
| 84 | + | found: boolean; | |
| 85 | + | begin | |
| 86 | + | A2 := 1 / sqrt(2 * c - 1); | |
| 87 | + | B2 := c - ln(4); | |
| 88 | + | Q := c + 1 / A2; | |
| 89 | + | C2 := 1 + c / exp(1); | |
| 90 | + | found := False; | |
| 91 | + | if c < 1 then | |
| 92 | + | begin | |
| 93 | + | repeat | |
| 94 | + | repeat | |
| 95 | + | unif := random(RESOLUTION) / RESOLUTION; | |
| 96 | + | until unif > 0; | |
| 97 | + | p := C2 * unif; | |
| 98 | + | if p > 1 then | |
| 102 | 99 | begin | |
| 103 | 100 | repeat | |
| 104 | - | ||
| 105 | - | ||
| 106 | - | ||
| 107 | - | ||
| 108 | - | ||
| 109 | - | ||
| 110 | - | ||
| 111 | - | ||
| 112 | - | ||
| 113 | - | ||
| 114 | - | ||
| 115 | - | ||
| 116 | - | ||
| 117 | - | ||
| 118 | - | ||
| 119 | - | ||
| 120 | - | ||
| 121 | - | ||
| 122 | - | ||
| 123 | - | ||
| 124 | - | ||
| 125 | - | ||
| 126 | - | ||
| 127 | - | ||
| 128 | - | ||
| 129 | - | ||
| 130 | - | ||
| 131 | - | ||
| 132 | - | ||
| 133 | - | ||
| 134 | - | ||
| 101 | + | unif := random(RESOLUTION) / RESOLUTION; | |
| 102 | + | until unif > 0; | |
| 103 | + | y := -ln((C2 - p) / c); | |
| 104 | + | if unif <= power(y, c - 1) then | |
| 105 | + | begin | |
| 106 | + | randomGamma := a + b * y; | |
| 107 | + | found := True; | |
| 108 | + | end; | |
| 135 | 109 | end | |
| 136 | 110 | else | |
| 137 | 111 | begin | |
| 138 | - | ||
| 139 | - | ||
| 140 | - | ||
| 141 | - | ||
| 142 | - | ||
| 143 | - | ||
| 144 | - | ||
| 145 | - | ||
| 146 | - | ||
| 147 | - | ||
| 148 | - | ||
| 149 | - | ||
| 150 | - | ||
| 151 | - | ||
| 152 | - | ||
| 153 | - | ||
| 154 | - | ||
| 112 | + | y := power(p, 1 / c); | |
| 113 | + | if unif <= exp(-y) then | |
| 114 | + | begin | |
| 115 | + | randomGamma := a + b * y; | |
| 116 | + | found := True; | |
| 117 | + | end; | |
| 155 | 118 | end; | |
| 156 | - | ||
| 119 | + | until found; | |
| 120 | + | end | |
| 121 | + | else if c = 1 then | |
| 122 | + | { Gamma distribution becomes exponential distribution, if c = 1 } | |
| 123 | + | begin | |
| 124 | + | randomGamma := randomExp(a, b); | |
| 125 | + | end | |
| 126 | + | else | |
| 127 | + | begin | |
| 128 | + | repeat | |
| 129 | + | repeat | |
| 130 | + | p1 := random(RESOLUTION) / RESOLUTION; | |
| 131 | + | until p1 > 0; | |
| 132 | + | repeat | |
| 133 | + | p2 := random(RESOLUTION) / RESOLUTION; | |
| 134 | + | until p2 > 0; | |
| 135 | + | v := A2 * ln(p1 / (1 - p1)); | |
| 136 | + | y := c * exp(v); | |
| 137 | + | z := p1 * p1 * p2; | |
| 138 | + | w := B2 + Q * v - y; | |
| 139 | + | if (w + D - T * z >= 0) or (w >= ln(z)) then | |
| 140 | + | begin | |
| 141 | + | randomGamma := a + b * y; | |
| 142 | + | found := True; | |
| 143 | + | end; | |
| 144 | + | until found; | |
| 145 | + | end; | |
| 146 | + | end; | |
| 157 | 147 | ``` | |
| 158 | 148 | ||
| 159 | 149 | ## Erlang Distribution | |
| 160 | 150 | ||
| 161 | - | ||
| 162 | - | ||
| 163 | - | ||
| 164 | - | ||
| 165 | - | ||
| 166 | - | ||
| 167 | - | ||
| 168 | - | ||
| 151 | + | 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. | |
| 152 | + | ||
| 153 | + | ``` pascal | |
| 154 | + | function randomErlang(mean: real; k: integer): real; | |
| 155 | + | const | |
| 156 | + | RESOLUTION = 1000; | |
| 157 | + | var | |
| 158 | + | i: integer; | |
| 159 | + | unif, prod: real; | |
| 160 | + | begin | |
| 161 | + | if (mean <= 0) or (k < 1) then | |
| 162 | + | randomErlang := NaN | |
| 163 | + | else | |
| 164 | + | begin | |
| 165 | + | prod := 1; | |
| 166 | + | for i := 1 to k do | |
| 169 | 167 | begin | |
| 170 | - | ||
| 171 | - | ||
| 172 | - | ||
| 173 | - | ||
| 174 | - | ||
| 175 | - | ||
| 176 | - | ||
| 177 | - | ||
| 178 | - | ||
| 179 | - | ||
| 180 | - | ||
| 181 | - | ||
| 182 | - | ||
| 183 | - | ||
| 168 | + | repeat | |
| 169 | + | unif := random(RESOLUTION) / RESOLUTION; | |
| 170 | + | until unif <> 0; | |
| 171 | + | prod := prod * unif; | |
| 184 | 172 | end; | |
| 173 | + | randomErlang := -mean * ln(prod); | |
| 174 | + | end; | |
| 175 | + | end; | |
| 185 | 176 | ``` | |
| 186 | 177 | ||
| 187 | 178 | ## Poisson Distribution | |
| 188 | 179 | ||
| 189 | - | ||
| 190 | - | ||
| 180 | + | 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. | |
| 181 | + | ||
| 182 | + | ``` pascal | |
| 191 | 183 | function randomPoisson(mean: integer): integer; | |
| 192 | - | ||
| 193 | - | ||
| 194 | - | ||
| 195 | - | ||
| 196 | - | ||
| 197 | - | ||
| 198 | - | ||
| 199 | - | ||
| 200 | - | ||
| 201 | - | ||
| 202 | - | ||
| 203 | - | ||
| 204 | - | ||
| 205 | - | ||
| 206 | - | ||
| 207 | - | ||
| 208 | - | ||
| 209 | - | ||
| 184 | + | { Generator for Poisson distribution (Donald Knuth's algorithm) } | |
| 185 | + | const | |
| 186 | + | RESOLUTION = 1000; | |
| 187 | + | var | |
| 188 | + | k: integer; | |
| 189 | + | b, l: real; | |
| 190 | + | begin | |
| 191 | + | assert(mean > 0, 'mean < 1'); | |
| 192 | + | k := 0; | |
| 193 | + | b := 1; | |
| 194 | + | l := exp(-mean); | |
| 195 | + | while b > l do | |
| 196 | + | begin | |
| 197 | + | k := k + 1; | |
| 198 | + | b := b * random(RESOLUTION) / RESOLUTION; | |
| 199 | + | end; | |
| 200 | + | randomPoisson := k - 1; | |
| 201 | + | end; | |
| 210 | 202 | ``` | |
| 211 | 203 | ||
| 212 | 204 | ## t Distribution | |
| 213 | 205 | ||
| 214 | - | ||
| 206 | + | 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. | |
| 215 | 207 | ||
| 216 | - | ||
| 217 | - | ||
| 208 | + | The following algorithm depends on the [[RTL]] function [[doc:rtl/system/random.html|random]] and on the **randomChisq** function | |
| 209 | + | ||
| 210 | + | ``` pascal | |
| 218 | 211 | function randomT(df: integer): real; | |
| 219 | - | ||
| 220 | - | ||
| 221 | - | ||
| 222 | - | ||
| 223 | - | ||
| 224 | - | ||
| 225 | - | ||
| 226 | - | ||
| 212 | + | { Generator for Student's t distribution } | |
| 213 | + | begin | |
| 214 | + | if df < 1 then | |
| 215 | + | randomT := NaN | |
| 216 | + | else begin | |
| 217 | + | randomT := randg(0, 1) / sqrt(randomChisq(df) / df); | |
| 218 | + | end; | |
| 219 | + | end; | |
| 227 | 220 | ``` | |
| 228 | 221 | ||
| 229 | 222 | ## Chi Squared Distribution | |
| 230 | 223 | ||
| 231 | - | ||
| 232 | - | ||
| 224 | + | 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**. | |
| 225 | + | ||
| 226 | + | ``` pascal | |
| 233 | 227 | function randomChisq(df: integer): real; | |
| 234 | - | ||
| 235 | - | ||
| 236 | - | ||
| 237 | - | ||
| 238 | - | ||
| 239 | - | ||
| 228 | + | begin | |
| 229 | + | if df < 1 then | |
| 230 | + | randomChisq := NaN | |
| 231 | + | else | |
| 232 | + | randomChisq := randomGamma(0, 2, 0.5 * df); | |
| 233 | + | end; | |
| 240 | 234 | ``` | |
| 241 | 235 | ||
| 242 | 236 | ## F Distribution | |
| 243 | 237 | ||
| 244 | - | ||
| 245 | - | ||
| 238 | + | 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**. | |
| 239 | + | ||
| 240 | + | ``` pascal | |
| 246 | 241 | function randomF(v, w: integer): real; | |
| 247 | - | ||
| 248 | - | ||
| 249 | - | ||
| 250 | - | ||
| 251 | - | ||
| 252 | - | ||
| 242 | + | begin | |
| 243 | + | if (v < 1) or (w < 1) then | |
| 244 | + | randomF := NaN | |
| 245 | + | else | |
| 246 | + | randomF := randomChisq(v) / v / (randomChisq(w) / w); | |
| 247 | + | end; | |
| 253 | 248 | ``` | |
| 254 | 249 | ||
| 255 | 250 | ## See also | |
| 256 | 251 | ||
| 257 | - | ||
| 258 | - | ||
| 259 | - | ||
| 260 | - | ||
| 261 | - | ||
| 262 | - | ||
| 252 | + | - [[Dev random]] | |
| 253 | + | - [[Functions for descriptive statistics]] | |
| 254 | + | - [[Marsaglia&|Marsaglia's pseudo random number generators]] | |
| 255 | + | - [[A simple implementation of the Mersenne twister]] | |
| 256 | + | - [[Delphi compatible LCG Random]] | |
| 257 | + | - [[EverettRandom]] | |
| 263 | 258 | ||
| 264 | 259 | ## References | |
| 265 | 260 | ||
| 266 | - | ||
| 267 | - | ||
| 268 | - | ||
| 269 | - | ||
| 270 | - | ||
| 271 | - | ||
| 261 | + | 1. [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](http://projecteuclid.org/DPubS/Repository/1.0/Disseminate?view=body&id=pdf_1&handle=euclid.aoms/1177706645) | |
| 262 | + | 2. Dietrich, J. W. (2002). [Der Hypophysen-Schilddrüsen-Regelkreis](http://openlibrary.org/books/OL24586469M/Der_Hypophysen-Schilddrüsen-Regelkreis). Berlin, Germany: Logos-Verlag Berlin. ISBN 978-3-89722-850-4. OCLC 50451543. | |
| 263 | + | 3. Press, W. H., B. P. Flannery, S. A. Teukolsky, W. T. Vetterling (1989). [Numerical Recipes in Pascal](http://openlibrary.org/works/OL16807779W/). The Art of Scientific Computing, Cambridge University Press, ISBN 0-521-37516-9. | |
| 264 | + | 4. Richard Saucier, [Computer Generation of Statistical Distributions](http://ftp.arl.mil/random/random.pdf), ARL-TR-2168, US Army Research Laboratory, Aberdeen Proving Ground, MD, 21005-5068, March 2000. | |
| 265 | + | 5. R.U. Seydel, Generating Random Numbers with Specified Distributions. In: Tools for Computational Finance, Universitext, [DOI 10.1007/978-1-4471-2993-6_2](http://dx.doi.org/10.1007/978-1-4471-2993-6_2), © Springer-Verlag London Limited 2012 | |
| 266 | + | 6. Christian Walck, Hand-book on STATISTICAL DISTRIBUTIONS for experimentalists, Internal Report SUF–PFY/96–01, University of Stockholm 2007 | |
| 272 | 267 | ||
| 273 | 268 | --- | |
| 274 | - | ||
| 269 | + | *From the Free Pascal wiki, page "Generating Random Numbers/pl", as it stood on 2020-11-08 after a change by Slawek, out of the wiki's dump of 2024-05-26. Copyright stays with the author who wrote it, according to the old wiki's [[Licensing]] page. If you have concerns about this material, [message the admin](/wiki-contact).* |
