Efektywność algorytmów (Przygoda z liczbami pierwszymi, część 3)

Jak możemy poprawić szybkość działania deterministycznego testu pierwszości?

Wyobraźmy sobie sytuację w której nowy łazik jest wysyłany na Marsa,

i my jesteśmy odpowiedzialni za jedną rzecz -

zaprogramowanie algorytmu wewnętrz łazika,

który sprawdza czy dana liczba jest liczbą pierwszą.

Jest to konieczne o tyle, że łazik komunikuje się używając kryptosystemu RSA.

Potrzebuje więc w środku algorytmu, który potrafi robić test pierwszości.

Gdy projektuje się łazik,

lub cokolwiek innego lecącego w przestrzeń kosmiczną, trzeba

być bardzo efektywnym w każdym calu.

A więc komponenty muszą być bardzo lekkie,

ilość energii, którą używa każdy podsystem musi być minimalna.

Należy oszczędzać na energii i masie,

w każdym momencie projektowania.

Mamy więc jasne zadanie w trakcie tego projektowania,

ponieważ nasz algorytm musi radzić sobie z liczbami,

aż do tej wielkości...

i musi to robić bardzo szybko.

Więc powiedzmy, że na wejściu naszego algorytmu podajemy małą liczbę, jak na przykład 90,

powinien on być w stanie ją przerobić prawie tak szybko,

jak tą całą liczbę.

A więc gdy rozmiar wejścia rośnie, nie chcemy,

aby nasz algorytm znacznie zwalniał.

Chciałbym teraz przeanalizować pytania użytkowników,

lub dobre idee, które użytkownicy mieli,

z matematycznego punktu widzenia.

Sprawdzamy czy n jest liczbą pierwszą czy złożoną,

A więc dla danego n myślmy,

o przestrzeni wszystkich możliwych n,

i jeśli n=100 to ta przestrzeń,

jest od 2 do 100.

I to co nasz algorytm robi,

to przeszukuje tę przestrzeń.

Ok, więc nasz algorytm przeszukuje tę przestrzeń,

i na każdym kroku pyta się - myślmy o tym

kroku jako o podstawowym kroku - zadaje pytanie.

Jest to właściwie pytanie testu złożoności,

powiedzmy, że rozważamy aktualnie liczbę a, i w zwykłym teście

przez próby dzielenia pytamy - czy a dzieli n?

Po prostu sprawdzamy to,

wykonując dzielenie n przez a,

i jeśli reszta z dzielenia jest równa 0, co oznacza że a jest dzielnikiem n,

możemy wtedy powiedzieć,

"Ah! Jesteśmy pewni na 100%, że jest to liczba złożona".

W przeciwnym wypadku, na każdym kroku nie jesteśmy do końca pewni,

może to być liczba pierwsza, ale nie musi.

A więc kontynuujemy sprawdzanie, aż do końca.

I jak pamiętamy największą wartością a, do której należy kontynuować sprawdzanie, jest pierwiastek kwadratowy z n,

Pesymistyczny przypadek wypada kiedy n jest liczbą pierwszą,

wtedy sprawdzamy wszystkie wartości a, aż do pierwiastka z n.

i gdy to skończymy, możemy powiedzieć,

"Ah! Ta liczba jest na 100% liczbą pierwszą."

A więc nawet w przypadku gdy n jest iloczynem dwóch liczb pierwszych,

powiedzmy 7,

na przykład 7 x 7,

co jest równe 49

Jeśli na wejściu tego algorytmu dostarczymy 49,

to również będzie pesymistyczny przypadek, przeszukamy wszystko,

aż do pierwiastka z n.

W pierwszym zestawie pytań,

użytkownik TheFourthDimension pyta,

"Gdy wykluczymy 2 jako niepodzielne, to

możemy wykluczyć wszystkie wielokrotności 2 jako podzielne,

to samo dla 3,

to samo dla 3, 4,

to samo dla 3, 4, 5, i tak dalej"

Jest to bardzo słuszna uwaga.

Nasz stary algorytm sprawdzał kolejne liczby co jeden,

a możemy przecież użyć właściwości liczb złożonych, które znamy,

jak na przykład to, że gdy liczba jest podzielna przez 2,

to wtedy jest złożona,

jeśli jest większa niż 2, bo 2 jest liczbą pierwszą.

Możemy więc od razu powiedzieć,

że 4 jest złożona...

Zgubiłem w tym miejscu 5, za co przepraszam.

4

4, 6

4, 6, 8

4, 6, 8, 10...

Więc zamiast tego możemy robić kolejne kroki w ten sposób:

3

3, 5

3, 5, 7

3, 5, 7, 11

Jedna kategoria pytań użytkowników,

stara się zredukować tę przestrzeń.

A więc gdy wykluczymy wszystkie liczby parzyste,

zredukujemy sprawdzaną przestrzeń z pierwiastka z n,

do pierwiastka z n podzielonego przez 2.

I możemy znaleźć więcej właściwości liczb złożonych,

aby zmniejszyć tę przestrzeń jeszcze bardziej.

Inny typ pytań rozważa przypadek,

gdzie staramy się znaleźć świadka złożoności,

