Generování celočíselných pseudonáhodných posloupností maximální délky

Věci se nedějí náhodně. Vždy se dějí cíleně, někdy však pod rouškou pseudonáhodného výběrového mechanismu. Ono se hodí, když se náhoda opakuje stále ve stejném rytmu. Minimálně programátoři to ocení při ladění svých výtvorů.

Takže co budeme řešit. Mějme registr délky N bitů, ve kterém lze zakódovat 2^N různých stavů, interpretovaných čísly 0 až (2^N)-1. A my chceme vygenerovat všechna tato čísla právě jednou, ovšem v náhodném pořadí.

Na konkrétní počítačové platformě si můžeme pomáhat čtením nějakého rychlého hardwarového čítače, registru rozkladu obrazu, stavového registru různých periferních obvodů ale vystavujeme se riziku, že rychlost změn v těchto registrech bude synchronní s během našeho programu a budeme dostávat (v lepším případě) omezený počet hodnot z celého dostupného rozsahu.

A tím se dostáváme i k další vlastnosti generátoru pseudonáhodných čísel. Neměl by v libovolně vybraném úseku zvýhodňovat určitý typ hodnot. Neměl by generovat příliš dlouhé úseky sudých či lichých čísel, čísel větších či menších než 32768, atp. Každou matematickou podmínku, kterou si dovedete u daného čísla představit, by měl náš algoritmus pravidelně střídat ve stylu splňuje – nesplňuje.

Většinou asi v praxi vystačíme se základním osmibitovým generátorem pseudonáhodné posloupnosti. Ten který uvádím, funguje na bázi LFSR s externí zpětnou vazbou. LFSR je lineární zpětnovazební sériový registr, který nahradíme registrem A u osmibitového generátoru a registrovým párem H:L u šestnáctibitového generátoru. Ta poznámka o externí zpětné vazbě je velmi důležitá. Znamená to, že jednotlivé bity v posuvném registru jsou na sebe navázány přímo a nejsou mezi nimi žádné bloky, generující nějakou funkci. Ta zpětnovazební funkce se generuje „externě“ z jednotlivých bitů a výsledek této funkce se nasouvá v našem případě zprava do posuvného registru na jeho nejnižší pozici. Protože ta zpětnovazební funkce má na vstupu bity (dvoustavové logické hodnoty), a sčítání bitů modulo 2 (tedy s odřezáním všech řádů mimo jednotek) není nic jiného než výpočet parity, transformuje se výpočet zpětnovazební funkce na výpočet parity nad vybranými bity předchozí hodnoty generovaného čísla. Co jsem asi ještě neřekl, že nově vygenerované číslo vznikne ze starého tím, že posunu registr s tímto číslem doleva (násobím jeho hodnotu dvěma) a zprava nasunu bit s hodnotou zpětnovazební funkce. Dost bylo řečí, tady je příklad:

Procedura random8

Pseudonáhodné generátory tohoto typu mají jednu nectnost. Generovaná číselná řada neobsahuje prvek se samými jedničkami. Například osmibitový generátor nevygeneruje číslo 255 (11111111 binárně). Sice můžeme negovat zpětnovazební funkci a pak dostaneme i tento poslední prvek ale zase se nám ztratí prvek nulový. Máme na výběr. V našem příkladu tak stačí zaměnit instrukci JPO za instrukci JPE. Ale i to má řešení. U generátoru, který „neumí“ nulu si na začátku nastavíme explicitně jako první generované číslo právě tuto nulu a při prvním průchodu generátorem podvrhneme „falešnou“ hodnotu zpětnovazební funkce, která už algoritmus navede do správných kolejí a on nám vygeneruje zbylá čísla, například 1..255. Tak jsem to řešil u svého simulátoru EPROM, takže to jde a je to odzkoušené.

Pro případ, že nám je 8 bitů málo, můžeme použít i pseudonáhodný generátor délky 16 bitů:

