Википедија

Atkinovo sito

U matematici, Atkinovo sito je moderan algoritam za traženje svih prostih brojeva do specifično celih brojeva. U poređenju sa drevnim Eratostenovim sitom, koje se obeležava sa umno prostijim brojeva, na neke preliminarne radove i onda obeležava sa biše korenima prostih brojeva, čime se postiže bolja asimptotska teorijska kompleksnost. Osmislili su ga 2003. godine A. O. L. Atkin  i Danijel J. Bernstejn.[1]

Algoritam uredi

U ovom algoritmu:

  • Svi ostaci su modul-šezdeset ostaci (podeliti taj broj sa 60 i vrati ostatak). 
  • Svi brojevi, uključujući, x i y su pozitivni celi brojevi.
  •  Fliping stavka na listi sito znači da promenite obeležavanje (prosti ili neprosti brojevi) na suprotnu oznaku.
  • To rezultira u brojkama sa neparnim brojem rešenja na odgovarajuće jednačina kao potencijalno proste brojeve (prosti ako su i oni beskvadratni brojevi), i brojeve sa parnim brojem rešenjima koji su složeni.

Algoritam:

  1. Pravi listu rezultata, ispunjenu sa 2, 3 i 5. 
  2. Pravi listu sita sa unosom za svaki ceo pozitivan broj; sve stavke iz ove liste treba u početku da budu obeležene ne prostim brojevima (složeni).
  3. Za bilo koji uneti broj n listi sita, sa modulom-šezdeset ostatkom r :
    1. Ako je r  1, 13, 17, 29, 37, 41, 49, ili 53, flip unos za svako moguće rešenje 4x2 + y2 = n. Broj flip operacija kao odnos prosejavanja opsega za ovaj korak prosejavanje pristupi 4√π/15[1] × 8/60 ("8" u frakciji dolazi od osam modulos rukuje ovim kvadratna i 60, jer Atkin izračunava na osnovu ovog parnog broja modulo 60 točaka), što rezultira u deliću o 0.1117010721276....
    2. Ako je r 7, 19, 31, ili 43, flip unosa za svako moguće rešenje je 3x2 + y2 = n. Broj flip operacija kao odnos prosejavanja opsega za ovaj korak prosejavanje pristupa  π√0.12[1] × 4/60 ( "4" u frakciji dolazi do četiri modula rukovanja ovim je kvadrat i 60, jer je Atkin računao na osnovu ovog parnog broja modula 60 točaka), što rezultira u deliću o 0.072551974569....
    3. Ako je r  11, 23, 47, ili 59, flip unosa za svako moguće rešenje je 3x2 − y2 = n kada je x > y. Broj flip operacija kao odnos prosejavanja opsega za ovaj korak prosejavanje pristupa √1.92ln(√0.5+√1.5)[1] × 4/60 ("4" u frakciji dolazi do četiri modula rukovanja ovim je kvadrat i 60, jer je Atkin računao na osnovu ovog parnog broja modula 60 točaka), što rezultira u deliću o 0.060827679704....
    4. Ako je r nešto drugo, ignoriše ga u potpunosti.
  4. Počinje sa najmanjim brojem u listi sita.
  5. Uključuje broj u listi rezultata.
  6. Koren broj i sve oznake tog kvadrata nisu prosti brojevi. Paziti da se više puta mogu uzeti za 2, 3 ili 5 a ne mora da bude obeleženi, jer će biti ignorisani u završnom prebrojavanju prostih brojeva.
  7. Ponavljaju se koraci od četiri do sedam. Ukupan broj operacija za ova ponavljanja obeležavanja kvadrata prostih brojeva je kao odnos prosejavanja opsega tj. zbir je suprotan od prostih brojeva na kvadrat, koji se približava funkciju prostih brojeva zeta (2) 0.45224752004... minus 1/221/22, 1/321/32, i 1/521/52 za one proste brojeve kod kojih su otklonjena sita, sa rezultatom pomnoženim 16/6016/60 za odnos sita pogotka po rasponu; to rezultira u odnosu od oko 0.01363637571....

Dodavanje gornjih pokazatelja zajedno, gore algoritam uzima konstantan odnos flipa / obeležavanje operacije na prosejavanju opsega od oko 0,2587171021. ..; Iz stvarne implementacije algoritma, odnos je oko 0,25 za prosejavanje opsega kao donja granica kao 67.

Pseudokod uredi