czyli staramy się znaleźć takie a, które pozwoli nam stwierdzić, że n jest liczbą złożoną.

Użytkownik lola napisał/a,

"Czy opuszczanie pętli, gdy tylko znajdziemy świadka,

nie zaoszczędzi trochę czasu?".

Tak, to zdecydowanie prawda.

To jest coś co z pewnością chcemy zrobić.

Kiedy tylko na pewnym kroku,

zdefiniowanym przez schemat którego używamy,

znajdziemy świadka złożoności,

to możemy stwierdzić na 100%, że liczba jest złożona,

i od razu zatrzymać algorytm.

Stwierdzamy: "liczba złożona",

i nie kontynuujemy przeszukiwania.

To zatrzymywanie jest bardzo dobre,

jednak nie pomaga nam w pesymistycznym przypadku,

który występuje gdy n jest liczbą pierwszą.

Nie przyspieszy to w żaden sposób czasu trwania algorytmu.

Teraz możemy zwizualizować, jak te usprawnienia,

pozwalają nam zredukować przestrzeń oraz

zmniejszyć ilość obliczeń w środku komputera

(które zależą od komputera jaki posiadamy)

pozwalają zmniejszyć czas trwania algorytmu.

Teraz przedstawię wizualizację, którą przygotowałem poniżej,

która pozwoli nam porównać dwa algorytmy na podstawie,

liczby kroków, które wykonują podczas ich trwania.

Po lewej stronie mamy algorytm A, który jest testem przez próby dzielenia,

sprawdza więc wszystkie liczby od 2 do pierwiastka z n,

a po prawej stronie mamy algorytm B,

który jest lepszą wersją A,

w tym przypadku najpierw sprawdzamy podzielność przez 2,

więc wykonujemy tylko połowę liczby kroków w A,

oraz kończymy od razu po znalezieniu świadka pierwszości.

Nie jest on więc idealny, po prostu zaaplikowałem kilka zaproponowanych usprawnień,

więc będziemy mogli zobaczyć co się stanie,

i pobawić się testowaniem.

Możemy zobaczyć, że gdy przewijam, widzimy

wynik, czy liczba jest pierwsza czy złożona,

a na dole liczbę kroków, którą dany algorytm wykonał podczas sprawdzania.

Pierwszą rzeczą rzucającą się w oczy jest to, że po prawej stronie,

dla wielu liczb liczba kroków to 2.

Wiemy czemu się tak dzieje, jest to przypadek gdy n jest parzyste,

na przykład wynosi tyle...

nasz stary algorytm wykonał aż 314 kroków,

podczas gdy nowy tylko 1,

ponieważ najpierw sprawdził czy liczba jest podzielna przez 2.

Wygląda to więc na całkiem niezłą optymalizację.

Jednakże, gdy odpowiednio zbudujemy nasze wejście,

można zobaczyć, że liczba kroków znacznie rośnie oraz pasek

robi się czerwny, gdy zbliżamy się do tego regionu,

gdzie kroków robi się zdecydowanie za dużo.

Ta czerwona linia to "Limit kroków".

Gdy pasek jej dotknie, algorytm kończy się porażką,

co jest równoważne z tym, że nasz łazik się zepsuje.

A w tym przypadku i przeglądarka się zawiesi,

więc spróbuję zbliżyć się do tej linii jak najbardziej.

W tej chwili jestem bardzo blisko i czućjak wszystko działa bardzo wolno,

widać że przeglądarka jest o krok od,

zawieszenia się.

Zauważmy jednak, że nasz poprawiony algorytm wykonał teraz tylko 2 kroki,

jednak pamiętajmy o pesymistycznym przypadku.

W tym celu mam tutaj zapisanych kilka dużych liczb pierwszych.

Dobry algorytm powinien sobie poradzić z każdą liczbą,

nie wiemy czy dajemy mu liczbę pierwszą czy złożoną.

Zobaczmy więc co się stanie gdy damy na wejściu dużą liczbę pierwszą.

Algorytm B jak wiemy wykonuje tylko połowę kroków,

w pesymistycznym przypadku,

jednak to wciąż dużo.

Ponieważ jest to pesymistyczny przypadek, prawda?

Więc zbliżamy się do limitu kroków,

a liczba którą dałem nie jest wcale dużą liczbą pierwszą.

Wciąż znajdujemy się poniżej 15 cyfr.

A gdy podam tę 12-cyfrową liczbę pierwszą do naszego algorytmu,

zobaczmy co się stanie,

program się opóźnia, możliwe że się zawiesi.

Zobaczmy co się stało,

oba algorytmy znacznie przekroczyły limit kroków,

a więc zawiodły.

Nasze usprawnienia algorytmu nie były wystarczająco dobre niestety.

Jednak teraz lepiej rozumiemy co tak naprawdę,

staramy się poprawić,

i czym jest "liczba kroków w pesymistycznym przypadku".

Mamy dobre narzędzie, które pozwala nam

zwizualizować jak szybko to rośnie,

jak szybko liczba kroków rośnie, gdy rośnie nam rozmiar wejścia.

Poniżej opiszę jak to przygotowałem,

aby można było przygotować swój własny algorytm,

porównać go z podstawowym,

i zobaczyć jak bardzo jest lepszy.