Ciekawa sprawa, ilekroć staram się o pracę programisty C++, w najbliższym tygodniu mam odcięty dostęp do internetu (na ogół spalone łącze).
Wydumałem algorytm sortowania tablicy, wymaga on jeszcze sprawdzenia praktycznego. Wydaje mi się, że w części przypadków nie ustąpi szybkości działania quicksort. Zwłaszcza dla danych częściowo posortowanych. Wymaga dodatkowych tablic rozmiaru początkowego, chociaż wystarczy jedna z zamianą tablic żródła i docelowej po każdej iteracji. Tablica zostanie całkowicie wypełniona dopiero w ostatniej iteracji algorytmu. Jest to silnie uzależnione od danych. W przypadku danych monotonicznych, nawet zaburzonych elementem skrajnym, wystarcza jedna iteracja.
26 grudnia 2007
26 listopada 2007
Heurystyka rozkładu na czynniki pierwsze
Heurystyki rozkładu liczb złożonych służą do szybkiego znajdowania dzielników pierwszych dużych liczb naturalnych. Mając daną liczbę N próbują zwrócić jej dzielnik q. Spotkałem test Rabina-Millera do sprawdzania, czy liczba jest pierwsza. Algorytm ten stał się punktem wyjścia do opracowania metody, która okazała się bardzo podobna do heurystyki ro Pollarda, przynajmniej w interpretacji graficznej.
Z algorytmu faktoryzacji ro Pollarda wziąłem część oznaczeń:
http://pl.wikipedia.org/wiki/Algorytm_faktoryzacji_rho_Pollarda
Oryginalny test Rabina-Millera jest tu:
http://pl.wikipedia.org/wiki/Test_Millera-Rabina
Algorytm znalezienia rozkładu liczby pierwszej N na czynniki.
1.Wyłączam z liczby N wielokrotności 2, by otrzymać liczbę nieparzystą
2.Ustalam ziarno – liczbę z zakresu {2, ..., (N-1)/2}
3.Obliczam
z_{i+1} = min {z_i^2 mod N, -z_i^2 mod N}
dopóki nie uzyskam 0, 1, albo powstanie cykl a_i
4.Gdy z=1 algorytm zawodzi, należy wrócić do 3 z nowym ziarnem
5.Gdy istnieje cykl (a_i), obliczane jest b=nwd(a, N) dla dowolnego elementu a cyklu, wtedy b jest dzielnikiem N, jeśli b=1, należy wrócić do 3 wybierając nowe ziarno nie należące do cyklu
6.Gdy z=0, ziarno jest dzielnikiem N
7.Jeśli po przejrzeniu wszystkich ziaren z zakresu otrzymywane są cykle z nwd(a,N)=1 albo ciągi jedynek (1), liczba N jest pierwsza
Jako jeden z pierwszych kroków można przeprowadzić pierwszy fragment testu pierwszości Rabina-Millera. Wynik pozytywny dla co najmniej dwu ziaren pozwala pominąć szukanie dzielników liczby pierwszej. Wykorzystanie ziarna inicjowanego a^m zamiast a powoduje skrócenie ogona, dzięki czemu cykl jest szybciej uzyskiwany. Następuje zmniejszenie krotności wartości występujących w cyklach,.
Ze względu na symetrie ziarna z oraz N-z dają te same wartości, przy czym dla N-1 od pierwszej iteracji otrzymywane są same jedynki.
Przykład 1: liczba złożona 57 = 3*19
Liczba 57-1 = 56 = 2^3*7. Spodziewane są zatem cykle zaczynające się nie dalej niż w 3 iteracji. Jeżeli ziarna inicjujemy nie przez z^7, lecz przez z, wyniki dają cykle przesunięte.
Ziarno z=2 daje wartości 14 (2^7 mod 57), 25 (14^2 mod 57), 2 (-(25^2) mod 57), 4, 16, 28, 14 (-28^2 mod 57), czyli okres 6 od pierwszej pozycji. Wspólny dzielnik nwd(2,57)=1, zmieniamy ziarno.
Ziarno z=3 daje kolejno wartości: 21, 15, 3, 9, 24, 6, 21, okres taki sam od pierwszej pozycji, nwd(3,57) = 3 jest jednym z dzielników liczby początkowej.
Dla innych ziaren okresy wynoszą odpowiednio 7: (7,8), 12: (12,27), 18: (18), 19:(19), występuje także 20: (1)!
Przykład 2: liczba złożona 49 = 7^2
Ponieważ 48 = 2^4*3, spodziewane są cykle zaczynające się nie dalej niż od 4.tej iteracji. Występują następujące cykle: (0), (1), (6,13,22), (8,15,20). Dla ziarna z=18 uzyskiwana jest 1 sugerująca, że liczba jest pierwsza!
Kiedy z nie jest inicjowane potęgą z^3, pojawiają się dodatkowe cykle długości 6, np. (2,4,16,11,23,10). Wtedy z ziarnem 18 nie ma kłopotu, tworzy się cykl (18,19).
Przykład 3: liczba pierwsza 53
Rozkład 52=2^2*13.
Występują 2 cykle: (1) oraz (4,16,9,25,11,15,13,10,6,17,24,7).
Kiedy z nie jest inicjowane potęgą, cykl 12-wyrazowy występuje dla większości ziaren.
Z algorytmu faktoryzacji ro Pollarda wziąłem część oznaczeń:
http://pl.wikipedia.org/wiki/Algorytm_faktoryzacji_rho_Pollarda
Oryginalny test Rabina-Millera jest tu:
http://pl.wikipedia.org/wiki/Test_Millera-Rabina
Algorytm znalezienia rozkładu liczby pierwszej N na czynniki.
1.Wyłączam z liczby N wielokrotności 2, by otrzymać liczbę nieparzystą
2.Ustalam ziarno – liczbę z zakresu {2, ..., (N-1)/2}
3.Obliczam
z_{i+1} = min {z_i^2 mod N, -z_i^2 mod N}
dopóki nie uzyskam 0, 1, albo powstanie cykl a_i
4.Gdy z=1 algorytm zawodzi, należy wrócić do 3 z nowym ziarnem
5.Gdy istnieje cykl (a_i), obliczane jest b=nwd(a, N) dla dowolnego elementu a cyklu, wtedy b jest dzielnikiem N, jeśli b=1, należy wrócić do 3 wybierając nowe ziarno nie należące do cyklu
6.Gdy z=0, ziarno jest dzielnikiem N
7.Jeśli po przejrzeniu wszystkich ziaren z zakresu otrzymywane są cykle z nwd(a,N)=1 albo ciągi jedynek (1), liczba N jest pierwsza
Jako jeden z pierwszych kroków można przeprowadzić pierwszy fragment testu pierwszości Rabina-Millera. Wynik pozytywny dla co najmniej dwu ziaren pozwala pominąć szukanie dzielników liczby pierwszej. Wykorzystanie ziarna inicjowanego a^m zamiast a powoduje skrócenie ogona, dzięki czemu cykl jest szybciej uzyskiwany. Następuje zmniejszenie krotności wartości występujących w cyklach,.
Ze względu na symetrie ziarna z oraz N-z dają te same wartości, przy czym dla N-1 od pierwszej iteracji otrzymywane są same jedynki.
Przykład 1: liczba złożona 57 = 3*19
Liczba 57-1 = 56 = 2^3*7. Spodziewane są zatem cykle zaczynające się nie dalej niż w 3 iteracji. Jeżeli ziarna inicjujemy nie przez z^7, lecz przez z, wyniki dają cykle przesunięte.
Ziarno z=2 daje wartości 14 (2^7 mod 57), 25 (14^2 mod 57), 2 (-(25^2) mod 57), 4, 16, 28, 14 (-28^2 mod 57), czyli okres 6 od pierwszej pozycji. Wspólny dzielnik nwd(2,57)=1, zmieniamy ziarno.
Ziarno z=3 daje kolejno wartości: 21, 15, 3, 9, 24, 6, 21, okres taki sam od pierwszej pozycji, nwd(3,57) = 3 jest jednym z dzielników liczby początkowej.
Dla innych ziaren okresy wynoszą odpowiednio 7: (7,8), 12: (12,27), 18: (18), 19:(19), występuje także 20: (1)!
Przykład 2: liczba złożona 49 = 7^2
Ponieważ 48 = 2^4*3, spodziewane są cykle zaczynające się nie dalej niż od 4.tej iteracji. Występują następujące cykle: (0), (1), (6,13,22), (8,15,20). Dla ziarna z=18 uzyskiwana jest 1 sugerująca, że liczba jest pierwsza!
Kiedy z nie jest inicjowane potęgą z^3, pojawiają się dodatkowe cykle długości 6, np. (2,4,16,11,23,10). Wtedy z ziarnem 18 nie ma kłopotu, tworzy się cykl (18,19).
Przykład 3: liczba pierwsza 53
Rozkład 52=2^2*13.
Występują 2 cykle: (1) oraz (4,16,9,25,11,15,13,10,6,17,24,7).
Kiedy z nie jest inicjowane potęgą, cykl 12-wyrazowy występuje dla większości ziaren.
24 listopada 2007
Obowiązki bezrobotnego
Studiując uprawnienia bezrobotnych doszedłem do ciekawego wniosku. Osoba taka nie może zarabiać w jakikolwiek sposób, bo traci prawa. Zatem bezrobotni mogą udzielać korepetycji tylko za darmo.
Subskrybuj:
Posty (Atom)