Sito Atkina

W matematyce sito Atkina to nowoczesny algorytm znajdowania wszystkich liczb pierwszych do określonej liczby całkowitej. W porównaniu ze starożytnym sitem Eratostenesa , które wyznaczało wielokrotności liczb pierwszych, sito Atkina wykonuje pewną wstępną pracę, a następnie zaznacza wielokrotności kwadratów liczb pierwszych, osiągając w ten sposób lepszą teoretyczną złożoność asymptotyczną . Został stworzony w 2003 roku przez AOL Atkin i Daniela J. Bernsteina .

Algorytm

W algorytmie:

  • Wszystkie reszty to reszty modulo -sześćdziesiąt (podziel liczbę przez 60 i zwróć resztę).
  • Wszystkie liczby, w tym x i y , są dodatnimi liczbami całkowitymi.
  • Odwrócenie wpisu na liście sit oznacza zmianę oznaczenia (prime lub nonprime) na oznaczenie przeciwne.
  • Powoduje to, że liczby z nieparzystą liczbą rozwiązań odpowiedniego równania są potencjalnie pierwsze (pierwsze, jeśli są również wolne od kwadratów), a liczby z parzystą liczbą rozwiązań są złożone.

Algorytm:

  1. Utwórz listę wyników wypełnioną liczbami 2, 3 i 5.
  2. Utwórz listę sit z wpisem dla każdej dodatniej liczby całkowitej; wszystkie pozycje tej listy powinny być początkowo oznaczone jako nie pierwsze (złożone).
  3. Dla każdego wpisu o numerze n na liście sit, z resztą modulo-sześćdziesiąt r :
    1. Jeśli r wynosi 1, 13, 17, 29, 37, 41, 49 lub 53, odwróć wpis dla każdego możliwego rozwiązania do 4 x 2 + y 2 = n . Liczba operacji odwracania w stosunku do zakresu przesiewania dla tego kroku zbliża się do 4 √ π / 15 × 8 / 60 („8” w ułamku pochodzi z ośmiu modulo obsługiwanych przez ten kwadrat i 60, ponieważ Atkin obliczył to na podstawie parzystej liczby kół modulo 60), co daje ułamek około 0,1117010721276....
    2. Jeśli r wynosi 7, 19, 31 lub 43, odwróć wpis dla każdego możliwego rozwiązania do 3 x 2 + y 2 = n . Liczba operacji odwracania w stosunku do zakresu przesiewania dla tego kroku zbliża się do ( π podstawie √ 0,12 × 4/60 „4” we frakcji pochodzi z czterech modułów obsługiwanych przez ten kwadrat i 60, ponieważ Atkin obliczył to na parzysta liczba kół modulo 60), co daje ułamek około 0,072551974569....
    3. Jeśli r wynosi 11, 23, 47 lub 59, odwróć wpis dla każdego możliwego rozwiązania do 3 x 2 - y 2 = n , gdy x > y . Liczba operacji odwracania w stosunku do zakresu przesiewania dla tego kroku zbliża się do √ 1,92 ln( √ 0,5 + √ 1,5 ) × 4 / 60 („4” w ułamku pochodzi z czterech modulo obsługiwanych przez ten kwadrat i 60, ponieważ Atkin obliczył to na podstawie parzystej liczby kół modulo 60), co daje ułamek około 0,060827679704....
    4. Jeśli r jest czymś innym, zignoruj ​​to całkowicie.
  4. Zacznij od najniższego numeru na liście sit.
  5. Weź następną liczbę na liście sit, wciąż oznaczoną liczbą pierwszą.
  6. Umieść numer na liście wyników.
  7. Podnieś liczbę do kwadratu i zaznacz wszystkie wielokrotności tego kwadratu jako nie pierwsze. Należy zauważyć, że wielokrotności, które można rozłożyć na czynniki przez 2, 3 lub 5, nie muszą być oznaczane, ponieważ zostaną one zignorowane w końcowym wyliczeniu liczb pierwszych.
  8. Powtórz kroki od czwartego do siódmego. Całkowita liczba operacji dla tych powtórzeń oznaczania kwadratów liczb pierwszych jako stosunku zakresu przesiewania jest sumą odwrotności liczb pierwszych do kwadratu, która zbliża się do funkcji zeta liczby pierwszej (2) ... 1/2 równej 2 0,45224752004 minus , 1 / 3 2 i 1 / 5 2 dla tych liczb pierwszych, które zostały wyeliminowane przez koło, z wynikiem pomnożonym przez 16 / 60 dla stosunku uderzeń kół na zakres; daje to stosunek około 0,01363637571....

