atarionline.pl uwarunkowania progr. gen. liczb pseudolosowych - Forum Atarum

Jeśli chcesz wziąć udział w dyskusjach na forum - zaloguj się. Jeżeli nie masz loginu - poproś o członkostwo.

  • :
  • :

Vanilla 1.1.4 jest produktem Lussumo. Więcej informacji: Dokumentacja, Forum.

    • 1: CommentAuthormarok
    • CommentTime18 Jan 2023
     
    Stosunkowo jeszcze proste do wyprowadzenia równanie:
    255!/(256^255)

    daje wynik prawdopodobieństwa rzędu:
    2,65438504251e-110

    (strasznie mały)

    Jeśli się nie mylę (oczywiście mogę), odpowiada to prawdopodobieństwu wszystkich takich zdarzeń spośród kolejnych 255 losowań, które złożą się na wystąpienie dokładnie 1 z 255 wartości, a określona z góry jedna nie wystąpi wcale, z pełnej puli 256 wartości do wylosowania. (Tą jedną z 256, która by miała nie wystąpić byłoby 0.)

    Z pewnością sporo zdarzeń o innej strukturze wyniku (określone liczby powtórzeń) będzie mieć wyższe prawdopodobieństwa wystąpienia (niestety nie jestem tego w stanie policzyć).

    Jeśli więc stwarzana jest tablica liczb pseudolosowych, na zasadzie wartości niepowtarzalnych w innym miejscu tablicy (bo tak się to odbywa), to czytanie liniowe takiej tablicy jest być może jakimś, obawiałbym się, błędem. Zwłaszcza jeśli tablica czytana miałaby być tak "w koło" po wielekroć (licząc już w tysiącach razy).

    Rejest Random w Atari jest dużo bezpieczniejszy, bo nie jest dla naszego użytku liniowy. Nie jest wcale pewne, czy określony wynik pojawi się 1 czy 2 razy (czy więcej razy lub się nie pojawi) w ciągu 255 kolejnych losowań, nawet gdyby jakimś sposobem (zakładając "czarny scenariusz") udało się jednak korzystać z tego rejestru liniowo.


    Słabo się z tym materiałem zdołałem zapoznać na ten moment, ale przypominam o artykule w "Syzygy #7" o generatorze liczb pseudolosowych autorstwa Fox'a.

    Gdyby coś, nadawałby się w całości do przeklejenia w celach edukacyjnych (wcale chętnie bym nawet to zrobił, ale mam problem aby go dobrze przekonwertować do ascii).


    W niedawnej przeszłości w innym wątku na tym forum był link do rozwiązań teoretycznych dla generowania liczb pseudolosowych. Teraz go jednak nie przytoczę (chodzi tylko o hasło w angielsko języcznym wiki).


    Co do samej procedury generującej wartości pseudolosowe, natrafiłem osobiście na tę stronę:

    ->link<-

    Tam znajduje się (jako druga, uproszczona procedura) taki kod (którym można wygenerować pełną tablicę 255 bajtową):
    ; returns pseudo random 8 bit number in A. Affects A. (r_seed) is the
    ; byte from which the number is generated and MUST be initialised to a
    ; non zero value or this function will always return zero. Also r_seed
    ; must be in RAM, you can see why......

    rand_8
    LDA r_seed ; get seed
    ASL ; shift byte
    BCC no_eor ; branch if no carry

    EOR #$CF ; else EOR with $CF
    no_eor
    STA r_seed ; save number as next seed
    RTS ; done

    r_seed
    .byte 1 ; prng seed byte, must not be zero


    Ze swojej strony sprawdziłem, to jeden z głównych powodów mojego pisania tego wątku, że poza wartością #$CF w argumencie, istnieją dodatkowo inne, które spełnić mogą tą samą funkcję (dając inny szyk wartości).
    Natomiast wartość wyjściowa zmiennej r_seed może być dowolna z pominięciem 0 (jak w opisie).

    Więc podaję wszystkie wartości dla których ta procedura generuje tablicę wartości pseudolosowych:

    ; $1D. $2B. $2D. $4D. $5F. $63. $65. $69.
    ; $71. $87. $8D. $A9. $C3. $CF. $E7. $F5.


    Nie było to wydedukowane jakoś (wolałbym), ale wykryte programowo, jeśli chodzi o te wartości.
    • 2: CommentAuthortebe
    • CommentTime18 Jan 2023
     
    na temat radzenia sobie z generowaniem losowych wartości

    ->link<-
    • 3: CommentAuthorilmenit
    • CommentTime18 Jan 2023
     
    zerknij na:
    ->link<-
    oraz:
    ->link<-
    • 4: CommentAuthor0xF
    • CommentTime18 Jan 2023
     
    Nie było to wydedukowane jakoś (wolałbym), ale wykryte programowo, jeśli chodzi o te wartości.


    Jeśli chcesz poczytać o matematycznych podstawach, to ->link<-
    • 5: CommentAuthormarok
    • CommentTime18 Jan 2023
     
    Dziękuję za wszystkie odpowiedzi.

    @0xF: Mono niedawno w innym wątku dotyczącym generowania liczb losowych także dał link do tej strony. O tym próbowałem wpomnieć już poprzednio.


    @ilmenit: Bardzo do rzeczy te linki - dziękuję.
    Przychodzi mi na myśl, aby "zrekonstruować" działanie generatora liczb preudolosowych z Pokeya, które opisał Fox, tym lfsr6502. Tzn. fajnie by było, gdyby to ktoś zrobił, ja się na pewno do tego nie przymierzam.


    @TeBe: Problem trochę od innej strony, ale warte poznania. Muszę to sobie trochę przemyśleć i może coś jeszcze napiszę w luźniejszym nawiązaniu. Dzięki.
    • 6:
       
      CommentAuthorjhusak
    • CommentTime18 Jan 2023
     
    Mam nieodparte wrażenie, że jest to opisane i zakodowane np. w asapconv.
    • 7: CommentAuthortebe
    • CommentTime18 Jan 2023
     
    w grze Arkanoid generatorem liczb pseudolosowych jest rejestr VCOUNT ($D40B) co było przyczyną braku możliwości wylosowania bonusu w postaci 3 piłek.
    • 8: CommentAuthormarok
    • CommentTime19 Jan 2023
     
    @jhusak: mnie trochę bardziej chodziłoby o dołączenie do reszty tych przykładów z lfsr6502.

    @tebe: też ciekawe.


    Taka głupawa może uwaga. Jeśli wynikiem pseudolosowania ma być na wyjściu wartość jedynie podmieniona i z góry ustalona w stosunku do numeru porządkowego wejścia w procedurę (generowania liczby), to jest to po prostu konwersja wartości.
    A konwersja nie nosi z założenia znamion przypadku, a więc nie jest losowaniem (przypadkowej liczby).

    Stąd postulatem jest, aby nie wchodzić w taką procedurę "liniowo" (mam tu na myśli, bez dodatkowej ingerencji w jej, dwie tutaj, zmienne).


    Problem jaki się pojawiał w grze Tetris (jej różnych odmianach) był z goła inny. Przywołam. Chodziło o powtarzalność losowania wciąż tego samego (i/ lub brak przez dłuższy czas gry danego) klocka z zestawu.

    Tutaj mam swoją teorię dlaczego do czegoś podobnego mogło dochodzić.
    Wyobraźmy sobie, że taka gra korzysta z jakiejś procedury lfsr (zupełnie prawdopodobne). Więc działając "liniowo" (autokorekta zmiennych) powinna losować kolejne klocki (ich rodzaj), ("konwersująca") bez powtórzeń, aż do wyczerpania się puli (7-miu). Dopiero po tym fakcie musiałaby zmieniać swoje ustawienia na inne (by przetasować kolejność klocków do nowej puli). Więc w takim przypadku powtórzenia byłyby rzadkie (tylko przy zmianie puli) i tylko na dwa klocki (z gwarancją że 6 kolejnych będzie każdy różny).

    Nie z tym jest problem, więc ja sobie spekuluję że ta procedura może być za każdym użyciem jakby resetowana do stanu wyjściowego, który jest korygowany jeszcze o pewnien czynnik mierzonego czasu. Ale ponieważ czynnik ten ma tendencję do ponownego odmierzania dokładnie tych samych wartości (czasu) co wcześniej (bo np. wykona się w tym czasie "od punktu kontrolnego" ta sama porcja instrukcji), to często nie wpływa na zmianę tej korekty w kolejnych wywołaniach. Więc wynik procedury staje się powtarzalny, w postaci oddawania numeru tego samego klocka.

    To proste wytłumaczenie, zakładające że jest reset procedury lfsr lub zwykły brak autokorekty zmiennych (skoro korekta następuje na podstawie mierzenia upływu czasu).
    • 9: CommentAuthorilmenit
    • CommentTime19 Jan 2023 zmieniony
     
    Powtarzalność sekwencji zawsze trzeba brać do uwagi przy używaniu generatora liczb pseudolosowych. Można na wiele sposobów zmitygować ten problem, np. przeskakiwać stany podczas niedeterministycznych interakcji grającego, używać generatora, który ma długi okres, zanim sekwencja zacznie się powtarzać, generować znacznie większe wartości i je przekształcać do małej (wtedy znając małą wartość nie jest się w stanie powiedzieć jaka będzie kolejna mała wartość, bo może być jedną z wielu).
    • 10: CommentAuthormarok
    • CommentTime7 dni temu zmieniony
     
    Aby uniknąć sekwencji powtarzalnych można
    używać generatora, który ma długi okres, zanim sekwencja zacznie się powtarzać, generować znacznie większe wartości i je przekształcać do małej (wtedy znając małą wartość nie jest się w stanie powiedzieć jaka będzie kolejna mała wartość, bo może być jedną z wielu)


    Przekonuję się, że jest to skuteczne podejście do generowania liczb pseudolosowych w ogóle. Taki "gwóźdź programu".

    W takim razie jednak przydatność procedury, z którą wpierw przyszedłem do tego wątku i która została twórczo rozwinięta w linku do zastosowania wyłonienia liczby losowej, ponieważ daje wynik w tym samym rozmiarze, co wartość przekształcana (generowana), jest wątpliwa. Nie spełnia postulatu ani długiego okresu, ani więc przekształcenia do mniejszej wartości.
    Ten ostatni punkt upoważnia do określenia jej funkcji jako "konwertującej wartość wejścia".

    Owszem, można na jej podstawie prosto jeszcze zadbać o zmniejszenie wartości do wymaganego rozmiaru, ale ponieważ nigdzie o tym nie wpominano przy okazji jej omawiania (jako np. wskazanie), więc potraktuję ją tutaj z całą surowością.

    Te inne wartości zmiennej (przy eor; które sam podawałem i które są w linku) nic w zasadzie poważnego nie wnoszą. Zammienne stosowanie ich nie przynosi niczego "nadzwyczajnego". Określone sekwencje powtarzają się masowo dla każdej z tych wartości, więc podmiana wartości samej tej zmiennej nie daje najmniejszej gwarancji uzyskania innego wyniku.

    Chwila o powtarzających się "masowo" sekwencjach z tej procedury.

    Jest pewnym "masochizmem" czynić podobne wykazy, ale dla zobrazowania "problemu" ma to swój sens:
    01 02 04 08 10 20 40 80
    03 06 0C 18 30 60 C0 XX
    05 0A 14 28 50 A0 XX XX
    07 0E 1C 38 70 E0 XX XX
    09 12 24 48 90 XX XX XX
    0B 16 2C 58 B0 XX XX XX
    0D 1A 34 68 D0 XX XX XX
    0F 1E 3C 78 F0 XX XX XX
    11 22 44 88 XX XX XX XX
    13 26 4C 98 XX XX XX XX
    15 2A 54 A8 XX XX XX XX
    17 2E 5C B8 XX XX XX XX
    19 32 64 C8 XX XX XX XX
    1B 36 6C D8 XX XX XX XX
    1D 3A 74 E8 XX XX XX XX
    1F 3E 7C F8 XX XX XX XX
    21 42 84 XX XX XX XX XX

    Jest to niepełny wykaz.
    Pierwsza kolumna to wartości które mogą następować (ich naturalna kolejność) po różnych wartościach dla każdej z wartości zmiennej (8 wariantów), ale pozostałe kolumny to są wartości, które wynikają z poprzedniej (a wariant zmiennej nie ma tu nic do rzeczy).
    To powinno wyjść jako wniosek z analizy prostego przecież programu, przyznaję że mnie nie wyszło ("przespałem" analizę).

    Pomiędzy $40 a $80 znajduje się $20 wartości nieparzystych, a to oznacza że jest drugie takich $20 wartości, które "muszą" (wariant zmiennej nie ma znaczenia) następować odpowiednio po "swojej" (czyt. poprzedniej) wartości.

    Wygląda więc na to, że ogólna liczba takich "zdeterminowanych" wartości to 64 (1+1+2+4+8+16+32).

    EDIT:
    Pomyłka z tymi ostatnimi obliczeniami.
    Powinni być raczej 127 (1*7+1*6+2*5+4*4+8*3+16*2+32*1)
    • 11: CommentAuthormarok
    • CommentTime7 dni temu zmieniony
     
    Uzupełniając.

    Łatwo dojść do wersji procedury z przekształcaniem wewnątrz wartości bajtu w odwrotnym kierunku.

    rand_8
    LDA r_seed ; get seed
    ; ASL ; shift byte
    lsr ; alt. shift byte
    BCC no_eor ; branch if no carry

    EOR #$C3 ; $C3 or $E7
    no_eor
    STA r_seed ; save number as next seed
    RTS ; done

    r_seed
    .byte 1 ; prng seed byte, must not be zero

    ; asl
    ; $1D. $2B. $2D. $4D. $5F. $63. $65. $69.
    ; $71. $87. $8D. $A9. $C3. $CF. $E7. $F5.

    ; lsr
    ; $B8. $D4. $B4. $B2. $FA. $C6. $A6. $96.
    ; $8E. $E1. $B1. $95. $C3. $F3. $E7. $AF.


    Uzyskany efekt końcowy.

    Zmienia się kolejność "sekwencji deterministycznych"
    80 40 20 10 08 04 02 01
    C0 60 30 18 0C 06 03

    Ich ogólna liczba powinna się zgadzać (zgaduję).

    Wartości zmiennej, które "działają", zmieniają się na inny zestaw (wygląda jakby o 2 pozycje mniejszy, co mnie troszkę zaskakuje - ale ogólnie to mało co rozumiem).
    W obu tych zestawach dwie wartości się powtarzają, więc nabierają charakteru uniwersalności.

    edit:
    Wartości działających jest dokładnie tyle ile było przy obrotach w prawo. (Wiem już jak zgubiłem dwie poprzednio nie przywołane.) Wartości są lustrzanym (bitowo) odbiciem poprzednich, teraz są posegregowane dla lsr aby wizualnie korespondowały z tymi dla asl.
    • 12: CommentAuthor0xF
    • CommentTime7 dni temu
     
    8-bitowy generator z "prawidłowym" wielomianem ma okres 255 - bo występują wszystkie wartości oprócz zera. Dla seeda zero utkniesz w zero.
    Te różne "prawidłowe" wielomiany (czyli w praktyce stałe dla EOR) są w praktyce równie dobre - dają wyniki w różnej kolejności, ale chyba nie ma tak, że jedne są lepsze, a drugie gorsze.
    W POKEYu jak wiadomo jest generator 17-bitowy. Jest też o tyle lepszy, że działa z zegarem 1,77 MHz.
    Co do gier to w "Bank Bang!" otwieranie drzwi jest losowane przez odczyt RANDOM w dwóch kolejnych instrukcjach, coś w rodzaju:
    LDA RANDOM
    ORA RANDOM
    AND #$0F
    BEQ OTWORZ

    Atari800 oryginalnie wołało po prostu funkcję C "rand()", co powodowało, że drzwi otwierały się bardzo rzadko.
    • 13: CommentAuthormarok
    • CommentTime6 dni temu zmieniony
     
    W Atariki pod hasłem "RANDOM" w mapie pamięci, znajduje się precyzyjna (pełna?) definicja.

    Liczba pseudolosowa z zakresu od 0 do 255.

    Rejestr zawiera 8 najstarszych bitów 9- lub 17-bitowego rejestru LFSR o wielomianie odpowiednio 1+x^4+x^9 lub 1+x^12+x^17 zależnie od stanu bitu 7 AUDCTL. Zawartość rejestru przesuwana jest w prawo co cykl zegara 1,77 MHz. Przy odczytywaniu serii wartości pseudolosowych dobrze jest więc zadbać, żeby pomiędzy kolejnymi odczytami upłynęło co najmniej 8 cykli pracy zegara 1,77 MHz; w przeciwnym wypadku kolejno odczytane wartości mogą okazać się między sobą zauważalnie skorelowane. Ten efekt da się zauważyć zwłaszcza na akceleratorach.

    Podczas resetowania układu (za pomocą bitów 0 i 1 SKCTL) do rejestru LFSR wsuwane są jedynki.


    Właśnie do niej zajrzałem i przywołuję, bo warto. ;)
    (odpowiedni timing)

    Z informacji, których raczej brakuje, a są w artykule z Syzygy, to nie ma o szczególnym przypadku działania rejestru LFSR w momencie przełączenia zegara z 17 na 9 bitów.

    Postaram się (nieprecyzyjnie) to zreferować:
    zamiast wyniku operacji EOR na bitach 8 i 13 do bitu 16 zawsze wsadzana jest 1-ka;
    ( odczyt z Random przełączonego na 9 bitów Pokeya daje wgląd w bity 16-9 )
    ( odczyt z Random przełączonego na 17 bitów Pokeya daje wgląd w bity 8-1; EOR odbywa się na bitach 0 i 5 )

    Przyczyną tego wyjątku jest to, że LFSR mogłby się "zatrzasnąć na 0".

    Być może to już wszystko, czego nie ma w haśle w Atariki z informacji z artykułu, ale dla mnie wszystko to pozostaje jakby nadal niedopowiedziane (niezrozumiałe najpewnie z przyczyn niedostaktu wiedzy matematycznej).

    Chyba że jeszcze to, że to jest cały czas ten sam rejestr LFSR i on cały czas pracuje (przesuwa wszystkie swoje 17 bitów) mimo przełączenia na 9 bit Pokeya.


    Wychodząc ze wzoru tych wielomianów to nie wiem jak to dokładnie wpasowuje się w opis działania rejestru LFSR Pokeya ("ludzkim językiem" z artykułu). Jak traktować ten X przy wzorze, pisząc kolokwialnie. Czy ten X reprezentuje liczbę 2, czy jest to faktycznie zmienna?

    Korelacja tych wielomianów z opisem działania Pokeya polega na tym, że:
    1+x^[12+5]+x^[17+0] = 1+x^[4+13]+x^[9+8]

    Rozumiem, że wielomian już opisuje działanie szczegółowe LFSR Pokeya (i ten opis z artykułu nic więcej w to nie wnosi), mimo wszystko dobrze że ten artykuł jest i można się z niego dowiedzieć o Random na Atari.

    EDIT:
    poprawiłem to co najważniejsze (całą resztę nie ruszam)
    bit 17 przeflancowałem na 16 (17 bitów: 0-16)
    (mam nadzieję, że ta reszta jest już dobrze przepisana z artka)
    • 14: CommentAuthor0xF
    • CommentTime6 dni temu
     
    to jest cały czas ten sam rejestr LFSR i on cały czas pracuje (przesuwa wszystkie swoje 17 bitów) mimo przełączenia na 9 bit Pokeya.

    Tak właśnie jest. Czy to jest niejasne po lekturze mojego starego artykułu w Syzygy?

    Wychodząc ze wzoru tych wielomianów to nie wiem jak to dokładnie wpasowuje się w opis działania rejestru LFSR Pokeya ("ludzkim językiem" z artykułu). Jak traktować ten X przy wzorze, pisząc kolokwialnie. Czy ten X reprezentuje liczbę 2, czy jest to faktycznie zmienna?

    Przeczytałeś ->link<- ?

    LFSR w POKEYu to Fibonacci LFSR a wykładniki w wielomianie mówią, które bity z rejestru bierzemy do XORa. Tyle od strony praktycznej. Jest do tego teoria matematyczna, ale jeśli potrzebujesz zaprogramować lub zbudować sprzętowy LFSR, potrzebujesz tylko wiedzieć, które bity XORować i to właśnie mówią wykładniki wielomianu.

    Programowo mniej kodu jest dla Galois LFSR i to jest właśnie to, co pojawia się w Twoich kawałkach kodu.
    • 15: CommentAuthormarok
    • CommentTime6 dni temu
     
    Tak właśnie jest. Czy to jest niejasne po lekturze mojego starego artykułu w Syzygy?

    Dokładnie odwrotenie.
    To wiem z Twojego artykułu, ale prawdopodobnie z hasła na Atariki ciężko o taki jednoznacznie wniosek (pewnie nie napisałem tego w odpowiednim miejscu czy nazbyt zrozumiale).

    Jeśli chodzi o Pokeya i reset to nie zrozumiałem z Twojego artykułu (skoro pytasz o niezrozumienie), czy i jak on może zostać przytrzymany w tym stanie (reset) przez 17 cykli by się "najedynkował" (kolokwializm/ neologizm). Może działa to z automatu (jako reset) albo można to jakoś sprokurować. (Źródeł do artykułu z przykładami jeszcze nie widziałem, tam może znalazłbym wyjaśnienie - przepraszam, ale nie zdołałem jeszcze sobie ich przygotować do wglądu.)
    W Atariki jest "Podczas resetowania układu (za pomocą bitów 0 i 1 SKCTL) do rejestru LFSR wsuwane są jedynki."
    To raczej by znaczyło, że działa tu automat, ale też nie jest to jasne, czy chodzi dokładnie o 17 cykli (może tylko naprowadza na taki wniosek.)


    Przeczytałeś ->link<- ?

    Próbuję, w jakimś tylko stopniu jest to dla mnie przyswajalne.

    LFSR w POKEYu to Fibonacci LFSR

    Tak to kojarzyłem.

    potrzebujesz tylko wiedzieć, które bity XORować i to właśnie mówią wykładniki wielomianu

    Tylko wymagałoby to pewnego jeszcze dopowiedzenia.
    Bity w LFSR są liczone wg kierunku przesuwu nimi (w prawo, z lewa). Nie spotykałem się dotąd z takim określaniem porządkowym bitów.
    To dziwne równanie, które "wysmażyłem" wcześniej, jest właśnie skutkiem braku zauważenia tego elementu (podpowiada ilustracja) i szukaniem mimo wszystko jakieś korelacji (bity się zgodziły - suma ich odwrotnie czytanych pozycji równa się wszystkim bitom, czyli 17).
    • 16: CommentAuthor0xF
    • CommentTime5 dni temu zmieniony
     
    czy i jak on może zostać przytrzymany w tym stanie (reset) przez 17 cykli by się "najedynkował"

    lda #0
    sta SKCTL
    cmp (0,x)
    cmp (0,x)
    lda #3
    sta SKCTL

    Powyższy kod resetuje POKEYa przez 18 cykli, czyli cały rejestr 17-bitowy się najedynkuje.

    Edit:
    Potencjalnie więcej cykli w przypadku wstrzymania CPU przez ANTICa. POKEY działa cały czas.
    • 17: CommentAuthormono
    • CommentTime5 dni temu zmieniony
     
    Nie.
    Poprawny reset POKEY-a nie może bazować na zegarze CPU, bo ten bywa większy niż 1.77, a na zegarze którym taktowany jest hardware:
    lda #0
    sta SKCTL
    sta WSYNC
    sta WSYNC
    lda #3
    sta SKCTL

    Tu masz gwarancję, że niezależnie od tego jakie będzie turbo w komputerze, reset będzie całkowity, bo bazuje na czasie trwania linii skanningowej (114 cykli 1.77 MHz).
    Temat był omawiany przez Draco w wątku o którymś BASIC-u.
    • 18: CommentAuthormarok
    • CommentTime5 dni temu zmieniony
     
    @mono: ok, jeszcze się może delikatnie odniosę, a teraz przeklejam to com se bazgrnął (bardziej w polemice do Fox'a)


    Czy to się zgadza?

    w celu uproszczenia opisu działania,
    jeśli mamy Pokey przełączony na 17 bitów,
    to jest to ".Word" (1-16) + Carry Bit (17) [w nawiasach ponumerowane bity pocz. od najstarszego, jak dla lfsr]

    w następnym cyklu, po
    lfsr do x^1 wpada x^17 po eor z x^12
    rcr do x^1 wpada(-łby) x^17 (po prostu)

    [ RCR Rotate Through Carry Right: 16-bitowy odpowiednik ror.6502 ]

    jeśli mamy Pokey przełączony na 9 bitów
    to jest to ".Byte" (1-8) + Carry Bit (9)

    i po
    lfsr do x^1 wpada x^9 po eor z x^4
    rcr do x^1 wpada(-łby) x^9



    jeśli tak można to zapisać, to nie rozumiem następujących rzeczy:

    co taki zapis mówi?:
    x^17+x^12+1

    przyjmując, że każde x^n niezależnie od pozostałych, reprezentuje swój stan - wartość bitu na pozycji n (z zawartości word / byte)
    (0 lub 1)

    wynik tego działania "na wielomianie" (czy jak je traktować) dać może wartość z przedziału 1-3

    jak rozumiem, dokonuje się następnie na tym wyniku operacja mod(ulo) z 2:
    wynikiem dalej, z tego modulo, może być 1 (1,3) lub 0 (2):
    jeśli x^17 <> x^12 (XOR) to dostajemy na wielomianie [1+0 +1]%2 = 0 , a pasowałoby bardziej odwrotnie, czyli 1,
    jeśli x^17 == x^12 (XOR) to dostajemy na wielomianie [[0|2]+1]%2 = 1 , czyli odwrotnie, niż spodziewałbym się (0).

    wynik spodziwałbym się jest już tym bitem, który ma wejść do x^1 w następnym cyklu lfsr (ale jest jakby odwrotnością)


    Przechodząc teraz do przykładu na stronie wikipedii o lfsr.
    Dodatkowo są tam rzeczy poza analogiami z tym powyżej, których nie rozumiem.

    Przykładowy lfsr jest rozpisany na 16 bitów (nie na 17).

    Tam, gdyby to trzeba przypisywać, rolę Carry Bit mógłby ewentualnie spełniać bit 16.

    Podany jest przykład (z diagramu) LFSR na wielomianie:
    x^16+x^14+x^13+x^11+1

    rezultat na tym wielomiane (po modulo) miałby więc znaleźć się w x^1 w następnym cyklu (najstarszym bicie)

    Jest parę reguł odnośnie tap-ów (pozycji dla wykładników wielomianów).
    The number of taps is even.
    The set of taps is setwise co-prime; i.e., there must be no divisor other than 1 common to all taps.

    The bit positions that affect the next state are called the taps. In the diagram the taps are [16,14,13,11].


    które nie rozumiem, jak spełnia ten wielomian
    gdyż w moim rozumieniu problemem jest to że 16 i 14 mają wspólny dzielnik 2 różny od 1.

    Może, w przypadku gdyby tak interpretować ten wielomian, jak zrobiłem to powyżej, lepszą pomocniczo (lepiej zrozumiałą) konwencją zapisu byłoby:
    x[17]+x[12]+1 ?

    Tylko, zapewne gdzieś tu tkwi błąd.
    • 19: CommentAuthormarok
    • CommentTime5 dni temu
     
    @mono: Fox nawiązywał (świadomie / podświadomie) zapewne do swoich źródeł z przeszłości (o których pisałem), a wtedy nie było realnie innego zegara CPU w zastosowaniu. Poza tym, narobiłem takich "byków", że było co poprawiać i chciał to zrobić sprawnie (nie bawiąc się już w didaskalia). Generalnie tamten przykład wyjaśnia sprawę, jak liczyć cykle w odniesieniu do resetu Pokeya (o to mi chodziło).
    Ja ze swojej strony nie doczytałem, że stan resetu utrzymuje się w stanie bitów %00 (bodajże ;) ).
    Czasami czyta się pewne ustępy bez właściwego zrozumienia.
    • 20: CommentAuthormarok
    • CommentTime5 dni temu
     
    Chyba jednak liczba tych bitów z przykładu to także 17. Tam jest dodatkowy bit 0 (nie 17). Ma reprezentować tą 1 w działaniu na wielomianie (wciąż nie pojęłem dlaczego to zawsze 1).
    • 21: CommentAuthor0xF
    • CommentTime5 dni temu
     
    x^0=1
    • 22: CommentAuthormarok
    • CommentTime5 dni temu
     
    Dobrze, ale w praktyce odwraca to wynik całości działania.

    Dla wzoru lsfr Pokeya x^17+x^12+1 ( GF(2) x^17+x^12+1 ?),
    gdy oba bity (.17 i .12) są skasowane (ogólnie: w jednakowym stanie) wyszłoby 1.

    a formalnie, czy x^0 tutaj nie oznaczałby x^17 ? (inne nazewnictwo)
    • 23: CommentAuthormarok
    • CommentTime4 dni temu zmieniony
     
    Programy liczące na podstawie tych wielomianów (z przykładów na stronie wiki) zdają się, jak dla mnie, ignorować to + 1 (od x^0) w obliczeniach.

    Pozostaje to w każdym bądź razie dla mnie wciąż zagadkowe, jakie dokładnie działanie odbywa się z tymi wielomianami.

    To się pewnie do tego nie odnosi, ale wyjaśnienie "inverse modulo" to byłoby to, o co by mogło chodzić… (redukcja + 1 z wyrażenia obliczanego wielomianu):
    Division is multiplication by the inverse modulo p



    W opisie z wikipedii o "Fibonacci LFSRs"…

    The LFSR is maximal-length if and only if the corresponding feedback polynomial is primitive over the Galois field GF(2).


    Odszukałem stronę z ich wykazem.
    ->link<-

    Skrócona lista (do której prowadzi link) określona jest jako "primitive irreducible polynomials", rozszerzona (dostępna do zassania) to "primitive polynomials" (co może znaczyć to samo).


    Z listy rozszerzonej, która wydaje się kompletować wszystkie warianty tych "primitive polynomials" do 32 wykładnika przy x (zawiera aż 5372962 wielomianów) wybrałem do "analizy" te pogrupowane wg klucza.

    Pierwsze kryterium, to chyba się określa jako GF(X^9), to wielomiany z najwyższą wartością wykładnika x^9, drugie to liczba "tabs" równa 2. Nasze "x" to raczej 2, więc to byłoby na dobrą sprawę GF(2^9).

    x^9 + x^1 + 1
    x^9 + x^4 + 1
    x^9 + x^5 + 1
    x^9 + x^8 + 1

    Jak można zauważyć tylko część kombinacji jest dopuszczalnych (by było to wyrażenie "primitive").

    Jeszcze jedna grupa, którą wybrałem do analizy.
    Różni się tylko tym (od tej poprzedniej), że drugie kryterium jest obliczone na liczbę "tabs" równą 8.

    x^9 + x^8 + x^6 + x^5 + x^4 + x^3 + x^2 + x^1 + 1
    x^9 + x^8 + x^7 + x^6 + x^5 + x^4 + x^3 + x^1 + 1

    (Z tej grupy nieaktywnych jest 6 kombinacji. Bez jednego z wykładników: 8,6,5,4,3,1 przy x w wielomianie.)

    LFSR Pokeya to x^9 + x^4 + 1 .

    Analizy w sumie nie będzie. ;)

    (Chodziłoby mi o przypadek drugiego warunku z tych, które określają pozycję tabs dla wielomianów, które działają. We wcześniejszych wpisach pisałem coś, że 16 i 14 jako wykładniki są podzielne przez tą samą wartość, 2, w jednym z takich wielomianów, użytym za przykład na stronie wiki. W każdym razie nie tak należy to rozumieć, jak ja to zrozumiałem. W sensie tego drugiego warunku dla wielomianów, które mogą działać. A rozważania jaki jest na prawdę ten warunek przekraczają moje kompetencje lub w najlepszym razie są przedwczesne.)


    Co jednak teraz zauważam. (!?)

    Nie ma wśród tego wykazu "primitive polynomial" tego od Pokeya przełączonego na 17 bit: x^17 + x^12 + 1 .

    To trochę zastanawia (niepokoi?).
    Nie umiem odpowiedzieć dlaczego, ale temat zamierzam jeszcze podrążyć.
    • 24: CommentAuthorilmenit
    • CommentTime4 dni temu
     
    Zapytaj ChatGPT, jest dobry w takich wyjaśnieniach, serio :)
    • 25: CommentAuthormarok
    • CommentTime4 dni temu
     
    Zapewne to dobra podpowiedź (trzeba by spróbować, by się o tym przekonać).

    Będąc jednak tradycjonalistą (że się tak określę) i dodatkowo z przyczyn "lingwinistycznych" (musiałbym się poważnie zastanowić nad poprawnym zapisem swojego pytania; angielski nie jest mi specjalnie bliski, z pisaniem poprawnym mam ogromny kłopot) nie spieszno mi do tego. Ponad to czułbym się zapewne onieśmielony jakiś "gadać" z AI (kto wie z czym i kim do końca?? to ostatnie rzucam przed wstępnym nawet jakimś rozpoznaczniem tego czym jest AI w tej odsłonie - zalecana jest może jakaś ostrożność podejścia, tak mi się wydaje).

    W sumie (więc) nie wiem co to jest (specjalnie nawet że jest). Choć wątek o AI jest obecnie na AOL dość mocno zdaje się dyskutowany, to muszę przyznać, że akurat go nie śledzę (z innych źródeł potencjalnej wiedzy na ten temat nie korzystałem).


    Tak przy okazji, znalazłem link do tego (choć to niedostępne dla ogółu):

    ->link<-

    (może dobre by to było dla bardziej wtajemniczonych w tych lfsr -ach)

    coś do liczenia "period" dla Polynomials ograniczonych w GF ? (w zasadzie nie umiem nazwać tego, czego aktualnie szukam)
    • 26: CommentAuthormarok
    • CommentTime3 dni temu zmieniony
     
    2^17+2^12+1 = 135169

    ta liczba nie przechodzi testu na liczbę pierwszą
    ->link<-

    jest to (2) niezbędny warunek dla wielomianu przy GF(2^n) gwarantujący okres 2^n-1

    EDIT:
    czy niezbędny? chyba jednak nie jest to prawidłowe wnioskowanie i rozumienie warunku 2 (sorry)

    przez analogię można to wykluczyć, gdyż za

    ->link<-

    "511 is not prime. It is divisible by 7."
    "135169 is not prime. It is divisible by 29."
    "92161 is not prime. It is divisible by 23."

    to z przykładu wiki dla wielomianu lfsr:
    2^16 + 2^14 + 2^12 +2^11 + 1 = 92161
    • 27: CommentAuthormarok
    • CommentTime3 dni temu zmieniony
     
    This also tells you that product is a bit more complicated, because it requires to do all the shifts but followed by a polynomial long division.


    Znalazłem to (wyrwane tu z kontekstu), co wiąże działanie na wielomianie (takim do lfsr) z dzieleniem (wielomianu? przez wielomian). A więc może wiązać się z tym użycie "inverse modulo" (czyli jak dla mnie ten brak odniesienia + 1 w obliczeniach na wielomianie w kodzie lfsr).

    (To odnośnie odpowiadania sobie na wątpliwości, które wyrażałem tu poprzednio.)
    • 28: CommentAuthormarok
    • CommentTime3 dni temu zmieniony
     
    # Complete list of primitive trinomials over GF(2)
    # up to degree 400

    ->link<-

    jest tam i ten
    17,12,0

    więc nie ma "problemu"
    (okres lfsr na tym "trójmianie" to rzeczywiście 2^17-1)

    trinomials to krótka odmiana polynomials
    akurat taka, jaka jest w użyciu przy Pokeyu

    Poprzednia lista, na której się oparłem, musi być nieco niekompletna

    edit:
    Już chyba rozumiem dlaczego na tamtej liście nie ma wszystkich "wielomianów, które działają".

    przykład:
    na tej liście trójmianów wykładnik 17 jest reprezentowany tak:
    17,3,0
    17,5,0
    17,6,0
    17,11,0
    17,12,0
    17,14,0

    widać, że robią się z tego pary (3+14, 5+12, 6+11) wielomianów, które są względem siebie "symetryczne"


    na pierwszej liście wielomianów wykładnik 17…

    x^17 + x^3 + 1
    x^17 + x^3 + x^2 + x^1 + 1
    x^17 + x^5 + 1
    x^17 + x^6 + 1
    x^17 + x^8 + x^4 + x^3 + 1
    x^17 + x^8 + x^7 + x^6 + x^4 + x^3 + 1
    x^17 + x^10 + x^9 + x^8 + x^6 + x^5 + x^3 + x^2 + 1
    x^17 + x^12 + x^6 + x^3 + x^2 + x^1 + 1
    x^17 + x^12 + x^9 + x^5 + x^4 + x^3 + x^2 + x^1 + 1
    x^17 + x^12 + x^9 + x^7 + x^6 + x^4 + x^3 + x^2 + 1
    x^17 + x^14 + x^11 + x^7 + x^5 + x^3 + x^2 + x^1 + 1
    x^17 + x^15 + x^13 + x^11 + x^9 + x^7 + x^5 + x^3 + 1
    x^17 + x^15 + x^13 + x^11 + x^9 + x^7 + x^6 + x^4 + x^2 + x^1 + 1
    x^17 + x^16 + x^3 + x^1 + 1

    czyli z "trójmianów" są wszystkie (3, 5, 6 ) z par (14, 12, 11)
    symetryczne są "domyślne", więc lista jest też kompletna (źle o niej zdążyłem już napisać)

    dla wielomianów innych niż trójmiany "symetryczność" też musi mieć zastosowanie

    na wiki też coś na ten temat napisano (przypominam sobie hasłowo, choć nie doczytałem w czym rzecz)
    • 29: CommentAuthorilmenit
    • CommentTime3 dni temu
     
    Nie do końca rozumiem co próbujesz uzyskać, z czym masz problem, albo czego nie rozumiesz. Czy wkleić kod (najlepiej cały kompilowalny kawałek) i jaki jest z nim problem z punktu widzenia teorii LFSR?
    • 30: CommentAuthormarok
    • CommentTime3 dni temu
     
    Próbuję coś odpowiedzieć, trochę mi się to nie klei.

    Ostatnio próbowałem na własną rękę przekonać się (siejąc może wątpliwość) czy okres dla generatora zniekształceń Pokeya przestawiony na 17 bit rzeczywiście działa z tym okresem, o którym "wiadomo" (potwierdzając to sobie).

    Nie mam problemu z kodem, bo nic z tych rzeczy nie piszę. Temat mi się objawił sam, przeglądając stronkę. Dodałem do tam zawartych informacji pewne szczegóły, które okazały się nieznaczące i oczywiście nieodkrywcze.



    Problem jest taki, że często się mylę i zabieram głos przedwcześnie (brakuje mi opanowania), potem się poprawiam i wycofuję z twierdzeń, sugestii, czy wyrażanych wątpliwości. Tworzy się niemiły chaos dla "postronnych".

    Próbowałem coś zrozumieć ogólnie z podstaw matematycznych chwytając się pewnych szczegółów i za ich pomocą starałem się odkryć więcej. Ale mam za duże braki i ogólnie nie tak sprawny umysł, jakbym sobie życzył, żeby się w to bawić (a innych dręczyć) zaczynając od podstaw. No ale, nie zawsze się człowiek kulturalnie umie odnaleźć w towarzystwie.
    • 31: CommentAuthormarok
    • CommentTime14 godzin temu
     
    Napisałem krótki program symulujący zachowanie lfsr 9/17 bit dla Pokeya (na <300 bajtów).

    Symulacja obejmuje przełączanie szerokości bitów i reset Pokeya (czy działa dobrze?).
    (Uwzględniłem konieczność 18 cykli do skasowania wszystkich bitów, tak jak interpretacyjnie pojąłem, że to działa. Nie jestem też pewien momentu wstawiania bitu po przełączeniu z 17 na 9.)

    Sterowanie to klawisze: lewo / prawo : zmiana tempa następowania kolejnego cyklu przekształceń lfsr,
    lewo / prawo (+ control) : przełączanie się na 9/17 bit,
    R : inicjowanie Reset lub inicjowanie normalnego przekształcania lfsr (po reset).

    Strzałki pomocnicze pokazują skąd pobierana jest informacja dla bitu który nadchodzi i wejdzie na pierwszą pozycję do lfsr w następnym cyklu.

    Są podawane dwie wartości przeliczone na hex z tych bitów / rejestrów lfsr. Odczyt symulowanego $d20a (random) zwracałby tą wartość, która znajduje się bliżej strzałek (otaczają ją). Druga to ta, do której analogicznie nie byłoby sprzętowego dostępu.

    Ostatnia wartość, z drugiej strony ekranu, jakby na uboczu, w hex, to wartość regulowanej prędkości przekształceń lsfr, czas pomiędzy cyklami przekształceń przeliczony na ramki (czyli liczba ramek na cykl).

    Nazwa programiku jest bardzo robocza (coś się może wymyśli, może ktoś podsunie nawet jakiś pomysł).

    Myślałem jeszcze o dodaniu sygnalizacji "BELL" inicjowania Reset, ale nie do końca wiem jak to zrobić w asm.

    Oprócz tego mogłyby się ewentualnie przydać rozkazy zatrzymania i pojedynczego kroku przekształceń.

    Jeśli ktoś miałby pomysł do wykorzystania w związaku z tą emulacją lfsr to oczywiście chętnie przeczytam.

    Przełączanie między 9/17 bit mogłoby może pozwolić na uzyskiwanie okresów o wartości liczby pierwszej (co byłoby może istotne dla generowanych dźwięków). Tutaj teoretycznie można trochę z tym poeksperymentować (tak sobie kombinuję). Natomiast ciężko jest na pewno uzyskać kontrolę nad lfsr w hardware, czyli byłoby to trudne później precyzyjnie odtworzyć (za ew. eksperymentem).