Główna zawartość
Informatyka
Kurs: Informatyka > Rozdział 2
Lekcja 6: Test pierwszości- Wprowadzenie
- Wyzwanie: test pierwszości
- Metoda próbnych dzieleń
- Czym jest pamięć komputera?
- Wydajność algorytmu
- Poziom 3: Wyzwanie
- Sito Eratostenesa
- Poziom 4: Sito Eratostenesa
- Test pierwszości z sitem Etastotenesa
- Poziom 5: Próba podziału za pomocą sita
- Twierdzenie o liczbach pierwszych
- Spirala Ulama liczb pierwszych
- Odległość pomiędzy liczbami pierwszymi
- Kompromis czasu i pamięci
- Podsumowanie (co dalej?)
© 2023 Khan AcademyWarunki użytkowaniapolitykę prywatnościInformacja o plikach cookie
Wydajność algorytmu
Jak możemy zwiększyć szybkość (deterministycznego) testu pierwszości? Stworzone przez: Brit Cruise.
Chcesz dołączyć do dyskusji?
Na razie brak głosów w dyskusji
Transkrypcja filmu video
Mam doniesienie, że wysyłają nowy łazik na Marsa. Odpowiadamy za jedno: mamy zaprogramować algorytm,
do łazika, sprawdzający, czy liczby są pierwsze. Powiedzmy, że łazik
porozumiewa się używając RSA. Musi mieć on wgrany algorytm
wykonujący test pierwszości. Projektując łazik
lub cokolwiek, co poleci w Kosmos, musicie dbać o wydajność
pod każdym względem. Składniki muszą być bardzo lekkie. Każdy podsystem musi zużywać
jak najmniej mocy, trzeba oszczędzać energię i masę w każdym momencie
procesu projektowego. Ułatwiliśmy sobie pracę. Będziemy mieć do czynienia
z liczbami do tej wielkości. Trzeba sobie z nimi radzić szybko. Przy bardzo małych danych
wejściowych, np. przy 90, algorytm powinien to obliczyć
prawie tak szybko, jak tę całą liczbę. Rozmiar danych wejściowych rośnie, ale nie chcemy
zauważalnego spowolnienia. Przeanalizuję pytania użytkowników i ich pomysły, bardzo dobre,
z matematycznego punktu widzenia. Sprawdzamy, czy liczba n
jest pierwsza czy złożona. Mając dane n, pomyślcie o przestrzeni wszystkich możliwych n. Jeśli n równa się 100,
to przestrzeń – od dwóch do stu. Nasz algorytm
przeszukuje tę przestrzeń. Myślcie o algorytmie,
który przeszukuje. W każdym punkcie pyta… Potraktujcie to jako krok.
Podstawowy. Algorytm pyta… to jest pytanie o złożoność n. Jesteśmy przy liczbie a. W metodzie próbnych dzieleń spytamy:
„Czy n dzieli się przez a?”. Próbujemy. Wrzucamy a,
próbujemy podzielić przez nie n, patrzymy, czy reszta wynosi zero, co oznacza, że a jest dzielnikiem n. I mówimy: „Tak, wiemy na 100%”. Wiemy na pewno, że ta liczba
jest złożona. Inaczej, przy każdym z kroków,
nie mamy całkowitej pewności. Liczba może być pierwsza. Kontynuujemy szukanie do końca. Pamiętacie, że w tym przypadku
granicą był pierwiastek z n. Najgorzej jest wtedy,
gdy n jest liczbą pierwszą, a my szukamy aż do pierwiastka z n i dopiero wtedy powiemy:
„Pierwsza. Wiemy to na 100%”. W razie, gdy n jest iloczynem
dwóch liczb pierwszych, 7 razy 7 równa się 49, jeśli wrzucimy 49 w nasz algorytm, będzie to najgorszy przypadek. Dojdziemy aż do pierwiastka
kwadratowego z n. Pierwsze komentarze… Np. użytkownik
TheFourthDimension pyta: „Kiedy wykluczymy 2,
jako niepodzielne, można wykluczyć
wszystkie wielokrotności 2, i 3, 4, 5 itd.”. Świetne spostrzeżenie. Stary algorytm posuwał się po kolei, ale możemy wykorzystywać wzory
związane z liczbami złożonymi. Np. wiemy na pewno, że jeśli liczba jest podzielna
przez 2, to jest złożona. Większa od 2, bo 2 to liczba pierwsza.
Powiemy: „4 to liczba złożona”. Nie wpisałem 5, przepraszam.
4, 6, 8… 10. Zamiast tego
możemy zrobić taki krok. 3, 5, 7, 9… Jedna kategoria pytań to te
starające się ograniczyć przestrzeń. Jeśli wyeliminujemy
wszystkie liczby parzyste, to przestrzeń sprawdzania
nie sięga pierwiastka z n, tylko pierwiastka z n
podzielonego przez 2. Znajdziemy inne schematy
dotyczące liczb złożonych, żeby zmniejszyć to jeszcze bardziej. Inny typ pytań… dotyczy przypadku,
gdy znajdujemy świadka złożoności. Takie a, które pozwoli powiedzieć:
„Wiemy, że n jest liczbą złożoną”. Lola napisała: „Czy wyjście z pętli gdy test pierwszości równa się
FAŁSZ oszczędziłoby czas?”. Tak, zgadza się,
i tego właśnie chcemy. Kiedy szukamy krokami określonymi w wybranym schemacie, znajdujemy świadka złożoności. Przechodzi test i mamy
stuprocentową pewność, że możemy przerwać wcześniej. Zatrzymujemy się.
„Gotowe. Dalej nie szukamy”. To wcześniejsze zatrzymanie jest świetne, tylko nie pomaga
w najgorszym przypadku, czyli kiedy n jest liczbą pierwszą. Wtedy nie da się przerwać wcześniej. Zobaczmy, jak te ulepszenia
pozwalają nam zmniejszyć przestrzeń, ograniczając liczbę testów
wewnątrz komputera. To, zależnie od komputera,
skróci cały proces. Mogę wam pokazać wizualizację,
którą przygotowałem. Pozwoli ona porównać dwa algorytmy w oparciu o to, ile kroków wymaga
ich wykonanie. Po lewej mamy algorytm A,
metodę próbnych dzieleń, sprawdzanie od dwóch
do pierwiastka kwadratowego z n. Po prawej jest algorytm B,
nasz algorytm ulepszony. W tym przypadku zastosowałem test podzielności przez 2, więc kroków
wykonujemy już tylko połowę. W algorytmie B także
wcześniej kończę. Nie jest doskonały. Wprowadziłem
parę sugestii użytkowników, zobaczymy, co będzie.
Uruchomię to, żebyście zobaczyli. Kiedy przesuwam, widzimy algorytm A. Mamy wynik:
liczba złożona czy pierwsza. Zaś na dole widzicie liczbę kroków. Zauważcie:
po prawej stronie, co druga liczba zajmuje
tylko jeden krok. Wiemy, dlaczego. Bo jeśli to liczba parzysta,
jak ta, to program się zatrzyma. Nasz stary algorytm
potrzebował 314 kroków. Nowy algorytm – tylko jednego, bo sprawdza, czy liczba dzieli się
przez 2. Przyjemna optymalizacja! Ale gdy będziemy zwiększać
dane wejściowe, zobaczycie, że liczba kroków rośnie, prostokąt powiększa się
i staje się czerwony. W miarę zbliżania się do regionu,
gdzie program się załamie. Czerwona linia to granica.
Jeśli prostokąt tu sięgnie, to nam się nie uda. Łazik się zepsuje. W naszym przypadku
padnie przeglądarka. Spróbuję się zbliżyć. Jestem blisko
i program działa bardzo wolno. Czuję, że moja przeglądarka
zaraz się posypie. Zauważcie, że ulepszony algorytm
potrzebował tylko dwóch kroków. Pamiętajcie o najgorszym przypadku. Mam parę dużych liczb pierwszych
zapisanych dla przykładu. Musimy sobie radzić z każdym
przypadkiem. Nie wiadomo, co się trafi. Jeśli wrzucę dużą liczbę pierwszą,
patrzcie, co będzie. Algorytm B, jak wiemy potrzebuje połowy kroków
w najgorszym przypadku, ale i tak wykonuje
wiele kroków tutaj. Bo to najgorszy przypadek. Zbliżamy się do katastrofy,
a to nie jest bardzo długa liczba. Znacznie poniżej 15 cyfr. Gdy wprowadzą tę
12-cyfrową liczbę pierwszą do naszego algorytmu, zobaczmy, co będzie… Zwalnia, może się zatrzyma. Patrzcie: oba algorytmy
przekroczyły granicę. Nie udało się. Nasz ulepszony algorytm
nie jest jeszcze dość dobry. Ale teraz rozumiemy,
co staramy się ulepszyć: liczbę kroków
w najgorszym przypadku. I mamy też świetne narzędzie, które pozwala wizualizować,
jak szybko to rośnie w miarę wzrostu rozmiaru
danych wejściowych. Poniżej wyjaśnię, jak to zrobiłem, żebyście mogli ułożyć
własny algorytm. I porównać z naszym przykładem.
Może dacie radę lepiej.