Аткиново сито

У математици, Аткиново сито је модеран алгоритам за тражење свих простих бројева до специфично целих бројева. У поређењу са древним Ератостеновим ситом, које се обележава са умно простијим бројева, на неке прелиминарне радове и онда обележава са бише коренима простих бројева, чиме се постиже боља асимптотска теоријска комплексност. Осмислили су га 2003. године А. О. Л. Аткин и Данијел Ј. Бернстејн.^[1]

Алгоритам

У овом алгоритму:

Сви остаци су модул-шездесет остаци (поделити тај број са 60 и врати остатак).
Сви бројеви, укључујући, x и y су позитивни цели бројеви.
Флипинг ставка на листи сито значи да промените обележавање (прости или непрости бројеви) на супротну ознаку.
То резултира у бројкама са непарним бројем решења на одговарајуће једначина као потенцијално просте бројеве (прости ако су и они бесквадратни бројеви), и бројеве са парним бројем решењима који су сложени.

Алгоритам:

Прави листу резултата, испуњену са 2, 3 и 5.
Прави листу сита са уносом за сваки цео позитиван број; све ставке из ове листе треба у почетку да буду обележене не простим бројевима (сложени).
За било који унети број n листи сита, са модулом-шездесет остатком r :
1. Ако је r 1, 13, 17, 29, 37, 41, 49, или 53, флип унос за свако могуће решење 4x² + y² = n. Број флип операција као однос просејавања опсега за овај корак просејавање приступи $.mw-parser-output .sfrac{white-space:nowrap}.mw-parser-output .sfrac.tion,.mw-parser-output .sfrac .tion{display:inline-block;vertical-align:-0.5em;font-size:85%;text-align:center}.mw-parser-output .sfrac .num,.mw-parser-output .sfrac .den{display:block;line-height:1em;margin:0 0.1em}.mw-parser-output .sfrac .den{border-top:1px solid}.mw-parser-output .sr-only{border:0;clip:rect(0,0,0,0);height:1px;margin:-1px;overflow:hidden;padding:0;position:absolute;width:1px}4√π/15$ ^[1] × 8/60 ("8" у фракцији долази од осам модулос рукује овим квадратна и 60, јер Аткин израчунава на основу овог парног броја модуло 60 точака), што резултира у делићу о 0.1117010721276....
2. Ако је r 7, 19, 31, или 43, флип уноса за свако могуће решење је 3x² + y² = n. Број флип операција као однос просејавања опсега за овај корак просејавање приступа $π \sqrt 0.12$ ^[1] × 4/60 ( "4" у фракцији долази до четири модула руковања овим је квадрат и 60, јер је Аткин рачунао на основу овог парног броја модула 60 точака), што резултира у делићу о 0.072551974569....
3. Ако је r 11, 23, 47, или 59, флип уноса за свако могуће решење је 3x² − y² = n када је x > y. Број флип операција као однос просејавања опсега за овај корак просејавање приступа $\sqrt 1.92 ln (\sqrt 0.5 + \sqrt 1.5)$ ^[1] × 4/60 ("4" у фракцији долази до четири модула руковања овим је квадрат и 60, јер је Аткин рачунао на основу овог парног броја модула 60 точака), што резултира у делићу о 0.060827679704....
4. Ако је r нешто друго, игнорише га у потпуности.
Почиње са најмањим бројем у листи сита.
Укључује број у листи резултата.
Корен број и све ознаке тог квадрата нису прости бројеви. Пазити да се више пута могу узети за 2, 3 или 5 а не мора да буде обележени, јер ће бити игнорисани у завршном пребројавању простих бројева.
Понављају се кораци од четири до седам. Укупан број операција за ова понављања обележавања квадрата простих бројева је као однос просејавања опсега тј. збир је супротан од простих бројева на квадрат, који се приближава функцију простих бројева зета (2) 0.45224752004... минус 1/2²1/2², 1/3²1/3², и 1/5²1/5² за оне просте бројеве код којих су отклоњена сита, са резултатом помноженим 16/6016/60 за однос сита поготка по распону; то резултира у односу од око 0.01363637571....

Додавање горњих показатеља заједно, горе алгоритам узима константан однос флипа / обележавање операције на просејавању опсега од око 0,2587171021. ..; Из стварне имплементације алгоритма, однос је око 0,25 за просејавање опсега као доња граница као 67.

Псеудокод