Dodając do siebie powyższe stosunki operacji, powyższy algorytm przyjmuje stały stosunek operacji odwracania/zaznaczania do zakresu przesiewania około 0,2587171021...; Z faktycznej implementacji algorytmu stosunek wynosi około 0,25 dla zakresów przesiewania tak niskich jak 67.

Pseudo kod

Poniżej znajduje się pseudokod , który łączy algorytmy Atkina 3.1, 3.2 i 3.3 przy użyciu połączonego zestawu „s” wszystkich liczb modulo 60 z wyłączeniem tych, które są wielokrotnościami liczb pierwszych 2, 3 i 5, zgodnie z algorytmami, dla prosta wersja algorytmu , która obsługuje opcjonalne pakowanie bitów koła; chociaż nie zostało to wyraźnie wspomniane w cytowanym artykule, ten pseudokod eliminuje pewne oczywiste kombinacje nieparzystych/parzystych x/y w celu zredukowania obliczeń, w przypadku których te obliczenia i tak nigdy nie przeszłyby testów modulo (tj. wygenerowałyby liczby parzyste lub wielokrotności 3 lub 5 ): 

          


   limit  ←  1000000000  // dowolny limit wyszukiwania  // zestaw pozycji „trafienia” koła dla koła 2/3/5 przetoczonego dwukrotnie zgodnie z algorytmem Atkina  s  ←  {  1  ,  7  ,  11  ,  13  ,  17  ,  19  ,  23  ,  29  ,  31  ,  37  ,  41  ,  43  ,  47  ,  49  ,  53  ,  59  } 


           0     
      





  // Zainicjuj sito z wystarczającą liczbą kół, aby zawierało limit:  for  n  ←  60  ×  w  +  x  gdzie  w  ∈  {  ,  1  ,...,  limit  ÷  60  },  x  ∈  s  :  is_prime  (  n  )  ←  false  // Wstaw kandydujące liczby pierwsze:  // liczby całkowite, które mają // nieparzystą liczbę  reprezentacji w pewnych formach kwadratowych.  // Krok algorytmu 3.1:  dla  n               
          ≤  granica  ,  n  ←  4  x²  +  y²  gdzie  x  ∈  {  1  ,  2  ,...}  i  y  ∈  {  1  ,  3  ,...}  // wszystkie x nieparzyste y's  , jeśli  n  mod  60  ∈  {  1  ,  13  ,  17  ,  29  ,  37  ,  41  ,  49  ,  53  }  : 
             

               
          is_prime  (  n  )  ←  ¬  is_prime  (  n  )  // przełączanie stanu  // Krok algorytmu 3.2:  for  n  ≤  limit  ,  n  ←  3  x²  +  y²  gdzie  x  ∈  {  1  ,  3  ,...}  i  y  ∈  {  2  ,  4  ,...}  // tylko nieparzyste x  jeśli  n  mod  60  ∈  {                                  
             

               7  ,  19  ,  31  ,  43  }  :  // a parzyste y  is_prime  (  n  )  ←  ¬  is_prime  (  n  )  // przełączanie stanu  // Krok algorytmu 3.3:  for  n  ≤  limit  ,  n  ←  3  x²  -  y²  gdzie  x  ∈  {  2  ,  3  ,...}  i  y  ∈  {  x  
                                            
             


     -1  ,  x  -3  ,...,  1  }  //wszystkie parzyste/nieparzyste  if  n  mod  60  ∈  {  11  ,  23  ,  47  ,  59  }  :  // nieparzyste/parzyste kombinacje  is_prime  (  n  )  ←  ¬  is_prime  (  n  )  // toggle state  // Wyeliminuj kompozyty przez przesiewanie, tylko dla tych wystąpień na kole:  for  n²  ≤  limit  ,  n           0      
     
        
        
                   ←  60  ×  w  +  x  gdzie  w  ∈  {  ,  1  ,...},  x  ∈  s  ,  n  ≥  7  :  if  is_prime  (  n  )  :  // n jest liczbą pierwszą, pomiń wielokrotności jej kwadratu; to wystarczy   // ponieważ kompozyty bezkwadratowe nie mogą znaleźć się na tej liście  dla  c  ≤  limit  ,  c  ←  n²  ×  (  60  ×  w       0   
              


   
                0 +  x  )  gdzie  w  ∈  {  ,  1  ,...},  x  ∈  s  :  is_prime  (  c  )  ←  false  // jedno przeciągnięcie w celu wytworzenia sekwencyjnej listy liczb pierwszych aż do granicy:  wyjście  2  ,  3  ,  5  dla  7  ≤  n  ≤  granica  ,  n  ←  60  ×  w  +  x  gdzie  w  ∈  {  ,    
        1  ,...},  x  ∈  s  :  jeżeli  is_prime  (  n  )  :  wyjście  n

