Prímszám keresés C-ben

 ( funtom | 2009. április 23., csütörtök - 23:52 )

Sziasztok!

Az alábbi programot szeretném optimalizálni, (azaz nem a hardvert fejleszteni) úgy hogy gyorsabban lefusson.

$ cat prim.c

$ gcc -Wall -O3 prim.c -o prim

$ time ./prim 1000000
DB: 1000000 PRIM: 15485863

real 0m14.426s
user 0m14.125s
sys 0m0.028s

Tudom, hogy néhány módszerrel lehetne még egy-két tizedet nyerni a dolgon, de nem ilyenre vágyom.

Van ötletetek, hogyan lehetne 10s alá menni? Esetleg más matematikai módszerrel, vagy valamilyen trükkel, netalán valamit nagyon elrontok?

Előre is köszi. :)

ps: Tudom, hogy 2^31 nagyságrendű prímnél elszállna a program, de jelenleg értelmes időn belül ezt megközelíteni sem tudom.

ps2: Az esetleges bemeneti argumentumhiba szándékosan nincs lekezelve.

ps3: Félreértések elkerülése végett a célom az, hogy mondjuk a 100 000 000. prímet megtaláljam, méghozzá gyorsan. :)

[UPDATE]
Volt végre tíz percem, s mivel elmúlt a másnaposságom, gyorsan megírtam a szitás módszerrel is. Egészen meglepődtem. :)

$cat prim2.c

$ gcc -Wall -O3 prim2.c -o prim2

$ time ./prim2 15485863
DB: 1000000 PRIM: 15485863

real 0m1.730s
user 0m1.616s
sys 0m0.036s

Hozzászólás megjelenítési lehetőségek

A választott hozzászólás megjelenítési mód a „Beállítás” gombbal rögzíthető.

Első körben ne egyesével vizsgáld a számokat:
pl. minden 2 vagy 3-nál nagyobb prim 6k+1 vagy 6k-1 alakú (k=1..)

Gyorsabb módszer pedig: az "Erasztotenész szitája" néven elérhető, erre keress rá.

Egyébként nehéz segíteni, mert a becopyzott kód eleve nemigazán tűnik korrektnek...

Megprobálhatnád: <code> </code> mezőben

Sry. Valóban nyirbált a hup. :( A < code > nem segített rajta. De most már talán jó lett.

az "Erasztotenész szitája"

+1

Ezzel tényleg sokat lehet nyerni? Nem írtam meg rá a programot, de érzésre nem lehet sokkal gyorsabb. :)

Alapból is gyorsabb, mert pl. nem kell maradékképzést használni.