Следећи је псеудокод који Аткин комбинује са алгоритмима 3.1, 3.2, 3.3 и^[1] помоћу комбинованог скупа "s" од свих бројева по модулу 60 искључујући оне чији су чиниоци прости бројеви 2, 3 и 5, по алгоритмима за директну верзију алгоритма који подржава битно опционо паковање за воланом ; иако није посебно поменуто у наведеном раду, овај псеудокод елиминише неке очигледне комбинације непарне / једнаке x's/y's у циљу смањења рачунања где се прорачуни никад не би прошли кроз тестове по модулу (тј. он ће произвести чак и бројеве, или више 3 или 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

Овај псеудокод је јасно написан; иако су неки сувишни прорачуни елиминисани ради контроле непарних / једнаких x/y комбинација, и даље се троши скоро половину својих квадратиних израчунавања на непродуктивне петље које не пролазе по модулу тестова тако да неће бити брже него ће еквиваленти точак раставити (2/3/5) Ератостеново сито. Да би се побољшала ефикасност, метод мора бити осмишљен да смањи или елиминише ова непроизводна израчунавања.

Објашњење

Алгоритам у потпуности игнорише све бројеве са наследног модула 60 који су дељиви са два, три или пет, пошто бројеве по модулу 60 остатак дељивих са једним од ова три проста броја су дељиви прости бројеви.

Сви бројеви n са модулом-шездесет остатком 1, 13, 17, 29, 37, 41, 49, или 53 имају модул-четири остатка 1. Ти бројеви су прости бројеви ако и само ако је број решења 4x² + y² = n непаран и ако је бесквадратни број(доказано као теорема 6.1^[1]).

Сви бројеви n са модулом-шездесет остатком 7, 19, 31, или 43 имају модул-шест остатак 1. Ти бројеви су прости бројеви ако и само ако је број решења 3x² + y² = n непаран број и број је бесквадратни број (доказано као теорема 6.2 ^[1]).

Сви бројеви n са модулом-шездесет остатком 11, 23, 47, или 59 имају модул-дванаест остатак 11. Ти бројеви су прости бројеви ако и само ако им је број решења 3x² − y² = n непаран и број им је бесквадратни ( доказано као теорема 6.3^[1]).

Ниједан од потенцијалних простих бројева није дељиви са 2, 3 или 5, тако да не могу бити дељив са својим коренима. То је разлог зашто бесквадратне провере не укључују 2², 3², и 5².

Рачунарска комплексност

Може се израчунати^[1] да горња серија од три квадратне једначине свака има број операција који је константан односу опсега како опсег тежи ка бесконачности; као и прости бројеви бесквадратних кулинг операција могу описати просте зета функције (2) са сталним компензација и чиниоцима, тако да је и стални чинилац у распону иде у бесконачност. Стога, горе описани алгоритам може израчунати просте бројеве до N користећи O(N) операције само са O(N) битовима меморије.

Сегментирана верзија странице се спроводи од стране аутора има исто O(N) операције, али смањује потребу меморије што и тражи од основних простих бројева испод квадратног корена у распону одO(N^1/2/log N) битова меморије плус минимална бафер страница. Ово је нешто бољег перформанса са истим захтевом меморије као и страна раздвојеног Ератостеновог сита која користи O(N log log N) операције и O(N^1/2/log N) битова меморије^[2] плус минимална буфер страница. Међутим, такво сито не надмашује Ератостеново сито са практично максималним точковима факторизације (комбинација 2/3/5/7 просејавања точкова и пре кулинг сложених бројева у сегменту бафер страница користећи 2/3/5/7 / 11/13/17/19 образац), који иако има нешто више операција него Аткин сито за веома велике, али практично покретне, има константни фактор мање сложености по операцији за око три пута у поређењу током времена рада између алгоритама спровођених од стране Бернстејна у ЦПУ сатном циклуса у раду. Главни проблем са страницом сегментираног Аткин сита је тешкоћа у примени "Простих бесквадратних бројева" уништавање секвенце због распона између брзо растућих кулсова далеко од страна тампон распона; време утрошена за ову операцију у реализацији Бернстајнобе имплементације брзо расте да много пута време утрошено у актуелним прорачунима квадратне једначине, што значи да је линеарна комплексност дела који би иначе био сасвим занемарљив постаје велики потрошач времена извршења. Тако, иако је оптимизована имплементација може се поново измирити до а O(n) комплексности времена, ова константа фактора повећаног времена по операцијама значи да је Аткин сито.

Посебна модификована "набрајање решетке тачака" варијација које није изнад верзија Аткин сита може теоретски да израчуна просте бројеве до N користећи O(N/log log N) операције са N^1/2 + o(1)битовима меморије^[1] али ова варијанта је ретко кад реализована, укључујући и ауторе. То је мало боље у перформансама на веома високој цени меморија у односу на обе обичне странице сегментиране верзије али ретко, ако икада спроведена верзија Ератостеновог сита које користи O(N) операције и O(N^1/2(log log N)/log N) битове меморије.^[3]^[4]^[5]

Причард је приметио да за воланом сита, може смањити потрошњу меморије уз очување временске комплексности великог О, али то углавном долази по цену сталног повећаног фактора за време операције па због додатних рачунских сложености; могло би се претпоставити да важи и за посебне варијације на Аткин сито по претходној дискусији. Дакле, ово је специјална верзија вероватно више вредности као интелектуалне вежбе него практична примена сита са реално смањеним временом утрошеним за велика практична просејавања опсега.

Види још

Референце

^ ^а ^б ^в ^г ^д ^ђ ^е ^ж ^з ^и A.O.L. Atkin, D.J. Bernstein, Prime sieves using binary quadratic forms, Math.
^ Pritchard, Paul, "Linear prime-number sieves: a family tree," Sci.
^ Paul Pritchard, A sublinear additive sieve for finding prime numbers, Communications of the ACM 24 (1981), 18–23.
^ Paul Pritchard, Explaining the wheel sieve, Acta Informatica 17 (1982), 477–485.
^ Paul Pritchard, Fast compact prime number sieves (among others), Journal of Algorithms 4 (1983), 332–344.

Спољашње везе

An optimized implementation of the sieve (in C)

[paper-1] а ^б ^в ^г ^д ^ђ ^е ^ж ^з ^и 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.

[1]

[2]

[3]

[4]

[5]