Welcome, Guest. Please login or register.


Author Topic: Randomize - véletlen szám generálása (Read 9496 times)

Offline IstvanV

  • EP addict
  • *
  • Posts: 4822
Re: Randomize - véletlen szám generálása
« Reply #30 on: 2019.January.16. 22:35:33 »
Ha a teljesen egyenletes eloszlás a fontos, akkor talán célszerűbb lenne a generálandó számoknak megfelelő méretű táblázatot 0 és 15 közötti értékekkel egyszerű növekvő sorrendben feltölteni, és utána a táblázatból véletlenszerű címről választani a következő elemet, amelynek a helyére az utolsó kerül, és a táblázat mérete eggyel csökken:
Code: C
  1. extern unsigned int rnd(unsigned int range);
  2.  
  3. #define RND_TABLE_SIZE 400
  4.  
  5. static unsigned char rnd_table[RND_TABLE_SIZE];
  6. static unsigned int rnd_left = 0;
  7.  
  8. void rnd_table_init(void)
  9. {
  10.   unsigned int  i;
  11.   for (i = 0; i < RND_TABLE_SIZE; i++)
  12.     rnd_table[i] = i & 15;
  13.   rnd_left = RND_TABLE_SIZE;
  14. }
  15.  
  16. unsigned char rnd_table_next(void)
  17. {
  18.   unsigned int  n;
  19.   unsigned char c;
  20.   if (!rnd_left)
  21.     return 0xFF;
  22.   n = rnd(rnd_left);
  23.   c = rnd_table[n];
  24.   rnd_table[n] = rnd_table[--rnd_left];
  25.   return c;
  26. }
« Last Edit: 2019.January.16. 22:49:32 by IstvanV »

Offline Povi

  • EP addict
  • *
  • Posts: 2296
  • Country: hu
    • http://povi.fw.hu
Re: Randomize - véletlen szám generálása
« Reply #31 on: 2019.January.17. 10:40:24 »
Ha a teljesen egyenletes eloszlás a fontos, akkor talán célszerűbb lenne a generálandó számoknak megfelelő méretű táblázatot 0 és 15 közötti értékekkel egyszerű növekvő sorrendben feltölteni, és utána a táblázatból véletlenszerű címről választani a következő elemet, amelynek a helyére az utolsó kerül, és a táblázat mérete eggyel csökken:

Hm... köszi, kipróbálom!
*** Speicherplatz zu klein

Offline IstvanV

  • EP addict
  • *
  • Posts: 4822
Re: Randomize - véletlen szám generálása
« Reply #32 on: 2019.January.18. 13:11:45 »
Elvileg jobb minőségű, de lassabb véletlenszám generátor rutinok. Ezeken valószínűleg még lehetne javítani és optimalizálni.
Code: ZiLOG Z80 Assembler
  1. ; A = RND(0..255)
  2.  
  3. random:
  4. .l1:    ld      hl, 7fffh               ; *
  5. .l2:    ld      a, l
  6.         add     hl, hl
  7.         xor     h
  8.         ld      l, a
  9.         xor     h
  10.         ld      h, a
  11.         ld      (.l1 + 1), hl
  12.         ld      c, l
  13. .l3:    ld      hl, 68ach               ; *
  14. .l4:    ld      b, 24h                  ; *
  15.         ld      a, h
  16.         ld      (.l4 + 1), a
  17.         ld      a, b
  18.         ld      b, l
  19.         add     hl, hl
  20.         xor     h
  21.         rla
  22.         ld      l, a
  23.         ld      a, b
  24.         rra
  25.         rlca
  26.         ld      h, a
  27.         ld      (.l3 + 1), hl
  28.         add     a, c
  29.         xor     l
  30.         ret
  31.  
  32. randomize:
  33.         ld      bc, 0027h               ; RANDOM_IRQ
  34.         exos    16
  35.         ld      l, d
  36.         ld      a, r
  37.         and     7fh
  38.         ld      h, a
  39.         or      l
  40.         jr      nz, random.l2
  41.         dec     hl
  42.         jr      random.l2
  43.  
  44. ; L = A = RND(0..L-1)
  45.  
  46. rnd8:
  47.         dec     l
  48. .l1:    ld      e, l
  49.         ld      d, l
  50.         ld      a, e
  51.         rra
  52.         or      e
  53.         ld      e, a
  54.         rra
  55.         srl     a
  56.         or      e
  57.         ld      e, a
  58.         rra
  59.         rra
  60.         rra
  61.         rra
  62.         and     0fh
  63.         or      e
  64.         ld      e, a
  65. .l2:    call    random
  66.         and     e
  67.         ld      l, a
  68.         ld      a, d
  69.         cp      l
  70.         jr      c, .l2
  71.         ld      a, l
  72.         ld      h, 0
  73.         ret
  74.  
  75. ; HL = BC = RND(0..HL-1)
  76.  
  77. rnd16:
  78.         dec     hl
  79.         ld      e, l
  80.         ld      d, h
  81.         ld      a, d
  82.         or      a
  83.         jr      nz, .l1
  84.         ld      a, e
  85. .l1:    ld      e, a
  86.         rra
  87.         or      e
  88.         ld      e, a
  89.         rra
  90.         srl     a
  91.         or      e
  92.         ld      e, a
  93.         rra
  94.         rra
  95.         rra
  96.         rra
  97.         and     0fh
  98.         or      e
  99.         ld      e, a
  100.         and     d
  101.         jr      z, .l2
  102.         ld      d, e
  103.         ld      e, 0ffh
  104. .l2:    push    hl
  105.         call    random
  106.         and     d
  107.         push    af
  108.         call    random
  109.         pop     bc
  110.         and     e
  111.         ld      c, a
  112.         pop     hl
  113.         ld      a, l
  114.         cp      c
  115.         ld      a, h
  116.         sbc     a, b
  117.         jr      c, .l2
  118.         ld      l, c
  119.         ld      h, b
  120.         ret

