Obsah / Utility / RANDOM / Náhodné číslo s danou maximální hodnotou
Zdrojový kód: INCLUDE\UTIL\RANDOM.INC, UTIL\RANDOM.ASM
Náhodné číslo s danou maximální hodnotou
Náhodná čísla s danou maximální hodnotou jsou obvykle počítána tak, že náhodně vygenerované číslo se vydělí požadovaným rozsahem hodnot a výsledek po dělení se použije jako náhodné číslo s danou maximální hodnotou (s číslem provedeme tedy operaci modulo). Tato metoda má však jednu velkou nectnost - nepravidelný výskyt rozložení pravděpodobnosti.
Představme si fiktivní situaci, kdy máme k dispozici lineární generátor s rozsahem hodnot 0 až 7. Provedli jsme 800 pokusů a každá z 8 hodnot byla vygenerována 100x. Z vygenerovaných čísel chceme vytvořit náhodná čísla s rozsahem hodnot 0 až 4 (tedy 5 hodnot). Případnou operaci s dělením si můžeme představit tak, jako bychom sloupec možných hodnot obtočili kolem trubky s šířkou rovnou děliteli (tj. od čísla opakovaně odečítáme dělitele, až se číslo dostane do požadovaných mezí). V tomto případě zůstane poslední otáčka neúplná a jak vidíme na obrázku, jednotlivá čísla nemají stejnou pravděpodobnost výskytu (čísla 0 až 2 mají mnohem větší četnost, 200x).
Náprava spočívá v jiné metodě generování náhodných čísel v intervalu. Náhodné číslo vygenerované lineárním generátorem náhody zkontrolujeme, zda spadá do požadovaného rozsahu a pokud neodpovídá, zahodíme ho a vygenerujeme nové číslo. Tím je zajištěno rovnoměrné rozložení četnosti čísel nezávisle na požadovaném rozsahu čísel.
Pro zvýšení efektivnosti generátoru náhody, aby nedocházelo při malých intervalech k příliš častému odhazování nevyhovujících čísel, je náhodné číslo nejdříve maskováno binární maskou tak, aby se maskované číslo rozsahem co nejvíce blížilo požadovanému rozsahu čísel. Náhodné číslo si i po zamaskování binární maskou zachovává lineární rozložení četnosti. Ke stanovení binární masky je s výhodou využita instrukce BSR, která umí rychle vyhledat pozici nejvyššího bitu čísla.
|
Funkce RandMaxByte vygeneruje náhodné číslo "bajt bez znaménka" s rozsahem 0 až dané maximum MAX (včetně nuly a maximální hodnoty), které funkci předáme v registru AL. Maximum může mít rozsah hodnot 0 až 255. Výsledné číslo obdržíme v registru AL.
Na začátku funkce nejdříve otestujeme případ, kdy je požadována maximální hodnota 0. V tom případě se funkce ukončí okamžitě, protože zadané maximum 0 je současně jediným možným generovaným číslem.
Funkce používá jako pracovní registry ECX a EDX, jejich obsahy jsou proto uchovány pomocí instrukcí PUSH/POP.
Před samotným generováním čísla se připraví maska maximální hodnoty. Do registru EDX se načte z registru AL maximální požadovaná hodnota čísla (instrukce MOVZX zaplní zbytek registru EDX nulami) a instrukcí BSR se vyhledá pozice nejvyššího bitu "1" v registru EDX. Nalezená bitová pozice se uloží do registru ECX.
Maximální požadovaná hodnota čísla se uchová do registru CH pro pozdější použití. Do registru DL se připraví hodnota 2 (tj. bit 1) a rotací doleva o zjištěný počet bitů a dekrementací výsledku se vygeneruje maska maximální hodnoty čísla. Například pro maximální hodnotu 15h (=21) bude pozice nejvyššího bitu 4, maximální hodnota pro masku bude 2<<4 = 2*10h = 20h (=32) a maska náhodného čísla bude 1Fh (=31).
Nyní se již může přistoupit ke generování náhodného čísla. Pomocí funkce RandByte se vygeneruje do registru AL náhodné číslo s rozsahem 0 až 255. Číslo se zamaskuje maskou z registru DL a výsledek se porovná s požadovaným maximem v registru CH. Je-li vygenerované číslo větší než požadované maximum, generování čísla se opakuje, jinak se funkce úspěšně ukončí.
|
Funkce RandMaxChar vygeneruje náhodné číslo "bajt se znaménkem" s rozsahem 0 až dané maximum MAX (včetně nuly a maximální hodnoty), které funkci předáme v registru AL. Maximum může mít rozsah hodnot -128 až +127. Výsledné číslo obdržíme v registru AL.
K vygenerování čísla se znaménkem využijeme funkci generování čísla bez znaménka. Je-li požadované maximum nezáporné (tj. kladná čísla a nula), použije se přímo funkce RandMaxByte. Je-li požadované maximum záporné, převede se nejdříve negací na kladné číslo, vygeneruje se náhodné kladné číslo pomocí RandMaxByte a výsledek se opět negací převede na záporné číslo.
|
Funkce RandMaxWord vygeneruje náhodné číslo "slovo bez znaménka" s rozsahem 0 až dané maximum MAX (včetně nuly a maximální hodnoty), které funkci předáme v registru AX. Maximum může mít rozsah hodnot 0 až 65535. Výsledné číslo obdržíme v registru AX.
Na začátku funkce nejdříve otestujeme případ, kdy je požadována maximální hodnota 0. V tom případě se funkce ukončí okamžitě, protože zadané maximum 0 je současně jediným možným generovaným číslem.
Funkce používá jako pracovní registry ECX a EDX, jejich obsahy jsou proto uchovány pomocí instrukcí PUSH/POP.
Před samotným generováním čísla se připraví maska maximální hodnoty. Instrukcí BSR se vyhledá pozice nejvyššího bitu "1" v registru AX. Nalezená bitová pozice se uloží do registru CX.
Do registru EDX se připraví hodnota 2 (tj. bit 1) a rotací doleva o zjištěný počet bitů a dekrementací výsledku se vygeneruje maska maximální hodnoty čísla. Například pro maximální hodnotu 3E7h (=999) bude pozice nejvyššího bitu 9, maximální hodnota pro masku bude 2<<9 = 2*200h = 400h (=1024) a maska náhodného čísla bude 3FFh (=1023).
Maximální požadovaná hodnota čísla se uchová do registru CX pro pozdější použití.
Nyní se již může přistoupit ke generování náhodného čísla. Pomocí funkce RandWord se vygeneruje do registru AX náhodné číslo s rozsahem 0 až 65535. Číslo se zamaskuje maskou z registru DX a výsledek se porovná s požadovaným maximem v registru CX. Je-li vygenerované číslo větší než požadované maximum, generování čísla se opakuje, jinak se funkce úspěšně ukončí.
|
Funkce RandMaxShort vygeneruje náhodné číslo "slovo se znaménkem" s rozsahem 0 až dané maximum MAX (včetně nuly a maximální hodnoty), které funkci předáme v registru AX. Maximum může mít rozsah hodnot -32768 až +32767. Výsledné číslo obdržíme v registru AX.
K vygenerování čísla se znaménkem využijeme funkci generování čísla bez znaménka. Je-li požadované maximum nezáporné (tj. kladná čísla a nula), použije se přímo funkce RandMaxWord. Je-li požadované maximum záporné, převede se nejdříve negací na kladné číslo, vygeneruje se náhodné kladné číslo pomocí RandMaxWord a výsledek se opět negací převede na záporné číslo.
|
Funkce RandMaxDWord vygeneruje náhodné číslo "dvojslovo bez znaménka" s rozsahem 0 až dané maximum MAX (včetně nuly a maximální hodnoty), které funkci předáme v registru EAX. Maximum může mít rozsah hodnot 0 až 0ffffffffh. Výsledné číslo obdržíme v registru EAX.
Na začátku funkce nejdříve otestujeme případ, kdy je požadována maximální hodnota 0. V tom případě se funkce ukončí okamžitě, protože zadané maximum 0 je současně jediným možným generovaným číslem.
Funkce používá jako pracovní registry ECX a EDX, jejich obsahy jsou proto uchovány pomocí instrukcí PUSH/POP.
Před samotným generováním čísla se připraví maska maximální hodnoty. Instrukcí BSR se vyhledá pozice nejvyššího bitu "1" v registru EAX. Nalezená bitová pozice se uloží do registru ECX.
Do registru EDX se připraví hodnota 2 (tj. bit 1) a rotací doleva o zjištěný počet bitů a dekrementací výsledku se vygeneruje maska maximální hodnoty čísla. Například pro maximální hodnotu 0F423Fh (=999999) bude pozice nejvyššího bitu 19, maximální hodnota pro masku bude 2<<19 = 2*80000h = 100000h (=1048576) a maska náhodného čísla bude 0FFFFFh (=1048575).
Maximální požadovaná hodnota čísla se uchová do registru ECX pro pozdější použití.
Nyní se již může přistoupit ke generování náhodného čísla. Pomocí funkce RandDWord se vygeneruje do registru EAX náhodné číslo s rozsahem 0 až 0ffffffffh, číslo se zamaskuje maskou z registru EDX a výsledek se porovná s požadovaným maximem v registru ECX. Je-li vygenerované číslo větší než požadované maximum, generování čísla se opakuje, jinak se funkce úspěšně ukončí.
|
Funkce RandMaxLong vygeneruje náhodné číslo "dvojslovo se znaménkem" s rozsahem 0 až dané maximum MAX (včetně nuly a maximální hodnoty), které funkci předáme v registru EAX. Maximum může mít rozsah hodnot -80000000h až +7fffffffh. Výsledné číslo obdržíme v registru EAX.
K vygenerování čísla se znaménkem využijeme funkci generování čísla bez znaménka. Je-li požadované maximum nezáporné (tj. kladná čísla a nula), použije se přímo funkce RandMaxDWord. Je-li požadované maximum záporné, převede se nejdříve negací na kladné číslo, vygeneruje se náhodné kladné číslo pomocí RandMaxDWord a výsledek se opět negací převede na záporné číslo.
|
Funkce RandMaxQWord vygeneruje náhodné číslo "čtyřslovo bez znaménka" s rozsahem 0 až dané maximum MAX (včetně nuly a maximální hodnoty), které funkci předáme v registrech EDX:EAX. Maximum může mít rozsah hodnot 0 až 0ffffffffffffffffh. Výsledné číslo obdržíme v registrech EDX:EAX.
Na začátku funkce nejdříve otestujeme případ, kdy je požadována maximální hodnota spadající do rozsahu dvojslova. Pokud je vyšší dvojslovo maxima rovno nule, předá se řízení funkci pro generování dvojslova v daném rozsahu (registr EDX si přitom uchová nulovou hodnotu).
Funkce používá jako pracovní registry EBX, ECX a ESI, jejich obsahy jsou proto uchovány pomocí instrukcí PUSH/POP.
Před samotným generováním čísla se připraví maska maximální hodnoty. Instrukcí BSR se vyhledá pozice nejvyššího bitu "1" v registru EDX, tedy ve vyšším dvojslovu maxima. Víme už z testu na začátku funkce, že obsah EDX je nenulový, proto nás nezajímá registr EAX s nižší hodnotou maxima. Nalezená bitová pozice se uloží do registru ECX.
Do registru EBX se připraví hodnota 2 (tj. bit 1) a rotací doleva o zjištěný počet bitů a dekrementací výsledku se vygeneruje maska maximální hodnoty čísla. Je to maska pouze pro vyšší dvojslovo generovaného čísla, protože víme, že generujeme rozsah čísel větší než je rozsah jednoho dvojslova.
Maximální požadovaná hodnota čísla se uchová do registrů ESI:ECX pro pozdější použití.
Nyní se již může přistoupit ke generování náhodného čísla. Pomocí funkce RandQWord se vygeneruje do registrů EDX:EAX náhodné číslo s rozsahem 0 až 0ffffffffffffffffh. Vyšší dvojslovo čísla se zamaskuje maskou z registru EBX a výsledek se porovná s požadovaným maximem v registrech ESI:ECX. Jedná se o porovnání dvou dvojslov a proto ho musíme provést ve dvou krocích - nejdříve porovnání vyššího dvojslova a pokud si jsou čísla rovna tak porovnání nižšího dvojslova. Je-li vygenerované číslo větší než požadované maximum, generování čísla se opakuje, jinak se funkce úspěšně ukončí.
|
Funkce RandMaxInt64 vygeneruje náhodné číslo "čtyřslovo se znaménkem" s rozsahem 0 až dané maximum MAX (včetně nuly a maximální hodnoty), které funkci předáme v registrech EDX:EAX. Maximum může mít rozsah hodnot -8000000000000000h až +7fffffffffffffffh. Výsledné číslo obdržíme v registrech EDX:EAX.
K vygenerování čísla se znaménkem využijeme funkci generování čísla bez znaménka. Je-li požadované maximum nezáporné (tj. kladná čísla a nula), použije se přímo funkce RandMaxQWord. Je-li požadované maximum záporné, převede se nejdříve negací na kladné číslo, vygeneruje se náhodné kladné číslo pomocí RandMaxQWord a výsledek se opět negací převede na záporné číslo.
Negaci čísla uloženého ve 2 registrech musíme provést ve více krocích. Negací registru EAX provedeme změnu znaménka nižšího dvojslova čísla. Pokud byl obsah registru EAX nulový, vynuluje se příznak CF. Byl-li obsah registru nenulový, příznak CF se nastaví. V případě nenulového registru se inkrementuje vyšší dvojslovo čísla (obsah registru EDX se inkrementuje přičtením 0 spolu s příznakem přenosu). Nakonec se provede negace vyššího dvojslova.
Vysvětlení pro uvedený postup výpočtu negace je následující: Instrukci negace si můžeme představit jako operaci "0 - číslo", tedy odečtení čísla od nuly. Je zřejmé, že k nastavení příznaku přenosu dojde vždy, když je číslo nenulové. Když bychom dělali negaci pomocí instrukcí pro odečítání, odečetli bychom nižší dvojslovo od nuly instrukcí SUB a vyšší dvojslovo instrukcí SBB, tedy odečetli bychom vyšší dvojslovo i příznak CF. To je stejná operace, jako když odečteme druhý operand s přičteným příznakem CF, příznak CF tedy můžeme přičíst k druhému operandu již před provedením operace.
|
Funkce RandMaxFloat vygeneruje náhodné číslo s daným maximem s přesností 10 číslic. Maximum je dáno na vstupu funkce v registru ST0 koprocesoru a může mít jak kladnou tak i zápornou hodnotu. Výsledek je navrácen opět v registru ST0. Protože funkce používá matematický koprocesor, je nutné pamatovat na uchování stavu koprocesoru v případě, že funkce je interně používána jádrem systému.
|
Funkce RandMaxDouble vygeneruje náhodné číslo s daným maximem s přesností 16 číslic. Maximum je dáno na vstupu funkce v registru ST0 koprocesoru a může mít jak kladnou tak i zápornou hodnotu. Výsledek je navrácen opět v registru ST0. Protože funkce používá matematický koprocesor, je nutné pamatovat na uchování stavu koprocesoru v případě, že funkce je interně používána jádrem systému.
Obsah / Utility / RANDOM / Náhodné číslo s danou maximální hodnotou
