Eratostenovo sito v C - rýchla implementácia

Pred pár dňami ma inšpiroval program na výpis prvočísel od Satíka

Satíkova aplikácie generuje pomerne rýchlo zoznam všetkých prvočísel v poriadku približne 10 ^6. U vyšších hodnôt už rýchlo stráca dych, čo je celkom pochopiteľné a očakávané.

Začal som sa zaujímať, ako rýchlo možno vygenerovať prvočísla v rozsahu 10 ^9?

Napísal som teda základné algoritmus, ktorý využíva naivný implementáciu Eratosthenova sita a začal robiť testy. Počas pokusov som vyskúšal nasledujúce implementácie:

1. naive Eratosthenes sieve
2. Segmented Eratosthenes sieve
3. wheel factorization
4. Optimized Eratosthenes sieve

Naivné verzia sita je podľa očakávania rýchla iba v rozsahu 10 ^6.

Na druhú stranu rozsah 10 ⁹ je stále ešte smiešne malý, takže optimalizácia sitá za využitia segmentácie je len "kanón na vrabca". Aj keď segmentácia priniesla pomerne slušné zrýchlenie, z hľadiska celkového času nepovažujem zisk za zodpovedajúcu voči cene komplikovaného kódu.

Faktorizácia cez "koleso" pri veľkosti bicykla 30 tiež zrýchlila beh, ale ani tá nestačila optimalizované verziu algoritmu, pre ktorú som sa nakoniec rozhodol najmä kvôli jednoduchosti implementácie.

Ak hľadáme prvočísla v rozsahu 3 .. 2 * n, pripravíme si poľa veľkosti n, kde prvok na pozícii i reprezentuje hodnotu 2 * n + 1. Pole inicializujeme na true. Nasledujúci kód označí všetky zložená čísla v danom rozsahu, zatiaľ čo prvočíselnom hodnoty zostanú nezmenené.

// iprime je 64-bitové celé číslo bez znaménka
for (iprime i = 1, j = 3; i < n; i++, j += 2)
    for (iprime k = j * j >> 1; k < n && primes[i]; k += j)
        primes[k] = 0;

Potom platí, že nepárne číslo x je prvočíslo, ak PRIMES [x >> 1]! = 0.

Na procesora Core i5 boli časy behu algoritmu približne nasledovné (nezahŕňa generovanie výstupného súboru):

• 10 6 - 0.002s
• 10 7 - 0.03s
• 10 8 - 0.51s
• 10 9 - 5.9s
• 10 9 - 1.5s pri segmentáciu sita

Ako rýchlo možno teda nájsť prvočísla až do miliardy? Počas niekoľkých sekúnd.

Využitím rady ďalších optimalizáciou je možné získať prvočísla v rozsahu 10 9 v čase okolo jednej sekundy. Tieto úpravy zahŕňajú najmä segmentáciu sita kombinovanú s úsporným pamäťovým modelom patriacim do L1 a L2 CPU cache. To sa však oplatí až u vyšších hodnôt okolo poriadku 10 12. Na mojom kódu sa mi páči jednoduchosť spojená so dostačujúcim výkonom.

Zdrojový kód v jazyku C je v prílohe.

Galéria