Ten pseudokod został napisany dla przejrzystości; chociaż niektóre zbędne obliczenia zostały wyeliminowane poprzez kontrolowanie nieparzystych/parzystych kombinacji x/y, nadal marnuje prawie połowę obliczeń kwadratowych na nieproduktywne pętle, które nie przechodzą testów modulo, tak że nie będzie szybszy niż odpowiednik koło faktoryzowane (2/3/5) sito Eratostenesa . Aby poprawić jego wydajność, należy opracować metodę minimalizowania lub eliminowania tych nieproduktywnych obliczeń.

Wyjaśnienie

Algorytm całkowicie ignoruje wszelkie liczby z resztą modulo 60 podzielną przez dwa, trzy lub pięć, ponieważ liczby z resztą modulo 60 podzielną przez jedną z tych trzech liczb pierwszych same są podzielne przez tę liczbę pierwszą.

Wszystkie liczby n z resztą z sześćdziesięciu modulo 1, 13, 17, 29, 37, 41, 49 lub 53 mają resztę z modulo cztery z 1. Liczby te są pierwsze wtedy i tylko wtedy, gdy liczba rozwiązań 4 x 2 + y 2 = n jest nieparzyste, a liczba jest wolna od kwadratów (udowodnione jako twierdzenie 6.1).

Wszystkie liczby n z resztą z modulo sześćdziesiąt 7, 19, 31 lub 43 mają resztę z modulo sześć równą 1. Liczby te są pierwsze wtedy i tylko wtedy, gdy liczba rozwiązań 3 x 2 + y 2 = n jest nieparzysta i liczba jest bezkwadratowa (udowodnione jako twierdzenie 6.2).

Wszystkie liczby n z resztą z sześćdziesięciu modulo 11, 23, 47 lub 59 mają resztę z dwunastu równych 11. Liczby te są pierwsze wtedy i tylko wtedy, gdy liczba rozwiązań 3 x 2 - y 2 = n jest nieparzysta i liczba jest bezkwadratowa (udowodnione jako twierdzenie 6.3).

Żadna z potencjalnych liczb pierwszych nie jest podzielna przez 2, 3 lub 5, więc nie mogą być podzielne przez ich kwadraty. To dlatego czeki bezkwadratowe nie obejmują 2 2 , 3 2 i 5 2 .

Złożoność obliczeniowa

Można obliczyć, że każda z powyższych serii trzech operacji równania kwadratowego ma pewną liczbę operacji, która jest stałym stosunkiem zakresu, gdy zakres dąży do nieskończoności; podobnie jak operacje swobodnego usuwania z kwadratu głównego można opisać funkcją zeta liczby pierwszej (2) ze stałymi przesunięciami i czynnikami, więc jest to również stały współczynnik zakresu, gdy zakres dąży do nieskończoności. Dlatego algorytm opisany powyżej może obliczyć liczby pierwsze do N przy użyciu operacji O ( N ) z tylko O ​​( N ) bitami pamięci.

