Błąd w publikacji "Pseudo-random number generators based on the Collatz conjecture"

Podzielność. Reszty z dzielenia. Kongruencje. Systemy pozycyjne. Równania diofantyczne. Liczby pierwsze i względnie pierwsze. NWW i NWD.
matemix
Użytkownik
Użytkownik
Posty: 465
Rejestracja: 10 cze 2008, o 19:38
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 12 razy
Pomógł: 1 raz

Błąd w publikacji "Pseudo-random number generators based on the Collatz conjecture"

Post autor: matemix »

Publikacja "Pseudo-random number generators based on the Collatz conjecture", David Xu, Dan E. Tamir jest możliwa do zobaczenia tu:

Kod: Zaznacz cały

https://sci-hub.se/10.1007/s41870-019-00307-9


Autorzy zaproponowali tam kilka generatorów liczb pseudolosowych opartych o ciągi Collatza. Najlepszy z nich wydaje się algorytm nr 1:

Niech \(\displaystyle{ b(n) = n >> (\lceil \log_{2}(n) \rceil - 95)}\) (operacja >> to przesunięcie bitowe, robimy to w celu konwersji liczby większej niż 95-bitowa na 95-bitową, przesuwamy bity w prawo o tyle miejsc ile mamy nadwyżkowych bitów).

Niech ziarno \(\displaystyle{ n > 2^{95}}\) oraz:

\(\displaystyle{ a_{0}=0}\)

\(\displaystyle{ a_{i} = (b(n+a_{i-1}) \oplus E(n+a_{i-1})[:95]+a_{i-1}) \mod 2^{128}}\)

gdzie \(\displaystyle{ \oplus}\) to XOR, natomiast \(\displaystyle{ E(x)}\), to wektor kodujący \(\displaystyle{ x}\) (wyjaśnię na końcu). Natomiast zapis \(\displaystyle{ x[:k]}\) oznacza pierwsze \(\displaystyle{ k}\) bitów wektora \(\displaystyle{ x}\).

Sekwencję liczb pseudolosowych otrzymujemy biorąc kolejne \(\displaystyle{ E(n+a_{0}),E(n+a_{1}),E(n+a_{2}),...}\).

Autorzy twierdzą, że generator ten będzie miał okres co najmniej \(\displaystyle{ 2^{32}}\) i podają dowód w publikacji. Nie będę go tutaj przepisywał, chyba, że ktoś potrzebuje pomocy w tłumaczeniu z j. angielskiego.

Problem w tym, że dowód jest błędny. Można znaleźć przypadek takich ziaren, że generator wpadnie w krótki cykl o długości zaledwie \(\displaystyle{ 1}\) przed wygenerowaniem różnych \(\displaystyle{ 2^{32}}\) liczb, co ma być gwarantowane według autorów. Generalnie za okres generatora przyjmuje się taką liczbę kolejno generowanych liczb pseudolosowych, że zapętlenie nastąpi dopiero po ich wygenerowaniu (wtedy generator powtórzy jeszcze raz tę samą sekwencję). Niedopuszczalne jest zatem aby generator przed wygenerowaniem przykładowo \(\displaystyle{ 2^{32}}\) deklarowanych różnych liczb pseudolosowych o wysokiej jakości wpadł w cykl typu:

\(\displaystyle{ 1,1,1,1,...}\)

To kompletnie kompromituje taki generator i czyni go nieużytecznym. Istnieją generatory, które mają gwarantowany okres, choćby generatory LCG (na mocy twierdzenia Hull–Dobell). Ale mogą też istnieć generatory, w przypadku których w zależności od ziarna możemy tylko szacować spodziewany okres i liczbę iteracji, po których liczby wpadną w cykl. Przykładem jest zaproponowany przez Mellisę O'Neil Meddle Square:

Kod: Zaznacz cały

https://www.pcg-random.org/posts/too-big-to-fail.html


