Eratosthenovo síto v C - rychlá implementace

C++ Pokročilé konstrukce Zdrojákoviště Eratosthenovo síto v C - rychlá implementace

Před pár dny mě inspiroval program na výpis prvočísel od Satíka

Satíkova aplikace generuje poměrně rychle seznam všech prvočísel v řádu přibližně 106. U vyšších hodnot už rychle ztrácí dech, což je celkem pochopitelné a očekávané.

Začal jsem se zajímat, jak rychle lze vygenerovat prvočísla v rozsahu 109?

Napsal jsem tedy základní algoritmus, který využívá naivní implementaci Eratosthenova síta a začal dělat testy. Během pokusů jsem vyzkoušel následující implementace:

  1. naive Eratosthenes sieve
  2. segmented Eratosthenes sieve
  3. wheel factorization
  4. optimized Eratosthenes sieve

Naivní verze síta je podle očekávání rychlá pouze v rozsahu 106.

Na druhou stranu rozsah 109 je stále ještě směšně malý, takže optimalizace síta za využití segmentace je pouze "kanón na vrabce". I když segmentace přinesla poměrně slušné zrychlení, z hlediska celkového času nepovažuji zisk za odpovídající vůči ceně komplikovaného kódu.

Faktorizace přes "kolo" při velikosti kola 30 také zrychlila běh, ale ani ta nestačila optimalizované verzi algoritmu, pro kterou jsem se nakonec rozhodl zejména kvůli jednoduchosti implementace.

Pokud hledáme prvočísla v rozsahu 3 .. 2*n, připravíme si pole o velikosti n, kde prvek na pozici i reprezentuje hodnotu 2*n+1. Pole inicializujeme na true. Následující kód označí všechna složená čísla v daném rozsahu, zatímco prvočíselné hodnoty zůstanou nezměněny.

// 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;

Poté platí, že liché číslo x je prvočíslo, pokud primes[x >> 1] != 0.

Na procesoru Core i5 byly časy běhu algoritmu přibližně následující (nezahrnuje generování výstupního souboru):

  • 106 - 0.002s
  • 107 - 0.03s
  • 108 - 0.51s
  • 109 - 5.9s
  • 109 - 1.5s při segmentaci síta

Jak rychle lze tedy najít prvočísla až do miliardy? Během několika sekund.

Využitím řady dalších optimalizací je možné získat prvočísla v rozsahu 109 v čase okolo jedné sekundy. Tyto úpravy zahrnují zejména segmentaci síta kombinovanou s úsporným paměťovým modelem spadajícím do L1 a L2 CPU cache. To se ovšem vyplatí až u vyšších hodnot okolo řádu 1012. Na mém kódu se mi líbí jednoduchost spojená se dostačujícím výkonem.

Zdrojový kód v jazyce C je v příloze.


Galerie

Program byl vytvořen v roce 2014.

 

Stáhnout

Staženo 177x (625 B)
Aplikace je včetně zdrojových kódů v jazyce C

 

  Aktivity (2)

Program pro vás napsal coells
Avatar

Jak se ti líbí článek?
Celkem (1 hlasů) :
55555


 



 

 

Komentáře

Avatar
Luboš Běhounek (Satik):

Taky už jsem na ten algoritmus koukal, ale zatím jsem se nedostal k tomu, abych ho zkusil napsat, v týdnu se na ten tvůj kód podívám :)

Odpovědět 16.6.2014 12:13
:)
Avatar
coells
Redaktor
Avatar
Odpovídá na Luboš Běhounek (Satik)
coells:

Publikovaný kód obsahuje pouze základní verzi Eratosthena.

Verzi se segmentací jsem tam nedával, protože by jí stejně nikdo nerozuměl. Je to jen zběsilé skákání sem a tam, které moc nedává smysl, pokud neznáš všechny podmínky i důsledky. Vím to, protože jsem se díval, jak efektivní jsou ostatní algoritmy a v kódu jsem se vždy ztratil ve chvíli, kdy tam autor zapracoval optimalizaci.

 
Odpovědět 16.6.2014 13:27
Avatar
Odpovídá na coells
Libor Šimo (libcosenior):

Ja len doplním, že ak to chce niekto otestovať na win xp a code:blocks 10.05, musí zmeníť: %llu na %I64u, inakšie to nepôjde skompilovať.

Odpovědět 16.6.2014 15:09
Aj tisícmíľová cesta musí začať jednoduchým krokom.
Avatar
hanpari
Redaktor
Avatar
hanpari:

Nemůžu si pomoct a musím tady doporučit jednu vynikající knihu o matematice:

http://www.academia.cz/…vocisly.html

I když není o programování, rozhodně je k tématu.
Vřele doporučuju.

 
Odpovědět 20.6.2014 14:58
Avatar
coells
Redaktor
Avatar
Avatar
hanpari
Redaktor
Avatar
Odpovídá na coells
hanpari:

Ta "moje" (z knihovny) je spíš matematicko-historická. Ale opravdu zajímavé čtení. Ale o počítačích tam moc není :)

Teď mám ještě rozečtenou tuhle:

http://www.dokoran.cz/index.php?…

Zatímco ta předtím se zabývala matematikou, tahle se zabývá historií problému z názvu, tj. výpočtem nejkratší cesty mezi n body. Také doporučuji. Ta už je o počítačích trochu víc :)

 
Odpovědět 20.6.2014 16:25
Děláme co je v našich silách, aby byly zdejší diskuze co nejkvalitnější. Proto do nich také mohou přispívat pouze registrovaní členové. Pro zapojení do diskuze se přihlas. Pokud ještě nemáš účet, zaregistruj se, je to zdarma.

Zobrazeno 6 zpráv z 6.