Znalezienie nasion dla 5-bajtowego PRNG

Question

Stary pomysł, ale od tego czasu nie mogłem znaleźć dobrego sposobu na rozwiązanie postawionego problemu. Tak więc "wymyśliłem" (patrz poniżej) bardzo zwartą i, moim zdaniem, dość dobrze wykonującą PRNG, ale nie mogę znaleźć algorytmów do budowania odpowiednich wartości początkowych dla dużych głębokości bitowych. Moje obecne rozwiązanie jest po prostu brutalnym wymuszaniem, jego czas działania to O (n^3).

Generator

Mój pomysł przyszedł z XOR krany (w zasadzie LFSRs) niektóre stare maszyny 8bit wykorzystywane do generowania dźwięku. Miałem do czynienia z XOR jako bazą na C64, starałem się tworzyć opkody i doświadczałem rezultatów. Ostateczny roztwór roboczy się następująco:

asl 
adC#num1 
eor #num2 

to 5 bajtów na 6502. z dobrze wybraną num1 i num2, w akumulatorze, że iteracje przez wszystkie wartości 256 w pozornie losowej kolejności, to znaczy, że wygląda dość przypadkowo, gdy używa się go do wypełnienia ekranu (napisałem wtedy wersję demo 256b). Jest 40 odpowiednich num1 & num2 par dla tego, wszystkie dając przyzwoicie wyglądające sekwencje.

Koncepcja ta może być także uogólnione, jeśli w przeliczeniu na czysty C, może wyglądać następująco (BITS czym głębokość nieco od sekwencji):

r = (((r >> (BITS-1)) & 1U) + (r << 1) + num1)^num2; 
r = r & ((1U<<BITS)-1U); 

Kod C jest większa od jego uogólnić a nawet gdyby użyć pełnej głębokości niepodpisanej liczby całkowitej, C nie miałby niezbędnej logiki przenoszenia, aby przenieść wysoki bit przesunięcia do operacji dodawania.

Dla niektórych analiz wydajności i porównań, patrz poniżej, po pytaniach.

problemu/zapytania (e)

Głównym problemem z generatora jest znalezienie odpowiedniego num1 i num2, które sprawiają, że iteracyjne na całej możliwej sekwencji bitowej danej głębokości. Na końcu tej sekcji dołączam mój kod, który po prostu brutalnie wymusza to. Zakończy się w rozsądnym czasie do 12 bitów, możesz poczekać na wszystkie 16 bitów (do tej pory jest 5736 możliwych par, nabytych przez nocne pełne przeszukiwanie już jakiś czas temu) i możesz otrzymać kilka 20 bitów jeśli jesteś cierpliwy. Ale O (n^3) jest naprawdę paskudny ...

(Kto dostanie się znaleźć pierwszą pełną sekwencję 32bit?)

Inne ciekawe pytania, które pojawiają się:

• Zarówno num1 a num2 tylko wartości nieparzyste są w stanie wytworzyć pełne sekwencje. Czemu? To może nie być trudne (prosta logika, jak sądzę), ale nigdy nie udowodniłem tego.

• Istnieje własność dublowania wzdłuż num1 (wartość dodana), to znaczy, jeśli "a" z danym "b" num2 daje pełną sekwencję, to 2 uzupełnienie "a" (w danym bitu głębokość) z tą samą liczbą 2 jest również pełną sekwencją. Obserwowałem to tylko niezawodnie z wszystkimi pełnymi pokoleniami, które obliczyłem.

• Trzeci interesującą właściwością jest to, że dla wszystkich num1 & par num2 uzyskane sekwencje wydają się tworzyć odpowiednie koła, to znaczy co najmniej liczbę zero wydaje się zawsze część okręgu.Bez tej właściwości moje brutalne poszukiwanie sił umrze w nieskończonej pętli.

• Bonus: Czy ten PRNG był już wcześniej znany? (i właśnie to wymyśliłem)?

A oto brute force wyszukiwania Kod (C):

#define BITS 16 

#include "stdio.h" 
#include "stdlib.h" 