Sledeći je pseudokod koji Atkin kombinuje sa algoritmima 3.1, 3.2, 3.3 i[1] pomoću kombinovanog skupa "s" od svih brojeva po modulu 60 isključujući one čiji su činioci prosti brojevi 2, 3 i 5, po algoritmima za direktnu verziju algoritma koji podržava bitno opciono pakovanje za volanom ; iako nije posebno pomenuto u navedenom radu, ovaj pseudokod eliminiše neke očigledne kombinacije neparne / jednake x's/y's u cilju smanjenja računanja gde se proračuni nikad ne bi prošli kroz testove po modulu (tj. on će proizvesti čak i brojeve, ili više 3 ili 5): 

limit ← 1000000000        // arbitrary search limit

// set of wheel "hit" positions for a 2/3/5 wheel rolled twice as per the Atkin algorithm
s ← {1,7,11,13,17,19,23,29,  31,37,41,43,47,49,53,59}

// Initialize the sieve with enough wheels to include limit:
for n ← 60 × w + x where w ∈ {0,1,...,limit ÷ 60}, x ∈ s:
    is_prime(n) ← false

// Put in candidate primes:
//   integers which have an odd number of
//   representations by certain quadratic forms.
// Algorithm step 3.1:
for n ≤ limit, n ← 4x²+y² where x ∈ {1,2,...} and y ∈ {1,3,...} // all x's odd y's
    if n mod 60 ∈ {1,13,17,29,37,41,49,53}:
        is_prime(n) ← ¬is_prime(n)   // toggle state
// Algorithm step 3.2:
for n ≤ limit, n ← 3x²+y² where x ∈ {1,3,...} and y ∈ {2,4,...} // only odd x's
    if n mod 60 ∈ {7,19,31,43}:                                 // and even y's
        is_prime(n) ← ¬is_prime(n)   // toggle state
// Algorithm step 3.3:
for n ≤ limit, n ← 3x²-y² where x ∈ {2,3,...} and y ∈ {x-1,x-3,...,1} //all even/odd
    if n mod 60 ∈ {11,23,47,59}:                                   // odd/even combos
        is_prime(n) ← ¬is_prime(n)   // toggle state

// Eliminate composites by sieving, only for those occurrences on the wheel:
for n² ≤ limit, n ← 60 × w + x where w ∈ {0,1,...}, x ∈ s, n ≥ 7:
    if is_prime(n):
        // n is prime, omit multiples of its square; this is sufficient 
        // because square-free composites can't get on this list
        for c ≤ limit, c ← n² × (60 × w + x) where w ∈ {0,1,...}, x ∈ s:
            is_prime(c) ← false

// one sweep to produce a sequential list of primes up to limit:
output 2, 3, 5
for 7 ≤ n ≤ limit, n ← 60 × w + x where w ∈ {0,1,...}, x ∈ s:
    if is_prime(n): output n

Ovaj pseudokod je jasno napisan; iako su neki suvišni proračuni eliminisani radi kontrole neparnih / jednakih x/y kombinacija, i dalje se troši skoro polovinu svojih kvadratinih izračunavanja na neproduktivne petlje koje ne prolaze po modulu testova tako da neće biti brže nego će ekvivalenti točak rastaviti (2/3/5) Eratostenovo sito. Da bi se poboljšala efikasnost, metod mora biti osmišljen da smanji ili eliminiše ova neproizvodna izračunavanja.

Objašnjenje uredi

Algoritam u potpunosti ignoriše sve brojeve sa naslednog modula 60 koji su deljivi sa dva, tri ili pet, pošto brojeve po modulu 60 ostatak deljivih sa jednim od ova tri prosta broja su deljivi prosti brojevi.

Svi brojevi n sa modulom-šezdeset ostatkom 1, 13, 17, 29, 37, 41, 49, ili 53 imaju modul-četiri ostatka 1. Ti brojevi su prosti brojevi ako i samo ako je broj rešenja 4x2 + y2 = n neparan i ako je beskvadratni broj(dokazano kao teorema 6.1[1]).

Svi brojevi n sa modulom-šezdeset ostatkom 7, 19, 31, ili 43 imaju modul-šest ostatak 1. Ti brojevi su prosti brojevi ako i samo ako je broj rešenja 3x2 + y2 = n neparan broj i broj je beskvadratni broj (dokazano kao teorema 6.2 [1]).

Svi brojevi n sa modulom-šezdeset ostatkom 11, 23, 47, ili 59 imaju modul-dvanaest ostatak 11. Ti brojevi su prosti brojevi ako i samo ako im je broj rešenja 3x2 − y2 = n neparan i broj im je beskvadratni ( dokazano kao teorema 6.3[1]).

