A | B | C | D | E | F | G | H | CH | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
Lineární kongruentní generátor (anglicky Linear Congruential Generator, zkratka LCG) je jeden z nejstarších a nejjednodušších generátorů pseudonáhodných čísel.
Je definován vztahem:
- ,
kde operace mod znamená zbytek po celočíselném dělení, , a jsou vhodně zvolené konstanty. Počáteční nastavení se nazývá random seed („náhodné semínko“). Generátor generuje celá čísla s rovnoměrným rozložením v rozsahu . Poněvadž je počet možných hodnot v tomto rozsahu omezen, začne se nejpozději po vygenerovaných číslech opakovat stejná posloupnost (tzv. perioda generátoru). Generátor bude mít plnou periodu () právě tehdy, když:[1]
- a jsou nesoudělná čísla,
- je dělitelné všemi provočíselnými faktory ,
- je násobek 4, jestliže je násobek 4.
Větší problém, než je periodicita generátoru, lze u tohoto typu generátoru pozorovat při generování náhodných bodů v prostoru. V případě špatně zvolených hodnot , , leží vygenerované body v několika rovnoběžných rovinách, zatímco zbytek prostoru, který by měl být rovnoměrně zaplněn, je prázdný. Nechvalně se tak proslavil například generátor RANDU (, , , je liché číslo) používaný okolo roku 1970.
Příklady konstant:
zdroj | m | a | c | výstup |
---|---|---|---|---|
Numerical Recipes | 1 664 525 | 1 013 904 223 | ||
Borland C/C++ | 22 695 477 | 1 | bity 30–16 v rand(), 30–0 v lrand() | |
glibc (GCC) | 1 103 515 245 | 12 345 | bity 30–0 | |
ANSI C: Watcom, Digital Mars, CodeWarrior, IBM VisualAge C/C++ | 1 103 515 245 | 12 345 | bity 30–16 | |
Borland Delphi, Virtual Pascal | 134 775 813 | 1 | bity 63–32 ze (seed * L) | |
Microsoft Visual/Quick C/C++ | 214 013 | 2 531 011 | bity 30–16 | |
Apple CarbonLib (Park & Miller) | 16 807 | 0 |
Příklad v C
unsigned int x, a, c;
void Reset()
{
x = 0; // Random seed (náhodné semínko)
a = 69069;
c = 1;
}
unsigned int GenerateNext()
{
x = x*a + c;
return x;
}
Související články
Reference
- ↑ D. E. Knuth. The Art of Computer Programming, Volume 2: Seminumerical Algorithms, Third Edition. Addison-Wesley, 1997. ISBN 0-201-89684-2. str. 17–19.
Externí odkazy
- Zdrojové kódy LCG v různých programovacích jazycích
- Test generátoru pseudonáhodných čísel RANDU: http://tjn.fjfi.cvut.cz/~virius/prednes/mc-prikl/Randu.html
Text je dostupný za podmienok Creative Commons Attribution/Share-Alike License 3.0 Unported; prípadne za ďalších podmienok. Podrobnejšie informácie nájdete na stránke Podmienky použitia.
Antropológia
Aplikované vedy
Bibliometria
Dejiny vedy
Encyklopédie
Filozofia vedy
Forenzné vedy
Humanitné vedy
Knižničná veda
Kryogenika
Kryptológia
Kulturológia
Literárna veda
Medzidisciplinárne oblasti
Metódy kvantitatívnej analýzy
Metavedy
Metodika
Text je dostupný za podmienok Creative
Commons Attribution/Share-Alike License 3.0 Unported; prípadne za ďalších
podmienok.
Podrobnejšie informácie nájdete na stránke Podmienky
použitia.
www.astronomia.sk | www.biologia.sk | www.botanika.sk | www.dejiny.sk | www.economy.sk | www.elektrotechnika.sk | www.estetika.sk | www.farmakologia.sk | www.filozofia.sk | Fyzika | www.futurologia.sk | www.genetika.sk | www.chemia.sk | www.lingvistika.sk | www.politologia.sk | www.psychologia.sk | www.sexuologia.sk | www.sociologia.sk | www.veda.sk I www.zoologia.sk