Wersja z segmentacją stron zaimplementowana przez autorów ma te same operacje O ( N ), ale zmniejsza wymagania dotyczące pamięci do poziomu wymaganego przez podstawowe liczby pierwsze poniżej pierwiastka kwadratowego z zakresu O ( N 1/2 /log N ) bitów pamięci plus minimalny bufor strony. Jest to nieco lepsza wydajność przy takim samym zapotrzebowaniu na pamięć, jak sito podzielone na segmenty stron Eratostenesa , które wykorzystuje operacje O( N log log N ) i to samo O ( N 1/2 /log N ) bitów pamięci plus minimalny bufor strony. Jednak takie sito nie przewyższa sita Eratostenesa z maksymalnym praktycznym rozkładem koła (kombinacja koła przesiewającego 2/3/5/7 i kompozytów wstępnej selekcji w buforach stron segmentu przy użyciu 2/3/5/7 /11/13/17/19), które chociaż ma nieco więcej operacji niż sito Atkina dla bardzo dużych, ale praktycznych zakresów, ma stały współczynnik mniejszej złożoności na operację około trzykrotnie w porównaniu czasu na operację między algorytmy zaimplementowane przez Bernsteina w cyklach zegara procesora na operację. Głównym problemem związanym z Segmentowanym Sitem Atkina jest trudność we wdrażaniu sekwencji usuwania „wolnych od głównych kwadratów” ze względu na rozpiętość między selekcjami szybko rosnącą daleko poza zakres bufora strony; czas poświęcony na tę operację w implementacji Bernsteina szybko rośnie do wielu razy w porównaniu z rzeczywistymi obliczeniami równań kwadratowych, co oznacza, że ​​​​liniowa złożoność części, która w przeciwnym razie byłaby całkiem nieistotna, staje się głównym konsumentem czasu wykonania. Tak więc, nawet jeśli zoptymalizowana implementacja może ponownie osiągnąć złożoność czasową O(n), ten stały współczynnik zwiększonego czasu na operację oznacza, że ​​sito Atkina jest wolniejsze.

Specjalna zmodyfikowana odmiana „wyliczania punktów sieci” , która nie jest powyższą wersją sita Atkina, może teoretycznie obliczyć liczby pierwsze do N przy użyciu operacji O ( N / log log N ) z N 1/2 + o (1) bitami pamięci ale ta odmiana jest rzadko wdrażana. Jest to trochę lepsza wydajność przy bardzo wysokim koszcie pamięci w porównaniu zarówno ze zwykłą wersją z segmentacją stron, jak i z równoważną, ale rzadko wdrażaną wersją sita Eratostenesa, która wykorzystuje operacje O ( N ) i O ( N 1/2 (log log N )/log N ) bitów pamięci.

Pritchard zauważył, że w przypadku sit kołowych można zmniejszyć zużycie pamięci przy zachowaniu złożoności czasu Big O, ale generalnie wiąże się to ze zwiększonym stałym współczynnikiem czasu na operację ze względu na dodatkową złożoność. Dlatego ta specjalna wersja jest prawdopodobnie bardziej wartościowa jako ćwiczenie intelektualne niż praktyczne sito główne ze zmniejszonym czasem rzeczywistym poświęcanym na dany duży praktyczny zakres przesiewania.

Zobacz też

  1. ^ a b c d e f g h i j A.OL Atkin, DJ Bernstein, Sita pierwsze przy użyciu binarnych form kwadratowych , Math. Komp. 73 (2004), 1023-1030. [1]
  2. ^ Pritchard, Paul, „Liniowe sita liczb pierwszych: drzewo genealogiczne”, Sci. Oblicz. Programowanie 9 : 1 (1987), s. 17–35.
  3. ^ Paul Pritchard, Podliniowe sito addytywne do znajdowania liczb pierwszych, Communications of the ACM 24 (1981), 18–23. MR 600730
  4. ^ Paul Pritchard, Wyjaśnienie sita koła, Acta Informatica 17 (1982), 477–485. MR 685983
  5. ^ Paul Pritchard, Szybkie zwarte sita liczb pierwszych (między innymi), Journal of Algorithms 4 (1983), 332–344. MR 729229

Linki zewnętrzne

Pobrane z „ https://en.wikipedia.org/w/index.php?title=Sieve_of_Atkin&oldid=1048307934 ”