int main(void) 
{ 
unsigned int r; 
unsigned int c; 
unsigned int num1; 
unsigned int num2; 
unsigned int mc=0U; 

num1=1U; /* Only odd add values produce useful results */ 
do{ 
    num2=1U; /* Only odd eor values produce useful results */ 
    do{ 
    r= 0U; 
    c=~0U; 
    do{ 
    r=(((r>>(BITS-1)) & 1U)+r+r+num1)^num2; 
    r&=(1U<<(BITS-1)) | ((1U<<(BITS-1))-1U); /* 32bit safe */ 
    c++; 
    }while (r); 
    if (c>=mc){ 
    mc=c; 
    printf("Count-1: %08X, Num1(adc): %08X, Num2(eor): %08X\n", c, num1, num2); 
    } 
    num2+=2U; 
    num2&=(1U<<(BITS-1)) | ((1U<<(BITS-1))-1U); 
    }while(num2!=1U); 
    num1+=2U; 
    num1&=((1U<<(BITS-1))-1U); /* Do not check complements */ 
}while(num1!=1U); 

return 0; 
} 

to, aby pokazać, że działa, po każdej iteracji będzie wyjście para znaleźć, jeśli to długość sekwencji jest równy lub dłuższy niż poprzedni. Zmodyfikuj stałą BITS dla sekwencji innych głębokości.

Seed polowanie

Zrobiłem kilka wykresów odnoszących się do nasion. O to ładny obraz pokazujący wszystkie długości sekwencji 9bit:

Białe kropki są sekwencje pełnej długości, o osi X jest num1 (ADD), oś Y jest num2 (XOR), tym jaśniejszy kropka, im dłuższa sekwencja. Inna głębia bitowa wygląda bardzo podobnie we wzorcu: wszystkie wydają się być zerwane na szesnaście głównych płytek z dwoma wzorami powtarzającymi się z odbiciem lustrzanym. Podobieństwo płytek nie jest kompletne, np. Powyżej przekątnej od lewego górnego do dolnego - prawe jest wyraźnie widoczne, podczas gdy przeciwne jest nieobecne, ale dla sekwencji o pełnej długości ta właściwość wydaje się być wiarygodna.

Powołując się na to, że jest to możliwe, aby zmniejszyć pracę nawet więcej niż w poprzednich założeniach, ale to wciąż O (n^3) ...

Analiza wydajności

Od prąd najdłuższe sekwencje, które można wygenerować, to 24 bitów: na moim komputerze potrzeba około 5 godzin, aby wymusić na nim pełną 24-bitową sekwencję. Wciąż tak jest w przypadku prawdziwych testów PRNG, takich jak Diehard, więc od tej pory raczej podążałem własnym podejściem.

Po pierwsze, ważne jest zrozumienie roli generatora. W żadnym wypadku nie byłoby to bardzo dobrym generatorem dla jego prostoty, ale celem jest raczej szybkie tworzenie godnych liczb. W tym regionie, który nie wymaga operacji mnożenia/dzielenia, funkcja Galois LFSR może zapewniać podobną wydajność. Więc mój generator jest przydatny, jeśli jest w stanie przewyższyć ten.

Przeprowadzony przeze mnie test obejmował wszystkie generatory 16-bitowe. Wybrałem tę głębokość, ponieważ daje ona użyteczną długość sekwencji, podczas gdy liczby mogą być nadal dzielone na dwie 8-bitowe części, co umożliwia prezentowanie różnych bit-dokładnych wykresów do analizy wizualnej.

Rdzeń testów szukał korelacji wzdłuż poprzednich i obecnie generowanych liczb. W tym celu użyłem wykresów X: Y, gdzie poprzednia generacja była Y, obecna X, obie zostały rozbite na niskie/wysokie części, jak wyżej wspomniano dla dwóch wykresów. Stworzyłem program zdolny do kreślenia tych kroków w czasie rzeczywistym, aby umożliwić również z grubsza zbadanie, w jaki sposób liczby podążają za sobą, w jaki sposób wykresy się wypełniają. Tutaj oczywiście tylko wyniki końcowe są pokazane, ponieważ generatory przebiegły przez ich pełny cykl 2^16 lub 2^16-1 (Galois).

Wyjaśnienie pól:

• ilustracje składają 8x2 wykresy 256x256 czyni całkowity rozmiar obrazu 2048x512 (sprawdzić je w oryginalnym rozmiarze).

• Górny lewy wykres potwierdza, że ​​rzeczywiście została wydrukowana pełna sekwencja, to po prostu działka X = r % 256; Y = r/256;.

