W rzeczywistości można zaimplementować nieograniczoną Sieve of Atkin (SoA), nie używając w ogóle segmentacji, tak jak zrobiłem here in F#. Zauważ, że jest to czysto funkcjonalna wersja, która nawet nie używa tablic do łączenia rozwiązań równań kwadratowych i filtru bez kwadratów, a zatem jest znacznie wolniejsza niż bardziej imperatywne podejście.
Optymalizacje Bersteina przy użyciu tablic przeglądowych dla optymalnych zakresów 32-bitowych sprawiłyby, że kod byłby wyjątkowo złożony i nieodpowiedni do prezentacji tutaj, ale byłoby całkiem łatwo dostosować mój kod F #, aby sekwencje zaczynały się od ustawionego dolnego limitu i są używane tylko w pewnym zakresie, aby zaimplementować wersję podzieloną na segmenty i/lub zastosować te same techniki do bardziej bezwzględnego podejścia z użyciem tablic.
Należy zauważyć, że realizacja nawet Berstein za SOA nie jest naprawdę szybciej niż Sito Eratostenesa z wszystkich możliwych optymalizacje zgodnie Kim Walisch's primesieve ale to tylko szybciej niż równoważnie zoptymalizowana wersja Sito Eratostenesa dla wybranego zakresu numerów zgodnie z jego implementacją.
EDIT_ADD: Dla tych, którzy nie chcą, aby przebrnąć przez Berstein za pseudo-kodu i kodu C, dodaję do tej odpowiedzi, aby dodać metodę pseudo-kodu do wykorzystania SOA w przedziale od niskiego do wysokiego gdzie delta z LOW do HIGH + 1 może być ograniczona do równego modulo 60 w celu użycia optymalizacji modulo (i potencjalnego upakowania bitowego tylko do pozycji na 2,3,5 koła).
Jest to oparte na możliwej implementacji przy użyciu kwadratów SoA (4 * x^2 + y ^), (3 * x^2 + y^2) i (3 * x^2 -y^2) wyrażone jako sekwencje liczb o wartości x dla każdej sekwencji ustalonej na wartości między jednym a SQRT ((HIGH - 1)/4), SQRT ((HIGH - 1)/3) i rozwiązywaniu kwadratów dla 2 * x^2 + 2 * x - HIGH - 1 = 0 dla x = (SQRT (1 + 2 * (HIGH + 1)) - 1)/2, odpowiednio, z sekwencjami wyrażonymi w moim kodzie F #, jak na górnym łączu . Optymalizacje dla sekwencji tam używanych powodują, że podczas przesiewania tylko dla nieparzystych kompozytów, dla sekwencji "4x", wartości y muszą być jedynie nieparzyste, a sekwencje "3x" wymagają tylko użycia nieparzystych wartości y, gdy x jest równy i na odwrót. Dalsza optymalizacja zmniejsza liczbę rozwiązań równań kwadratowych (= elementów w sekwencjach) przez obserwację, że wzory modulo powyżej powyższych sekwencji powtarzają się w bardzo małych zakresach x, a także powtarzają się nad zakresami y wynoszącymi tylko 30, które są używane w kod Bersteina, ale nie (jeszcze) zaimplementowany w moim kodzie F #.
Nie uwzględniam również dobrze znanych optymalizacji, które można zastosować do wstępnego wyrównywania "bez kwadratów", aby użyć współczynnika koła i obliczeń dla początkowego adresu segmentu, którego używam w my implementations of a segmented SoE.
Dla celów obliczania adresów segmentów rozpoczynających sekwencję dla "4x", "3x +" i "3x-" (lub "3x +" i "3x-" połączonych tak jak w przypadku kodu F #), i obliczeniu zakresów X w każdym zgodnie z powyższym pseudokod jest następujący:
Oblicz zakresie niskich - FIRST_ELEMENT, gdzie FIRST_ELEMENT z najmniejszą odpowiedniej wartości y dla każdej określonej wartości x lub y = x - 1 dla przypadku sekwencji "3x-".
Aby obliczyć, ile elementów znajduje się w tym przedziale, sprowadza się to do liczby (y1)^2 + (y2)^2 + (y3)^2 ... gdzie każda liczba y jest oddzielona przez dwa, aby uzyskać równe lub nieparzyste liczby y zgodnie z wymaganiami. Jak zwykle w analizie sekwencji kwadratowych, zauważamy, że różnice między kwadratami mają stały przyrost, ponieważ w delcie (9 - 1) wynosi 8, delta (25 - 9) wynosi 16 dla wzrostu o 8, delta (49 - 25) jest 24 dla dalszego wzrostu o 8 itd. więc dla n elementów ostatni przyrost wynosi 8 * n dla tego przykładu. Wyrażając sekwencję elementów za pomocą tego, otrzymujemy, że jest to jeden (lub cokolwiek wybiera się jako pierwszy element) plus ośmiokrotnie kolejność czegoś podobnego (1 + 2 + 3 + ... + n). Teraz standardowa redukcja sekwencji liniowych ma zastosowanie tam, gdzie suma ta wynosi (n + 1) * n/2 lub n^2/2 + n/2. Możemy to rozwiązać, ilu n elementów znajduje się w zakresie, rozwiązując równanie kwadratowe n^2/2 + n/2 - range = 0 lub n = (SQRT (8 * zakres + 1) - 1)/2.
Teraz, jeśli FIRST_ELEMENT + 4 * (n + 1) * n nie jest równe LOW jako adres początkowy, dodaj jeden do n i użyj FIRST_ELEMENT + 4 * (n + 2) * (n + 1) jako adres początkowy. Jeśli stosuje się dalsze optymalizacje do zastosowania uśredniania rozłożenia koła do wzoru sekwencji, należy sprawdzić tablice tablicowe, aby wyszukać najbliższą wartość użytego n, która spełnia warunki.
Moduł 12 lub 60 elementu początkowego może być obliczany bezpośrednio lub może być wytworzony przy użyciu tabel wyszukiwania w oparciu o powtarzalny charakter sekwencji modulo.
Każda sekwencja jest używana do przełączania stanów kompozytowych do limitu WYSOKIE. Jeśli dodatkowa logika jest dodawana do sekwencji, aby przeskoczyć wartości tylko do odpowiednich elementów na sekwencję, nie jest konieczne dalsze stosowanie warunków modulo.
Powyższe jest wykonywane dla każdej sekwencji "4x", po której następują sekwencje "3x +" i "3x-" (lub łącz "3x +" i "3x-" w jednym zestawie sekwencji "3x") do limity x obliczone wcześniej lub testowane w pętli.
I nie trzeba go: podana odpowiednia metoda podzielenie zakresu sito do segmentów, które jest używane jako stałych rozmiarach, które są związane z wielkością pamięci podręcznej procesora dla najlepszej wydajności dostępu do pamięci, to metoda segmentacji SoA tak samo używane przez Bernsteina, ale nieco prostsze w wyrażeniu, ponieważ wspomina, ale nie łączy operacji modulo i bitowego pakowania.
Przez lata badałem sito Atkin/Bernstein i nigdy nie wymyśliłem, jak go posegmentować - przez co mam na myśli rozpoczynanie go na jakiejś dowolnej dużej liczbie, z może mniejszym wyprzedzeniem. Byłbym zainteresowany, czy ktoś ma. – librik