Prímszám keresés C-ben

C/C++

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

  • 9761 megtekintés

( szemet | 2009. 04. 24., p – 00:11 )

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á.

( phaul | 2009. 04. 24., p – 00:22 )

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.

( geever | 2009. 04. 24., p – 00:46 )

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.) :)

( eax | 2009. 04. 24., p – 01:41 )

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!

( pelz | 2009. 04. 24., p – 03:48 )


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?

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

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

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

( Yorirou | 2009. 04. 24., p – 07:47 )

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?

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

( hud | 2009. 04. 24., p – 12:00 )

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...

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... ;)

"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...)

( KisKresz | 2009. 04. 24., p – 15:38 )

Miért akarsz 10s alá menni?

KisKresz

( psc | 2009. 04. 26., v – 02:18 )

"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.

( strangelove | 2009. 05. 04., h – 20:02 )

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