Przed burzami miewam czasem ciekawsze pomysły. Połączyłem metodę faktoryzacji, która sprawdza od razu duże i małe dzielniki opublikowaną 7 sierpnia 2013 roku
'Faktoryzacja, przepis z prostymi przekształceniami'
z jedną z pierwszych faktoryzacji przez konwersję na inny system.
Okazało się wtedy, że nie muszę sprawdzać nie tylko liczb parzystych jako kandydatów na dzielniki (po wyłączeniu 2 na pewno nie są dzielnikami), ale mogę nawet pomijać wszystkich kandydatów mniejszych niż około 1/3 pierwiastka kwadratowego kosztem około log_3 n obliczeń nwd.
Łącznie można pominąć n/6 wartości szukając dzielników liczby n. Dzielnik znajdziemy przeliczając nie więcej niż trzykrotność jego wartości.
W poniższym sposobie dzielnik d pojawia się co d wartości, na kolejny ślad obecności trafimy nie później niż zmiejszając podstawę systemu o 3d.
Dodatkowo, dla bardzo dużych liczb jesteśmy w stanie łatwo oszacować na podstawie reszty, że nie ma blisko dzielników, lecz nie można tego łatwo sformalizować. Praktycznie można przyspieszyć stosując w niektórych przypadkach konwersję nie o 2, lecz o 6. Tutaj ignorowane.
Lemat 1. Jeśli k jest względnie pierwsze z a, to
nwd(a,b) = nwd(a, k*b).
Jeśli jest wspólny dzielnik d = nwd(a,b), to d dzieli a oraz b, zatem dzieli także k*b.
Jeśli d = nwd(a, k*b), to d dzieli równocześnie a oraz k*b. Skoro a oraz k są względnie pierwsze, zatem d dzieli b. Stąd nwd(a,b) = d.
Lemat 2. Jeśli n = ap^2+bp+c, to dzielnika n można szukać jako nwd(p,c) dla pewnego p.
Zapiszmy n nieco inaczej n = (ap+b)p+c. Liczba się dzieli przez d, gdy c się dzieli przez d oraz iloczyn (ap+b)p się dzieli przez d. Ponieważ p jest modyfikowane, można się ograniczyć do szukania tylko nwd(p,c).
Ciekawe rezultaty są wtedy, gdy d jest małą liczbą, np. 3. Wtedy co trzecia podstawa jest podzielna przez 3, co piąta jest podzielna przez 5. Po wyeliminowaniu 2 jako dzielnika podstawy systemów są nieparzyste.
Konwersja na system p, kiedy podstawa systemu jest równa p+2 dla liczb 'trójcyfrowych' n = ap^2+bp+c wygląda następująco:
a b+2a
a b+4a c+(b+2a)
co można zapisać równaniami:
a'=a;
b'=b+4a;
c'=c+(b+2a);
Jeśli którakolwiek z b', c' jest większa niż p, wykonujemy operacje (c'-=p; b'++;) oraz (b'-=p; a'++;) odpowiednio. Nie więcej niż dwukrotnie każda.
W praktyce, zaczynając od podstawy będącej liczbą nieparzystą mniejszą od pierwiastka z n, mamy tak długo do czynienia z trzema 'cyframi', że trzecia część pierwiastka kwadratowego z n jest jeszcze liczbą 'trójcyfrową'.
Algorytm:
Inicjacja: niech p będzie największą liczbą nieparzystą mniejszą niż pierwiastek kwadratowy z liczby nieparzystej n. Przedstawiamy liczbę n = p^2+bp+c, gdzie b jest mniejsze niż 4 oraz -1<c<p. Zapamiętujemy podłogę z p/3 jako x.
Powtarzamy w pętli dopóki nie znajdziemy dzielnika:
Jeżeli c jest zerem, dzielnikiem jest p.
Jeśli p jest podzielne przez 3, szukamy liczby q takiej że p=q*3^i, gdzie i jest całkowite oraz 3 nie dzieli q. Obliczamy d = nwd(c,q). Jeśli d>1, d jest dzielnikiem.
Zmniejszamy p o 2 i porównujemy z x. Jeśli p>x wracamy do pętli, w przeciwnym przypadku n jest pierwsza.
Ponieważ co szóste p jest nieparzyste podzielne przez 3, w algorytmie przyjmujemy za p tylko wartości nieparzyste, zatem co trzecie p jest podzielne, a na dodatek niech t=p/3. Wtedy co trzecią iterację mamy wartość t-2, zapamiętując je nie musimy dzielić przez 3 więcej niż raz, a następnie zastosować funkcję rekursywną: t[0]=p/3, t[j+1] = 1/3 t[j],
zmienna wewnętrzna i odmierza co 3 wejście, inicjowana jest jako reszta i=2 (t[j] = 3r+1), i=1 (t[j] = 3r+2), i=0 (t[j] = 3r), r naturalne;
new f( t[j] ): { t[j+1] = floor t[j]/3; i=3-(t[j]%3)); }, t[j]>1
tworzy t[j+1].ty element. Funkcja zwraca dodatnią wartość nwd albo ujemną wiadomość 'jest reszta z dzielenia przez 3':
f (t[j])(i) = {
i--;
if( 0<i) return -i; else {
i = 3;
t[j] -= 2;
k = f(t[j+1]);
if(0<k) return k; else return nwd(t[j],c);
}
};
Złożoność.
Konwersje mają złożoność arytmetyczną stałą, pamięciowo liniową.
Obliczanie nwd ma najgorszą złożoność, i to ono decyduje o złożoności algorytmu. Przy okazji, wartości dla nwd są ograniczone, jedna przez p, druga przez p/3. Obydwie mniejsze niż pierwiastek z n.
Kontrprzykład numeryczny, liczba pierwsza n = 1447 = 38^2+3
a b c p t[j] nwd(d,c)
1 0 3 38
1 2 4 37 // algorytm
1 6 12 35
1 10 28 33 t[0]=11 nwd(11,28)=1
1 15 21 31
1 20 26 29
1 26 16 27 t[0]=9 t[1]=3 t[2]=1 nwd(1,16)=1
2 7 22 25
2 16 11 23
3 5 19 21 t[0]=7 nwd(7,19)=1
4 0 3 19
5 0 2 17
6 6 7 15 t[0]=5 nwd(5,7)=1
8 7 4 13
Wszystkie możliwe liczby nieparzyste uwzględnione, od 13 do 37 przy p, mniejsze przy liczeniu nwd. Jest przeliczonych 13 spośród 19 wartości nieparzystych (2/3 oraz nadmiar). Pozostałe uwzględnione są w czterech nwd.
algorytmy, pomysły na rozkład liczb i arytmetykę, także systemów niedziesiątkowych; elementy programowania pod DOSem
30 maja 2014
21 maja 2014
Wskażnik na funkcję, ale nie na każdą
Spróbowałem, czy można wymieniać ciało metody klasy za pomocą wskaźnika.
Pierwsze próby robił Koza programowaniem genetycznym w LISPie. (Algorytmy genetyczne + struktury danych = programy ewolucyjne Z. Michalewicza)
Kompilator gcc nie przepuścił. Traktował jako konwersję 'int (*)(int)' na 'int (obiekt::*)(int)' i nawet reinterpret_cast nie pomógł. Nie udało się wewnątrz klasy odwoływać się do jej metod wskaźnikiem.
Kilka dni i poddałem się. Nie zamierzam rezygnować z obiektów. Ale mam coraz większą ochotę blokować lub fałszować sprawdzanie typów.
Czyli coraz dalej od standardów.
Na razie sposobem na zmianę ciała funkcji w czasie działania programu w C++ wydaje mi się interpretacja ciągu tekstowego funktorów.
Pierwsze próby robił Koza programowaniem genetycznym w LISPie. (Algorytmy genetyczne + struktury danych = programy ewolucyjne Z. Michalewicza)
Kompilator gcc nie przepuścił. Traktował jako konwersję 'int (*)(int)' na 'int (obiekt::*)(int)' i nawet reinterpret_cast nie pomógł. Nie udało się wewnątrz klasy odwoływać się do jej metod wskaźnikiem.
Kilka dni i poddałem się. Nie zamierzam rezygnować z obiektów. Ale mam coraz większą ochotę blokować lub fałszować sprawdzanie typów.
Czyli coraz dalej od standardów.
Na razie sposobem na zmianę ciała funkcji w czasie działania programu w C++ wydaje mi się interpretacja ciągu tekstowego funktorów.
Subskrybuj:
Posty (Atom)