Nijedan od potencijalnih prostih brojeva nije deljivi sa 2, 3 ili 5, tako da ne mogu biti deljiv sa svojim korenima. To je razlog zašto beskvadratne provere ne uključuju 22, 32, i 52.

Računarska kompleksnost uredi

Može se izračunati[1] da gornja serija od tri kvadratne jednačine svaka ima broj operacija koji je konstantan odnosu opsega kako opseg teži ka beskonačnosti; kao i prosti brojevi beskvadratnih kuling operacija mogu opisati proste zeta funkcije (2) sa stalnim kompenzacija i činiocima, tako da je i stalni činilac u rasponu ide u beskonačnost. Stoga, gore opisani algoritam može izračunati proste brojeve do N koristeći O(N) operacije samo sa O(N) bitovima memorije.

Segmentirana verzija stranice se sprovodi od strane autora ima isto O(N) operacije, ali smanjuje potrebu memorije što i traži od osnovnih prostih brojeva ispod kvadratnog korena u rasponu odO(N1/2/log N) bitova memorije plus minimalna bafer stranica. Ovo je nešto boljeg performansa sa istim zahtevom memorije kao i strana razdvojenog Eratostenovog sita koja koristi O(N log log N) operacije i O(N1/2/log N) bitova memorije[2] plus minimalna bufer stranica. Međutim, takvo sito ne nadmašuje Eratostenovo sito sa praktično maksimalnim točkovima faktorizacije (kombinacija 2/3/5/7 prosejavanja točkova i pre kuling složenih brojeva u segmentu bafer stranica koristeći 2/3/5/7 / 11/13/17/19 obrazac), koji iako ima nešto više operacija nego Atkin sito za veoma velike, ali praktično pokretne, ima konstantni faktor manje složenosti po operaciji za oko tri puta u poređenju tokom vremena rada između algoritama sprovođenih od strane Bernstejna u CPU satnom ciklusa u radu. Glavni problem sa stranicom segmentiranog Atkin sita je teškoća u primeni "Prostih beskvadratnih brojeva" uništavanje sekvence zbog raspona između brzo rastućih kulsova daleko od strana tampon raspona; vreme utrošena za ovu operaciju u realizaciji Bernstajnobe implementacije brzo raste da mnogo puta vreme utrošeno u aktuelnim proračunima kvadratne jednačine, što znači da je linearna kompleksnost dela koji bi inače bio sasvim zanemarljiv postaje veliki potrošač vremena izvršenja. Tako, iako je optimizovana implementacija može se ponovo izmiriti do a O(n) kompleksnosti vremena, ova konstanta faktora povećanog vremena po operacijama znači da je Atkin sito.

Posebna modifikovana "nabrajanje rešetke tačaka" varijacija koje nije iznad verzija Atkin sita može teoretski da izračuna proste brojeve do N koristeći O(N/log log N) operacije sa N1/2 + o(1)bitovima memorije[1] ali ova varijanta je retko kad realizovana, uključujući i autore. To je malo bolje u performansama na veoma visokoj ceni memorija u odnosu na obe obične stranice segmentirane verzije ali retko, ako ikada sprovedena verzija Eratostenovog sita koje koristi O(N) operacije i O(N1/2(log log N)/log N) bitove memorije.[3][4][5]

Pričard je primetio da za volanom sita, može smanjiti potrošnju memorije uz očuvanje vremenske kompleksnosti velikog O, ali to uglavnom dolazi po cenu stalnog povećanog faktora za vreme operacije pa zbog dodatnih računskih složenosti; moglo bi se pretpostaviti da važi i za posebne varijacije na Atkin sito po prethodnoj diskusiji. Dakle, ovo je specijalna verzija verovatno više vrednosti kao intelektualne vežbe nego praktična primena sita sa realno smanjenim vremenom utrošenim za velika praktična prosejavanja opsega.

Vidi još uredi

Reference uredi

  1. ^ a b v g d đ e ž z i A.O.L. Atkin, D.J. Bernstein, Prime sieves using binary quadratic forms, Math.
  2. ^ Pritchard, Paul, "Linear prime-number sieves: a family tree," Sci.
  3. ^ Paul Pritchard, A sublinear additive sieve for finding prime numbers, Communications of the ACM 24 (1981), 18–23.
  4. ^ Paul Pritchard, Explaining the wheel sieve, Acta Informatica 17 (1982), 477–485.
  5. ^ Paul Pritchard, Fast compact prime number sieves (among others), Journal of Algorithms 4 (1983), 332–344.

Spoljašnje veze uredi

Preuzeto iz „https://sr.wikipedia.org/w/index.php?title=Аткиново_сито&oldid=27395708”