LINEÁRNÍ KONGRUENČNÍ GENERÁTOR

PROBLÉM
Generovat pseudonáhodná čísla ze zadaného intervalu. V standardním Rexxu můžeme užít vestavěnou funkci RANDOM, která vrací pseudonáhodné celé číslo z intervalu [Min,Max], kde Min>=0. V konkrétní implementaci, např. Regina, musí být Max<=100000.

ALGORITMUS
Standardní postup pro generování pseudonáhodných čísel je použít lineární kongruenční metodu, kterou porpvé uvedl v roce 1948 D. H. Lehmer. Při ní jsou členy posloupnosti určeny rekurentním vztahem

Im1=I-1;X.I=(X.Im1*A+C)//M

kde konstanty A, C, a M určují statistickou kvalitu generátoru. Mají-li A a M společného dělitele většího než jedna, a nejsou tedy nesoudělná, pak generovaná posloupnost čísel pravděpodobně nebude příliš náhodná.

Volba A=16807, C=0 a M=2**31-1 (M=2147483647) definuje generátor, který má úplnou periodu a výsledná posloupnost dostatečně věrně realizuje rovnoměrnou náhodnou posloupnost čísel z intervalu 1,2,...,M-1. Byl testován mnohonásobným a dlouholetým používáním v praxi. 16807 a 2**31-1 jsou nesoudělná čísla,

NSD(16807,2**31-1)=1.

IMPLEMENTACE
Jednotka: vnitřní funkce nebo vnější, ale pak bez procedure příkazu
 
Parametr: X z intervalu 1M-1
 
Vrací: pseudonáhodné číslo z intervalu 1M-1

 

LCG: procedure
parse arg X
numeric digits 14
A = 16807; M = 2147483647
return A * X // M

 

PŘÍKLAD POUŽITÍ
Viz Technika: Testovací data

SOUVISLOSTI

Literatura
Knuth D. E. Seminumerical Algorithms, vol. 2 of The Art of Computer Programming
Addison-Wesley, 1973
Park S. K., Miller K. W. Random Number Generators: Good ones are hard to find
CACM October 1988 Vol. 31 No. 10, pp. 1192-1201


Obálka Obsah Index Hlavní stránka

změněno 1. srpna 2001
Copyright © 2000-2001 Vladimír Zábrodský, RNDr.