Offline IstvanV

  • EP addict
  • *
  • Posts: 4822
Re: Randomize - véletlen szám generálása
« Reply #33 on: 2019.January.19. 12:17:59 »
de aztán valahol azt olvastam, hogy szerencsésebb inkább a 16-tal osztás

Ez az algoritmustól függ, az itt használtaknál nem igazán számít, de PC-n gyakori ez a megoldás:

  y[n] = (y[n - 1] * a + b) % c

ahol c sokszor 2 hatványa, például 2^32, mert azzal nagyon egyszerű és gyors lehet a kód, x86 CPU-n a szorzás egy utasítással elvégezhető, a % műveletet pedig az eredmény 32 bitesre csonkítása automatikusan megoldja. Így azonban az alsó N bit legfeljebb 2^N hosszúságú sorozatot ismételhet, ez könnyen belátható, mivel szorzásnál és összeadásnál az alsó bitek nem függhetnek a felsőktől. Jobb minőségű megvalósításnál a c prímszám, lehetőleg Mersenne szám, azaz 2 hatványánál eggyel kevesebb, például 0x7FFFFFFF, így már nincs különbség a bitek véletlenszerűsége között.

Offline endi

  • EP addict
  • *
  • Posts: 7298
  • Country: hu
  • grafikus, játékfejlesztõ, programozás, scifi, tudományok, vallás
    • Honlapom
Re: Randomize - véletlen szám generálása
« Reply #34 on: 2019.January.19. 18:10:40 »
vajon az ilyen régi gépekben miért nem használtak táblázatot a random szám generálásának gyorsításához? szerintem mondjuk egy 256 elemű táblázat használatával egyszerűbb és gyorsabb generáló kód készíthető. 256 bájt meg nem sok, nem foglalt volna sokat.
Vigyázat! Szektás vagyok! :)

Offline geco

  • EP addict
  • *
  • Posts: 7082
  • Country: hu
    • Támogató Támogató
Re: Randomize - véletlen szám generálása
« Reply #35 on: 2019.January.19. 18:15:31 »
vajon az ilyen régi gépekben miért nem használtak táblázatot a random szám generálásának gyorsításához? szerintem mondjuk egy 256 elemű táblázat használatával egyszerűbb és gyorsabb generáló kód készíthető. 256 bájt meg nem sok, nem foglalt volna sokat.
Speccyn előszeretettel használták a ROM-ot táblázatként :D

Offline endi

  • EP addict
  • *
  • Posts: 7298
  • Country: hu
  • grafikus, játékfejlesztõ, programozás, scifi, tudományok, vallás
    • Honlapom
Re: Randomize - véletlen szám generálása
« Reply #36 on: 2019.January.19. 18:29:25 »
Speccyn előszeretettel használták a ROM-ot táblázatként :D

ja, ez is jó ötlet. össze xor-ozni egy "zajosabb" kis táblázat adataival, és elég jó eredménye lehet. legalábbis játékokhoz bővel elég
Vigyázat! Szektás vagyok! :)

Offline Zozosoft

  • Global Moderator
  • EP addict
  • *
  • Posts: 14723
  • Country: hu
    • http://enterprise.iko.hu/
Re: Randomize - véletlen szám generálása
« Reply #37 on: 2019.January.19. 18:46:58 »
Speccyn előszeretettel használták a ROM-ot táblázatként :D
Aztán ebből lesznek olyanok, mint pl a Monte Carlo Casino EP átiratában mindig 0 jön ki a ruletten...

Offline IstvanV

  • EP addict
  • *
  • Posts: 4822
Re: Randomize - véletlen szám generálása
« Reply #38 on: 2019.January.19. 18:47:42 »
Speccyn előszeretettel használták a ROM-ot táblázatként :D

Jól használható lehet ilyen célra tömörített adat is, ha a játék egyébként is tartalmaz ilyet, különösen a nagy méretű, m0 formátumú blokkok amikben az adat eredetileg sem volt túl egyszerű (pl. sok egymás után ismétlődő 0).

De külön véletlenszám táblázat általában nem igazán éri meg, legfeljebb ha nagyon fontos a sebesség, például grafikai célú használatnál. És ez a rutin is csak néhány utasítás, ami nem nagy különbség a táblázat olvasáshoz képest, és nem ismétlődik a kimenet 256 byte után. Még a fenti "bonyolultabb" random rutin is csak 38 byte, és CALL/RET utasítással együtt 193 ciklus alatt fut le, ami a programtól függően elfogadható lehet.
« Last Edit: 2019.January.19. 19:25:56 by IstvanV »

Offline endi

  • EP addict
  • *
  • Posts: 7298
  • Country: hu
  • grafikus, játékfejlesztõ, programozás, scifi, tudományok, vallás
    • Honlapom
Re: Randomize - véletlen szám generálása
« Reply #39 on: 2019.January.19. 18:54:55 »
a gyorsaság mindig számít :)
sőt, csak az számít :)
Vigyázat! Szektás vagyok! :)