bazy potęgowe (modyfikacja podejścia do barokowego sa)
Wlodzimierz Holsztynski
kosztem większego trudu, włożonego
w zakodowanie algorytmu.
Czy zysk będzie dostatecznie dramatyczny
(by uzasadnić trud)? Nie wiem. Zajrzyjcie
przynajmniej do mojego PPS, z końca listu
(nie chodzi o Polską Partię Socjalistyczną).
***
Najprostszą przestrzenią konfiguracyjną
dla barokoowego s.a. wydaje się być
C(wkd[supp]). Przy tym należy ograniczać
się do wkd[supp] typu TWR; inne są stratą
czasu. Obaj, Artur i ja, mieliśmy ochotę na
wydajniejsze przestrzenie. Sam zaproponowałem,
ale mało entuzjastycznie, ograniczanie
się do konfiguracji v takich, że suma wykładników
sd(P^v)_supp jest niemniejsza od sumy samego v.
Mój brak zapału brał się z tego, że opisane
sprawdzanie konfiguracji wymagało by dodatkowych
obliczeń, więc może jest prościej i bezpieczniej
wykonywać ruchy po prostu w C(wkd).
Tym razem zaproponuję coś, co będzie
czystym zyskiem w porównaniu do TWRów,
tak jak TWRy były czystym zyskiem
w porównaniu z dowolnymi bazami barokowymi.
***
Ustalmy dwa skończone zbiory liczb
pierwszych, Q oraz Q', gdzie Q jest
zawarte w Q' (w praktyce, na ogół,
będziemy mieć Q'=Q).
Zbiór Q po staremu jest zbiorem
wartości ciągu prime[0], prime[1], ...:
Q = { prime[j] : j < pDim }
Konfiguracjami (wierzchołkami) będą po
staremu funkcje
v : {0 ... pDim-1} --> {0 1 ...}
Interpretujemy v też po staremu: mamy
prime[pDim]; patrząc na v myślimy o
liczbie naturalnej
P^v := Prod( prime[j] ^ v[j] : j < pDim)
(z nadzieją, że jest barokowa :-).
Natomiast ruchy będą specjalne, oparte na
potęgowej bazie, co w efekcie będzie oznaczało
mniejszą przestrzeń konfiguracji--już wyjaśniam.
Najpierw zapewnić chcę, że choć przestrzeń będzie
mniejsza, to z żadnych liczb barokowych nie
zrezygnujemy (chyba że zdecydujemy się polować
na specjalne, ale to już jest inna sprawa).
Potęgowa baza oprócz prime[pDim] będzie miała
jeszcze dwa "arrays": base[ppow] oraz wyk[ppow],
tego samego wymiaru ppow ("prime powers").
Liczby base[j] będą stanowiły niemalejący ciąg,
z powórzeniami!, liczb z Q, a raczej ich indeksów.
Zatem base[] może wyglądać mniej więcej tak:
0 0 0 0 0 0 0 1 1 1 1 1 2 2 3 3 3 3 4 4 5 6 6 7 8 8...
Ruch od v do v' będzie po prostu polegal na losowaniu
indeksu m < ppow. W wyniku ruchu, wykładnik
v[base[m]], w konfiguracji v, zostanie zastąpiony
przez nowy: v'[base[m]] = wyk[m]. Gdyby okazało się,
że nie prowadzi to do zmiany, bo wyk[m] = v[base[m]],
to losowo wybierze się dowolny inny wykładnik wyk[m'],
ale tej samej liczby pierwszej co wcześniej:
p := base[m'] = base[m]
(jeżeli byłby tylko jeden inny wykładnik, to będzie
wybrany z pewnością).
Widzimy, że ruchy są równie proste jak
wcześniej.
***************
Chociaż ruchy są dalej proste, to bazę danych
algorytmu nieco skomplikowalem. Dzięki temu
mam lepszą kontrolę, bo dopuszczę tylko wybrane
bazy potęgowe.
Należy o bazie potęgowej myśleć jako o kolekcji
potęg liczb pierwszych p^a = base[j] ^ wyk[j].
Musi ona spełniać 2 warunki. Jeden TWRowski:
(i) każdy element p^a bazy potęgowej musi
być rekomendowany przez pozostałe, czyli
musi być dzielnikiem sumy dzielników
produktów innych elementów q^b naszej bazy,
przy czym każde q może wystąpić w tym
iloczynie co najwyżej raz.
Drugi warunek jest nowy;
(ii) jedynymi dzielnikami pierwszymi sd(p^a),
dla elementu bazy potęgowej, p^a, są
wyłącznie elementy zbioru Q'.
Tak więc możemy powiedzieć, że
warunek (ii) usuwa pewne konfiguracje z C(wkd).
*****
Na ogół nasz zbiór Q będzie miał między innymi
wszystkie liczby pierwsze mniejsze od 200 (nawet
od 1000). Jeżeli nie, to możemy je dodać do Q'.
Wtedy warunek (ii) nie ominie żadnej liczby
barokowej o współczynniku mniejszym od 211 --
takie liczby barokowe i tak będą poza zasięgiem
naszych rachunków.
***
Powinienem podać metody na uzykiwanie
potęgowych baz. Niepokoi mnie moja przerwa
w programowaniu s.a. Chcę najpierw przeprowadzić
test pewnych ruchów (wciąż czysto losowo, jeszcze
bez temperatury), po czym już uczciwie wziąć się
za s.a. i zakończyć pierwszą fazę programowania
pełnym algorytmem, jego pierwszą wersją. Potem
już będzie więcej przyjemności (mam nadzieję :-).
Pozdrawiam,
Włodek
PS. Lada moment wytrę Windows i załaduję
ubuntu (wersja unixa) na moje drugie PC
(które okropnie huczy, bo trochę jest stare;
ale jare--to chyba dobra maszyna :-)
PPS. Jeżeli znacie pakiet z wielocyfrową
arytmetyką dla C++, który taka ciapa jak
ja potrafi ściągnąć i używać, to dajcie,
proszę, znać. Może być na Maca, może
na ubuntu (:-). Czy na ubuntu łatwo ściągnąć
te inne Wasze cuda-cudeńka Artura
i Mirka?