Kiedy nie wiadomo co robić, zaczynam szukać innych form, to było granie w gry na sucho, w edytorze tekstu. Gdyż myślałem, że z teorii liczb nic już nie wycisnę. Myliłem się.
Powstał nowy algorytm. Jest bardzo dobry na maszyny wieloprocesorowe, ma stosunkowo mało przypadków do sprawdzenia, i do końca nie wiem jak działa.
Ustalmy 3 procesory. Pierwszy delikatnie przekształca liczbę faktoryzowaną n zapisaną w postaci trójki
n = a*b+c ,
przy czym a rośnie od parzystej liczby ograniczajacej pierwiastek z n z góry do podwojonej tej wartości po liczbach parzystych. Ma zatem 2^i przypadków, gdzie 2^(2i) < n < 2^(2i+1).
Przekształcenie polega na konwersji na system o 2 wyższy, czyli dany tożsamościami:
a*b+c = (a+2)*d+e, gdzie d in {b-2, b-1, b} w zależności od znaku (c-2b).
Dokładniej:
a*b+c = (a+2)*b + (c-2b), -1 < c-2b;
a*b+c = (a+2)*(b-1) + (c-2b+a+2), -a-3 < c-2b <0;
a*b+c = (a+2)*(b-2) + (c-2b+2(a+2)), c-2b < -a-2.
Np. jeśli n jest postaci n = 12441^2+987, to a=12442, b=12440, c=987-12441+12442 = 988; następna wartość jest równa a=12444, zaś b i c są znajdowane według wzoru (tu jest b=12438).
Dla n postaci n=12442^2+c przyjmujemy a=12444, pozostałe są odpowiednio dopasowane, by b było bliskie a, zaś c jest resztą.
Wartości (a,b,c) są przekazywane drugiemu procesorowi.
Drugi z procesorów przyjmujący (a,b,c), gdzie a jest parzyste, usiłuje dokonać konwersji, w której a jest połowione, b jest podwajane, zaś c w zależności od znaku (c<a) jest albo pozostawiane, albo zmniejszane o a, z równoczesnym zwiększeniem b o 1. Wzorami
(2a)*b+c = a*(2b)+c, c<a;
(2a)*b+c = a*(2b+1)+(c-a), c>a-1.
Pętlę kończymy, gdy wartość zmniejszana a jest nieparzysta. Mamy do czynienia co najwyżej z logarytmem binarnym z a przypadków (b jest nie większe niż podwojony sufit pierwiastka kwadratowego z n). Ciąg wartości c jest ciągiem nierosnącym.
Watości (a,c) oraz (b,c) są przesyłane do trzeciego z procesorów. Jedna z tych wartości jest stosunkowo mała.
Trzeci procesor ma najwięcej roboty. Sprawdza największy wspólny dzielnik przesłanych wartości, jeśli jest on większy od 1, znaleziona wartość jest zarazem dzielnikiem liczby n.
Bardzo podobnie wygląda cecha podzielności przez 9 lub 11, która stała się prekursorem algorytmu. Jeśli cyfry liczby dwucyfrowej zapisanej w systemie niedziesiątkowej są równe, to podstawa systemu zwiększona o 1 jest dzielnikiem liczby.
W praktyce nie zawsze musimy przesyłać dane do trzeciego procesora. Ale musimy je przesłać, gdy następuje zmiana wartości c, które nie jest zbyt małe. Przy c=1 możemy zignorować ten krok, przy c pierwszych przyspieszyć sprawdzanie testując podzielność przez c.
Przykładowy fragment rozkładu znajdujący dzielnik:
n = a*b+c = (2990 * 2987 + 2923) = 8934053
Procesor pierwszy: przelicza od a=2990 do a=5980:
(2990 , 2987 , 2923 ) = (2992 , 2985 , 2933) = ...
= (4348 , 2054 , 3261) = ...
Procesor drugi (4348, 2054, 3261):
(4348 , 2054 , 3261) = (2174 , 4109 , 1087) = (1087 , 8219 , 0)
Procesor trzeci:
nwd(4348, 3261) = 1;
nwd(2054, 3261) = 1;
nwd(2174, 1087) = 1087, znaleziony dzielnik 1087
Zaś 8934053 = 1087 * 8219.
Pętla działania procesora drugiego tworzy 'grzebień'. Tzn. dla połowy przypadków jest jedna iteracja, każda dłuższa pętla sąsiaduje z dwoma najkrótszymi. Krotność iteracji tworzy podciągi (1, 2, 1, 4, 1, 2, 1, 8, 1, 2, 1, 4, ... ).
Algorytm powstał, kiedy połączyłem cechy podzielności przez liczby sąsiadujące z podstawą systemu, konwersje o potęgi dwójki oraz konwersje o 2.
Brak komentarzy:
Prześlij komentarz