Procedura random16

Opět platí, že v základní variantě negeneruje prvek 65535 (1111 1111 1111 1111 binárně). Tato šestnáctibitová varianta je v dále uvedeném příkladu rozpracována do dílčích podvariant délky 9 až 15 bitů, protože musíme vždy ořezat nevyužívané bity registru shora.

Následující program obsahuje testovací demo smyčku, která postupně spouští generátory pseudonáhodných čísel délky 8 až 16 bitů. Pro každou generovanou posloupnost se zobrazuje pixelové pole. Z časoprostorové distribuce pixelů si můžete udělat obrázek, jak dalece jsou ty generátory náhodné. Třeba u délky 15 bitů je pěkně vidět zvýrazněné „osy“, generované v úvodní fázi posloupnosti. Ale můžete si zvolit i jiné zpětnovazební funkce, než ty uvedené v příkladu. Zkoušel jsem i jiné a také fungují. Sada použitých generujících polynomů byla tuším někde ze stránek Xilinxu.

Demo se spouštěním několika generátorů pseudonáhodných posloupností čísel

Demo ve formě souboru virtuální MGF pásky pro emulátor PMD 85 od RM Teamu

2 komentáře u „Generování celočíselných pseudonáhodných posloupností maximální délky

  1. RomBor

    Opäť doplním, ak by niekto chcel plný rozsah 256 alebo 65536.

    ;——————————————————————————
    ; Pseudonahodne 16-bit cislo s periodou 65536 podla vztahu: X[1] = X[0] * 73 – 1
    ; I: –
    ; O: HL=RND
    ; M: HL, DE, F
    ; T: 131
    Rnd16: lxi h,0 ; posledna hodnota RND
    mov e,l ; DE=x1
    mov d,h
    dad h ; x2
    dad h ; x4
    dad h ; x8
    dad d ; x9
    dad h ; x18
    dad h ; x36
    dad h ; x72
    dad d ; x73
    dcx h ; x73-1
    shld Rnd16+1 ; uloz novu hodnotu
    ret

    ;——————————————————————————
    ; Pseudonahodne 16-bit cislo s periodou 65536 podla vztahu: X[1] = X[0] * 9 + 89
    ; I: –
    ; O: HL=RND
    ; M: HL, DE, F
    ; T: 106
    Rnd16B: lxi h,0 ; posledna hodnota RND
    mov e,l ; DE=x1
    mov d,h
    dad h ; x2
    dad h ; x4
    dad h ; x8
    dad d ; x9
    lxi d,89 ; x9+89
    dad d
    shld Rnd16B+1
    ret

    ;——————————————————————————
    ; Pseudonahodne 8-bit cislo s periodou 256 podla vztahu: X[1] = X[0] * 5 + 7
    ; I: –
    ; O: A=RND
    ; M: B, AF
    ; T: 54
    Rnd8: mvi a,0
    mov b,a
    add a ; * 2
    add a ; * 4
    add b ; * 5
    adi 7 ; + 7
    sta Rnd8+1
    ret

    1. Libor L.A.

      Tak jsem ty výše uvedené generátory hodil do pixelového zobrazovače a mohu potvrdit, že pokrývají všech 65536 event. 256 hodnot, přičemž každá hodnota je v rámci jednoho cyklu generována právě jednou. U osmibitové posloupnosti nedokážu posoudit míru distribuce jednotlivých hodnot, protože posloupnost 256 hodnot je příliš krátká na vizuální posouzení. Ale u obou 16-bitových posloupností jsou vidět zřetelné „stopy“, kdy se krátce po sobě generují čísla, lišící se pouze hodnotou vyššího bajtu. To samo o sobě nepředstavuje zase až tak významný problém, u grafických aplikací by to ale mohlo vytvářet rušivé obrazce.

Napsat komentář

Vaše emailová adresa nebude zveřejněna.