Z teorii Random Mappings wiemy, że przykładowo spodziewania długość cyklu dla losowego ziarna będzie wynosić w takim N-bitowym generatorze \(\displaystyle{ \sqrt{ \pi \cdot \frac {N}{8}}}\). Ale zawsze istnieje niezerowe prawdopodobieństwo, że dla jakiegoś startowego ziarna trafimy pechowo na jakiś bardzo krótki cykl i generator przed wygenerowaniem różnych liczb zacznie powtarzać liczby w jakiejś krótkiej sekwencji.

Ale przechodząc do rzeczy, ziarna, które dają wyniki skutkujące następującymi wynikami (od pierwszej iteracji dostajemy cykl o długości jeden):
Ukryta treść:    
To liczby postaci:

\(\displaystyle{ 2^{x}-1}\)

Oczywiście zgodnie z warunkiem podanym przez autorów muszą być one większe niż \(\displaystyle{ 2^{95}}\). Kolejnym nieużytecznym ziarnem jest \(\displaystyle{ 2^{95}+1}\), tutaj też bardzo szybko, po \(\displaystyle{ 4}\) iteracjach, dostajemy cykl o długości jeden. Świadczy to o tym, że dowód autorów publikacji jest błędny. Pytanie, czy istnieje więcej ziaren, które powodują nieprawidłowe działanie generatora? W przypadku wymienionych ziaren ciągi Collatza zachowują się dosyć trywialnie przez pierwsze iteracje i można sobie odtworzyć przyczynę takiego zachowania generatora. Ale skąd pewność, że dla innych ziaren, które będą powodować bardziej skomplikowane wyniki, mimo wszystko również nie zaobserwujemy takich trywialnych cykli? Jeżeli dowód nie zwrócił uwagi na te wyjątki, jest błędny, a wyjątków może być więcej.

Czy mam rację? Gdyby ktoś chciał sprawdzić to osobiście podaję kod w pythonie, którym się posłużyłem:
Ukryta treść:    
Dodano po 18 minutach 19 sekundach:
PS Wektor kodujący obliczamy iterując kolejno wyrazy w ciągu Collatza:

\(\displaystyle{ c_{n+1} = \begin{cases} \frac{c_n}{2} &\text{gdy }c_n \text{ jest parzyste} \\ 1,5c_n+0,5 &\text{gdy } c_n \text{ jest nieparzyste} \end{cases}}\)

Np. kolejne iteracje dla liczby startowej \(\displaystyle{ 26}\) to:

\(\displaystyle{ 13,20,10,5,8,...}\)

w zależności od tego, czy wyrazy ciągu rosły, czy malały, przyporządkowujemy im jedynkę lub zero: \(\displaystyle{ 0,1,0,0,1}\). I tak oto otrzymujemy liczbę binarną \(\displaystyle{ 01001=1001}\). Wektory kodujące obliczamy dla \(\displaystyle{ 95}\) kolejnych iteracji, zgodnie z definicją generatora, otrzymując w ten sposób 95-bitowe liczby.

Dodano po 2 dniach 11 godzinach 31 minutach 39 sekundach:
A jednak popełniłem błąd w implementacji. W Pythonie funkcja math.log(x,2) nie liczy poprawnie logarytmu dla dużych liczb (prawdopodobnie poprawnie radzi sobie tylko z liczbami co najwyżej 32-bitowymi). Oznacza to, że na przykład dla wartości \(\displaystyle{ x=2^{95}-1}\) daje wartość minimalnie większą niż \(\displaystyle{ 95}\).

Musiałem napisać własną funkcję do liczenia logarytmu - a właściwie do liczenia od razu \(\displaystyle{ \lceil \log_{2}(x) \rceil}\), jak to wymagane jest w algorytmie autorów. Po zmianie wygląda na to, że wszystko jest w porządku z ziarnem \(\displaystyle{ 2^{95}+1}\), ale ziarna postaci \(\displaystyle{ 2^{x}-1}\) nadal dają te same wyniki, co wcześniej. Kod:
Ukryta treść:    
Ostatnio zmieniony 14 lis 2021, o 21:54 przez Jan Kraszewski, łącznie zmieniany 3 razy.
Powód: Poprawa wiadomości.
ODPOWIEDZ