• Dolny lewy wykres pokazuje, że co druga cyfra jest drukowana tylko w ten sam sposób, co w górnej części, potwierdzając, że liczby występują w sposób racjonalnie losowy.

• Z drugiego wykresu górny rząd to wykres korelacji high-bajtowej. Pierwsza z nich używa poprzedniej generacji, następna pomija jedną liczbę (używa więc drugiej poprzedniej generacji) i tak dalej aż do 7. poprzedniej generacji.

• Od drugiego dolnego rzędu są nisko-bajtowe wykresy korelacji, zorganizowane w taki sam sposób jak powyżej.

generatora Galois, 0xB400 kranu ustawione

to generator znaleźć w Wikipedia Galois example. Jego wydajność nie jest najgorsza, ale wciąż zdecydowanie nie jest dobra.

generatorem Galois, 0xA55A kranu ustawić

Jednym z godnych Galois "nasiona" znalazłem. Zauważ, że niska część liczb 16-bitowych wydaje się dużo lepsza niż powyższe, jednak nie mogłem znaleźć żadnego "nasionka" Galois, które zmyliłoby wysoki bajt.

Mój generator, 0x7F25 (ADC), 0x00DB (EOR) nasienie

Jest to najlepszy z moich generatorów gdzie bajt wartości EOR wynosi zero. Ograniczenie wysokiego bajtu jest użyteczne na komputerach 8-bitowych, ponieważ wtedy to obliczenie można pominąć dla mniejszego kodu i szybciej wykonać, jeśli utrata wydajności losowości jest niedroga.

Mój generator, 0x778B (ADC), 0x4A8B (EOR) nasienie

Jest to jeden z bardzo dobrej jakości nasion przez moich pomiarów.

Aby znaleźć ziarna o dobrej korelacji, I zbudował mały program, który będzie analizować je w pewnym stopniu, ten sam sposób dla Galois i kopalni. Przykłady "dobrej jakości" zostały określone przez ten program, a następnie przetestowałem kilka z nich i wybrałem jedną z nich.

Niektóre wnioski:

• Generator Galois wydaje się być bardziej sztywna niż moja. Na wszystkich wykresach korelacji można zaobserwować określone wzory geometryczne (niektóre nasiona dają wzory "szachownicy", nie pokazane tutaj), nawet jeśli nie składają się z linii. Mój generator również pokazuje wzory, ale z większą liczbą generacji stają się mniej zdefiniowane.

• Część wyniku generatora Galois, który zawiera bity w górnym bajcie, wydaje się być wrodzona sztywnością, której właściwość wydaje się być nieobecna w moim generatorze. Jest to słabe założenie, ale prawdopodobnie wymaga więcej badań (aby sprawdzić, czy tak jest zawsze z generatorem Galois, a nie z kopalnią w innych kombinacjach bitów).

• Generator Galois nie ma zera (maksymalny okres to 2^16-1).

• W tej chwili niemożliwe jest wygenerowanie dobrego zestawu nasion dla mojego generatora powyżej 20 bitów.

Później mógłbym dostać w tej kwestii głębszej stara się przetestować generator z Dieharda, ale jak na razie brak zdolności generowania wystarczająco duże ziarno to uniemożliwia.

Answer 1

Jest to forma nieliniowego rejestru sprzężenia zwrotnego. Nie wiem, czy został użyty jako taki, ale przypomina nieco rejestry sprzężenia zwrotnego liniowego. Przeczytaj tę stronę Wikipedia jako wprowadzenie do LSFR. Są często używane w generowaniu liczb pseudolosowych.

Jednak twój generator liczb pseudolosowych jest z natury zły, ponieważ istnieje liniowa korelacja pomiędzy bitem o najwyższej kolejności wcześniej wygenerowanej liczby i bitu najniższego rzędu liczby wygenerowanej w następnej kolejności. Przesuwasz najwyższy bit B na zewnątrz, a następnie bit najmniejszego rzędu dla nowej liczby będzie XOR lub B, bit najmniejszego rzędu stałej dodatku num1 i bit najmniejszego rzędu XORed stałej liczby 2, ponieważ dodanie binarne jest równoważne do bitu wyłącznego lub na najniższym poziomie. Najprawdopodobniej twój PRNG ma inne podobne braki. Tworzenie dobrych PRNG jest trudne.

Muszę jednak przyznać, że kod C64 jest przyjemnie zwarty!