Ráadásul a különféle változataival (pl Euler's Sieve) és megfelelő adatszerkezetekkel később sokkal tovább csiszolgatható és optimalizálható mint ez a maradékképezgetős ciklus.

Ellenben minden számot struktúra tömbbe kell helyezni. Én most csak a prímeket rakom tömbbe.

De a maradékképzés masszív FPU művelet, míg az adattagok elérése csak mutatózás.

--
"SzAM-7 -es, tudjátok amivel a Mirage-okat szokták lelőni" - Robi.

+1
En is ezzel a modszerel generaltam primaszamokat.

-----
“Firefox, you say? No I don't play Pokémon”

Nem vagom, hogy amit irtal az hogy akar mukodni, valoszinuleg mert a copy-paste-nel kihagyta a karakterek felet, de nem igy alnek neki. Elso korben egy jo trukk lehet a kis Fermat-tetel.
p prim => a ^ p mod p == a mod p
azaz ha 2 ^ p mod p != 2 akkor p nem prim. Persze ha a ketto egyenlo attol meg nem biztos hogy p prim...
tovabb lehet jatszani a := 3 -ra stb..
==
`Have some wine,' the March Hare said in an encouraging tone.
Alice looked all round the table, but there was nothing on it but tea.

Carmichael számok - álprím-adatbázis is kell hozzá, mert sajnos nem elég ritkák az álprímek.

ami át van húzva, azt teljesen fölösleges elolvasni. az olyan, mintha ott sem lenne

Biztos, hogy ez a kód, így működik? Vagy a HUP megnyirbálta a postod?

Na mindegy. Egy időben játszottam én is ilyen "kis" prímszámokkal. Ezen az oldalon van egy nagyon jó kis írás forráskódokkal, időeredményekkel. Indul a naív tesztből, optimalizálgatja, aztán áttér az Eratosthenészi szitára, azon is farag, nagyon tanulságos...

ps. Én magam is faragtam a végső kódon, aztán találtam egy mégjobb szitát (Atkins and Bernstein). :)

[Edit] Speed test (Atkins szita - AthlonXP 2000+ (1667Mhz), terhelve)
# konzolra:
$ time ./primes 1 1000000
real 0m1.564s
user 0m0.060s
sys 0m0.212s
# csak ugy:
$ time ./primes 1 1000000 >dev/null
real 0m0.053s
user 0m0.024s
sys 0m0.004s

-geever

Köszi, ez érdekesnek tűnik. Ha lesz egy kis időm elolvasom. :)

Mellesleg ha jól értem, te az 1 és 1 000 000 közötti prímeket keresed meg, azért az nem ugyanaz, mint amit én csinálok.

$ time ./prim 78499
78499: 1000003

real 0m0.309s
user 0m0.304s
sys 0m0.004s

Így könnyű. (Még ha a tied gyorsabb is.) :)

Ha nem kell tokeletesen biztosnak lennie, akkor hasznalhatsz pl. Rabin-Miller-tesztet.

--
Fontos feladatot soha ne bizz olyan gepre, amit egyedul is fel tudsz emelni!

while(1){
int prim=1;
int x=0;
while(xi) break;
x++;
}

Ez szerintem egy végtelen ciklus!

while(xi) break;

utasítás hatására rögtön kilép ebből a második (belső) while ciklusból, de a program sosem lesz képes kilépni a külső while(1) ciklusból, mert ahhoz nem írtál "break"-et!

Nem lehet, hogy azért tart neked órákig a keresés, mert bennragadt a program ebben a végtelen ciklusban?

Sajna a hup "megette" a kód egy részét, javítottam. :)

Talán ha használnád a [code][/code]-ot, akkor nem enné meg, plusz rénézésre se lenne okádék, mert megtartaná az formáját :)

#include < stdio.h >
#include < stdlib.h >
#include < unistd.h >

int main(int argc, char *argv[]){
    int i = 2;
    int db = 0;
    int serial = atoi(argv[1]);
    int *primszam = malloc(serial*sizeof(int));
    
    while(1){
	int prim = 1;
	int x = 0;
	while(x < db){
	    if(i % primszam[x] == 0){
		prim = 0;
		break;
	    }
	    if(primszam[x+1]*primszam[x+1] > i) break;
	    x++;
	}

Ha ez sem működik, akkor http://hup.pastebin.com. Ide meg bemásolod az URL-t. Ott még syntax highlight is van.

http://hup.pastebin.com/m58960214

--
trey @ gépház

Jogos, de sajnos ha az #include-ot is korrekten akarom beírni, még mindig elnyeli. :(

< helyett a megfelelő ascii kód:

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>

De ez már kényelmetlenebb (igaz egy pillanat alatt ki lehet cserélni egy szövegben). Akkor marad a http://hup.pastebin.com

--
trey @ gépház

Köszi, így már működik. :)

Mivel ez a 100 000. alkalom, hogy valakinek ezt el kell mondani, nem lehetne a hozzászólások szerkesztő ablakába írni erről egy sort?

Egy 4. pontot az "Előnézet", "Beküldés" gombok fölötti 3 ponthoz.
Pl.:

Forráskódokat [code] [/code] közé kell rakni, a < helyett &lt; vagy &#60; használható.

"...handing C++ to the average programmer seems roughly comparable to handing a loaded .45 to a chimpanzee."
-- Ted Ts'o

+1
Unalmas sokadszorra leirni ezt. Trey, legyszives. Persze a B verzio a regi mukodes helyrerangatasa lenne, mert anno a bbcode kodkepzo ezt megtette automatice.
--

()=() Ki oda vagyik,
('Y') hol szall a galamb
C . C elszalasztja a
()_() kincset itt alant.

Ez már máskor is felmerült, gyanítom, hogy trey nem akar belenyúlni mélyen a drupál szívébe, mert akkor ezt a változtatást minden frissítésnél karban kéne tartania...

"...handing C++ to the average programmer seems roughly comparable to handing a loaded .45 to a chimpanzee."
-- Ted Ts'o

Ezert mondtam, hogy B terv. Viszont azt a formazasi helpet kiegesziteni nem lenne rossz valahogy. Akar a bbcode helpjet, akar valahogy mashogy.
--

()=() Ki oda vagyik,
('Y') hol szall a galamb
C . C elszalasztja a
()_() kincset itt alant.

AKS prímtesztelés a leggyorsabb ahogy tudom (és a megjelenése óta tuningoltak rajta).
http://fatphil.org/maths/AKS/


"A fejlesztot azert fizetik, hogy oldja meg a problemat. Ez egy kemeny szakma." - Chain-Q

váváváváááárjá.... ha jól látom, ez egy egzakt, polinomidejű prímtesztelő-algoritmus???? o_O Nekem nem is olyan régen azt tanították, hogy ilyen állat márpedig nincs. Ha ez nem kamu (nem tűnik annak), akkor elég durva... egyrészt hogy van ilyen, másrészt, hogy nem hallottam róla. Amúgy meg az is, hogy itt azt írja, hogy már korábban is sok polinomidejű, bár nem determinisztikus algoritmus létezett... gondolom voltak azok között is jobb képességűek.
A fentiek ismeretében csak halkan kérdezném: RSA?

Az RSA relatív prímekkel is működik, nem?

Ha jól emlékszem a kiinduló p,q számoknak nem csak egymásohoz, de a titkosítandó "számhoz" is relatív prímeknek kell hogy legyenek, és mivel az bármi lehet, ott tartunk, hogy jó volna ha p és q legalább nagy valószínűséggel prímek...
No de hogy jön ez ide?

Az RSA ereje nem abban rejlik, hogy a prímteszt nehéz, sőt, az pont szívás lenne, hiszen ki akar 3 hetet várni egy RSA kulcs generálására?!

A RSA ereje az, hogy a prímfaktorizáció nehéz...

"...handing C++ to the average programmer seems roughly comparable to handing a loaded .45 to a chimpanzee."
-- Ted Ts'o

Na ja, de amit én írtam az nem prím tesztelő, hanem prím kereső. Igaz itt már mindenről esett szó. :)

a prímek 2002 óta P-ben vannak
ami át van húzva, azt teljesen fölösleges elolvasni. az olyan, mintha ott sem lenne

Az n. prím kisebb, mint n (log n + log log n - 0.9385), ha n nagyobb, mint 8601 (forrás). Én a helyedben eddig csinálnék szitát (ennek a gyökéig kell elmenned x-szel, kiszórni x többszöröseit, majd megszámolni a bent maradtakat).

És igen, ha a szitánál a páros számokat okosan kizárod, az kétszeres szorzót hoz (fele futási idő, fele memória).

Fentebb olvastam Miller-Rubin és AKS tesztekről. Neked nem az a célod, hogy egy nagy számról eldöntsd (nagy szám=több száz számjegyes), hogy prím-e, így ezek itt nem segítenek.

Sőt ha te csak az n.-edik prímet keresed, mint a példaprogramban, a legegyszerűbb gyorsítás letárolni bizonyos sarokpontokat előre. Belefordítani a programba egy statikus tömbben, és csak onnan vizsgálni a számokat, pl.:
a[0] = a 1000. prím
a[1] = a 2000. prím
.
.
.

és így kb. tetszőleges tradeoffot beállíthatsz a memória és számításigény vonalon...

Igen, ha ismerem a 1 000 000. prímet, akkor csak a nála nagyobb számokat kell vizsgálnom, hogy megtaláljam a 1 000 001-et. Azonban jó ha tudom az előző 999 999-et is, mert akkor "csak" velük kell próbálnom leosztani. :)

Hát ilyeneken már tényleg kár fennakadni:
1. egyrészt elég a gyökéig ismerni csak (azokat is letárolhatod ha 2^32-ig számítasz akkor mindenképp)
2. ha a kisméretű prímeket párhuzamosan számítod szitával n gyökéig, még az is belefér mert:
3. addig csökkented a lépésközt és növeled a tömb méretét amíg busásan megtérül az egész

És igen, ha a szitánál a páros számokat okosan kizárod, az kétszeres szorzót hoz (fele futási idő, fele memória).

Ha átírom:
int i=3;
int db=1;
primszam[0]=2;

i+=2;

Körülbelül semmivel sem lesz gyorsabb, pedig tényleg ezt várná az ember... :(
A memória pedig nem értem miért lenne a fele. :)

Igen, mert ez nagyon kevés maradékos osztást vesz ki, beleveheted a 3-mal osztást is, amit az elején írtam, hogy csak 6k+1 és 6k-1 alakú számokat vizsgálod

Egy másik talán látványosabb pont, hogy pl. a négyzetreemelős tesztelős sor indokolatlanul sokszor lefut a legbelső ciklusmagban. Hiszen ha az előző prímnek ismered a gyökét, a következő prímnek annál csak nagyobb lehet a gyöke. Nem kell megint az elejétől kezdve tesztelgetni, futhat egy ciklus tesztelés nélkül az előző prím gyökéig, majd egy új ciklus a teszteléssel tovább.

pl. while(x<db)

feltétel sosem ad hamis értéket, ez a teszt pl. feleslegesen fut le annyiszor

De ilyen bitbabrálós dolgokat még számtalant lehetne találni biztos... Az igazi megoldás egy komplexebb normálisabb szitás algoritmus megírása lenne, hidd csak el nyugodtan, hogy az gyorsabb... ;)

No megírtam a 6k+1 és 6k-1 formulával és nyertem vele kb 0.25 másodpercet. :)
A négyzetreemelős sor elé beraktam egy primszam[x]>előzőgyök feltételt és sokkal lassabb lett. :(

Ok, hazamegyek írok egy szitásat is és majd összevetem. :)

"sor elé beraktam egy primszam[x]>előzőgyök feltételt és sokkal lassabb lett"

Hát mit vártál, ettől csökkent a belső ciklusban futtatott feltétel ellenőrzések száma??? Én nem egészen ezt írtam.

(De egyébként nem is rajtad múlik persze mindig, ez így bitbabrálás: fordító otimalizációja ilyesmi beleszólhat...)

Jogos, nem ezt írtad. Gyorsan átírtam olyanra, mint mondtad, de így is fél másodpercet lassult. :(
Jaja az optimalizáció ki tudja mit művel a kóddal. :)

Miért akarsz 10s alá menni?

KisKresz

Mert abban reménykedem, hogy akkor sikerül megértenem az univerzum rejtélyét és ezzel megbomlik a tér-idő kontinuum.

És? Megbomlott?

KisKresz

"Volt végre tíz percem, s mivel elmúlt a másnaposságom, gyorsan megírtam a szitás módszerrel is. Egészen meglepődtem. :) ....."

Tipikus példa arra, hogy nem mindig eszetlenül optimalizálni kell, általában csupán egy jobb algoritmuson kell gopnolkozni.

Esetleg más matematikai módszerrel, vagy valamilyen trükkel, netalán valamit nagyon elrontok?

Tipikus példa arra, hogy nem mindig eszetlenül írni kell. :)

Ki ír itt eszetlenül? Te?

Igen, én.

Komplex függvénytan II. - egy rakat jó szitálást tanítanak, ajánlom mindenkinek a figyelmébe!

ami át van húzva, azt teljesen fölösleges elolvasni. az olyan, mintha ott sem lenne