Aktív témák
-
''De a valószínűségessel csak bizonyos előre megadott hibakorláttal számolhatunk, nem?''
Ellenben, ha százszor lefuttatod a teszted, akkor (1/2)^100 az esélye, hogy prim. Az pedig nem tul sok.
Tudomásom szerint a Rabin-Miller teszt a legjobb annak eldöntésére, hogy a szám prim-e, vagy sem. Sajnos nem tudom fejből az algoritmust, de biztos meg lehet találni. A másik, amit tanítanak (használnak?), a Euler-Fermat tételre épül.
Legyen a, amit tesztelünk.
1. véletlen számot sorsolunk, legyen t (1<t<a)
2. lnko(a,t) (euklideszi algoritmussal), ha !=1, akkor nem prim
3. ha t^(a-1) mod a !=1, akkor nem prim
1-3 ismétlése annyiszor, amennyi neked megfelel (ha ez i, akkor (1/2)^i a valószínűsége, hogy mégsem prim)
Ez az algoritmus azért sem a legjobb, mert vannak un. Charmichael számok, amik primnek jönnek ki ezzel, de mégsem azok (talán az 561 ilyen).
Persze ezek arra jók, hogy megmondják egy számról, hogy prim-e. Azonban vannak képletek, amikbe behelyettesítve sokszor primeket kapunk, ezekre talán érdemesebb ráengedni a prim-e kérdést. Persze nem értek túlzottan a témához, egy matematikus kisegíthetne:) -
Lortech
addikt
Szerintem a P4 azért lassú itt, mert 16 bites a kód és azt meg nem nagyon szereti. Ezért átírtam a progot Delphiben és az eredmény: 10-15M 16 másodperc. Celeron 2@2.66GHz.
Ha esetleg érdekel valakit, akkor elküldöm a ''progit'', majd este felé.
Majd lefuttatom otthon az AthlonXP-men is. -
#95
The Creature
tag
The Creature
tag
[10.000.000]-[15.000.000]-ig
netezés közben..:DD
[Szerkesztve] -
Qorthral
őstag
Hello!!!
Én magam is épp múlt héten dobtam össze ilyen progit, csak nem Pascalban, hanem Mathcadben. Nagy hátránya, hogy jóval lassabb, viszont csinaltam mellé egy-két elsozlásvizsgáló progit is és így már vicces. Vmint fájlból beolvassa az eddigi prímeket és folytatja a kért értékig. A végén meg kiírja fájlba.
Én is arra jöttem rá, hogy: csak a szám gyökéig kell futnia, és csak a már megtalált prímekre kell ellenőriznie a számot. :)
Amugy nekem: Xp 1800+ - 75 sec, mondjuk sok minden futott mellette és no tuning.
No Üdv!!!
Tom -
Niquis
aktív tag
válasz
Cathfaern
#88
üzenetére
Talán a hosszú pipeline-ok és a másfajta elágazásbecslés miatt. Vagy a DOS futási sajátosságok miatt. Ki tudja. Ez is inkább csak sejtés.
Ja amúgy nekem:
200*8.5 XP, 7-3-3-3 DDR400, 10-15 M :
64.32 sec, és ez szinte hajszálra megegyezik egy másik ugyanilyen géppel. Valahol a 2x-es hozzászólás körül, (bdav).
[Szerkesztve] -
-
peltar
tag
Még egy kis tuning a teszt kedvéért :D
Órajel Sebesség Futási idő Teljesítménynövekedés
1533(133*11,5) növekedés 69,63s
1916(166*11,5) 24,9% 55,77s 24,8%
2083(166*12,5) 35,8% 51,43s 35,3%
2119(163*13) 38,2% 50,22s 38,6%
2166(166*13) 41,2% 49,33s 41,1%
Kérdés: Az a 2166Mhz mennyinek felel meg az AMD +-os számozásábam?
Bár ott már nem stabil de azért érdekelne.
UI: A teszt még nem az 1.3 verzióval készült, azt csak most vettem észre, és lusta voltam újra megcsinálni.
Szerk: A Tab-okat miért nem szereti a motor? :(
[Szerkesztve] -
WolfByte
tag
Ismét itt :)
Köszönöm a hasznos hozzászólásokat és észrevételeket is! Kipróbáltam azt hogy tömbbe rendezem a dolgokat, viszont a tömb méretéből és a DOS környezet memóriatulajdonságaiból adódóan nagyon csúsztak az eredmények és nem jön ki olyan szépen az órajelből adódó különbség (nagyon variatív lett), ezért ez elvetve, mindenesetre érdekes a megoldás, alacsony prímek keresésére határozottan gyorsabb! Thx :D
A bugról annyit hogy elfelejtettem a <2 kikötést beletenni, de javítva, kb 5 perc múlva fent lesz a siteon az 1.3 verzió és mostantól jelölni fogja a filelogban a használt verziószámot is. Nem terveztem ilyen nagy volumenű projektnek, de ha tetszik és esetleg más hasonlóan egyszerűen kivitelezhető benchmark ötleteitek vannak, szívesen megcsinálom!
A Celeron-ok is Intel termékek, mégis nagyon jó eredmény produkálnak az összesített statban. P4 central processing unit magja valószínűleg a szerkezeti felépítéséből adódóan (pontos technikai hátterét nem ismerem) lehet jobban szereti a multitask feladatokat :t -
fokukac
nagyúr
egész jól elszórakozgattam ezzel a progival ! :-)
A Konfig : EPox 8RDA3+, AMD Barton 2600+, 2x256 MB, 400 MHz Kinsgton memória (CL3)
Az alaplapi buszsebesség : 200 MHz
1. eset :
1900 MHz (így szoktam használni) 55.88 mp
2. eset :
2100 MHz 50.38 mp
3. eset :
2300 MHz 45.98 mp
2300 MHz-n most próbáltam először... ehhez már feszültséget kellett emelni... -
#72
Alvin_ti4200
félisten
Alvin_ti4200
félisten
Keresési tartomány: [ 10000000 .. 15000000 ]
Futás ideje: 53.85 mp
Net alatt nyomtam.
CPU: 2000+@11,5*174(2001 MHz)
RAM: 2*256 MB DDR333@348 MHz(CAS 2,5), Top Performance On a BIOS-ban. -
válasz
VladimirR
#69
üzenetére
http://www.cs.elte.hu/~jaksy/elte/rsa/
Polinomidejű: olyan probléma, amelyre igaz, hogy n méretű adathalmaz esetén a megoldáshoz maximálisan szükséges idő kifejezhető n polinomjával, azaz pl. n^2, n^8 stb. Akkor nem polinomidejű, ha pl. 2^n idő kell hozzá, azaz az n a kitevőben van.
Pl. a primszamkereses nem az, mert egy n jegyu primszam megtalalasa/bizonyitasa x^n-el aranyos. -
Terminus_
aktív tag
Pár évvel ezelőtt én is írtam ilyen programot, de az az igazsag, hogy ezek az algoritmusok (a gyökeig keresés és az Eratoszthenész-szitája) nem polinomidejűek. Van viszont egy, ami polinomidőben is működik, csupán annyi a hátránya, hogy az eredménye nem biztos (de a hiba elhanyagolhatóan kicsi). Sajnos fejből most én sem tolom, de ha gondoljatok utananézhetek. Bár gyanítom itt nem, az volt a cél, hogy minnél több prímszámot talaljatok meg... Meg gondolom, akkor nem Pascalban lenne írva a program.
-
Cathfaern
nagyúr
Pontosan, mégpedig azért nem, mert ha az 1 prím, akkor egy szám nem bontható egyértelműen prímtényezők szorzatára (pl. ha az egy prím, akkor a 6 felbontása lehet: 2*3; 2*3*1; 2*3*1*1; 2*3*1*1*1; stb.)
Benchmark:
1300Duron (100Mhz FSB); 133Mhz-en futó 512 SDRam; Mercury kt266A alaplap:
10.000.000-15.000.000: 87,62 mp
Háttérben DC++ ment.
[Szerkesztve] -
SmithT
csendes tag
Lehet, hogy nem tartozik ide, de azért elmondom:
Van egy kevésbé számolásigényes megoldás is (bár ez a memória kárára megy): veszünk egy marha nagy tömböt, kezdetben az elemek értéke 0 (ügyesebbek akár bitvektorral is próbálkozhatnak :) ).
Minden elemhez hozzárendeljük a pozitív egész számokat (1-től n-ig)
Ezután elkezdjük a számolást... 1 prím, OK.
2 prím, OK. Ezután megjelölünk minden második számot 2 után (4, 6, 8...) avektor végéig. A megjelölt számokkal nem kell tovább foglalkozni, azok összetett számok. A következö lépés, megkeressük 2 után a legelső jelöletlen számot (ez a 3, és mivel jelöletlen, ezért prím). Most minden harmadik számot megjelöljük a 3 után, majd megkeressük a 3 után legelső jelöletlen számot... stb. a vektor végéig.
A jelöletlen számok lesznek a prímek.
Bár tudom itt a számolás a lényeg, de azért a programot is lehet optimalizálni.
Amúgy az eredmény: 75.57 az aláírásban szereplő konfiggal.
[Szerkesztve] -
Hequila
őstag
:O:O:O:O:O
Ilyet én is csináltam már régebben, nyilvánossárga is akartam itt hozni. Az én változatom elég számolásigényes módon számolja a prím számokat, és a végén nem időt ír ki, hanem pontot ad.
:O:O:O:O
Elkéstem. De he teljesen kész lesz (most még csak amolyan alpha verzió), akkor én is közzéteszem. -
TexT-BoY
addikt
itt van a hardver infom:
alaplap:
Giga-Byte GA586TX2
PU típusa Intel Pentium MMX, 233 MHz
Alaplap neve Gigabyte GA-586TX2 (3 ISA, 4 PCI, 4 SIMM, 2 DIMM)
Alaplapi lapkakészlet Intel Triton 82430TX
Rendszer memória 256 MB (SDRAM)
BIOS típusa Award Modular (12/09/97)
Megjelenítés:
Videokártya Viper V330 (4 MB)
3D gyorsító nVIDIA RIVA128
Képernyő EIZO FlexScan F56
Creative SB Live! Player 1024 Sound Card
QUANTUM FIREBALLlct20 20 (19 GB, 4500 RPM, Ultra-ATA/100)
52*LG cdrom
nagyábol ez a lkotja áűdesanyám konfigját:DD -
bdav
őstag
Tehát ''p'' számig az összes n>0 egész számmal elosztja ''p''-t, és ugy nézi meg? Mert elvileg nem kell az összessel, csak a ''p'' szám négyzetgyökénél kisebbekkel, ha azok közt nincs osztó, akkor a szám prímszám.
amugy
10-15 millioig
64.30 mp
a gép: Athlon XP 200*8,5, Via KT600 csipszet 512 full noname 400-as ram idözitéseit nem tudom :B
[Szerkesztve]
[Szerkesztve] -
WolfByte
tag
Megnézi hogy az adott számnak van-e osztója. Van egy prim:boolean=true változó, ha talált osztót akkor false és a belső ciklus megy tovább a külsőbe, ahol ha prim igaz kiírja ParamStr=1 esetén majd következő páratlan számot nézi és elkezdi megint vizsgálni.
nézd meg a forrását, ''ciklus amíg'' felépítésű
Kár hogy Pascallal nem tudok túl sokat optimalizálni, de azért így is szépen kijön hogy mennyit számít az órajel :U
[Szerkesztve] -
WolfByte
tag
Sziasztok!
Összedobtam egy kisebb Turbo Pascalos toolt, ami a processzort brute force módon megdolgoztatja, méghozzá prímszámok keresésével. Szedjétek le, próbáljátok ki és ha tetszik lehet dícsérni, de nem kötelező szeretni, mindenesetre ebben a témában lehet megtenni az észrevételeket.
Letölthető innen a forrás és a futtatható állomány egyben:
[L]http://web.axelero.hu/wolfbyte/primszam.zip[/L]
Keressetek mondjuk 10,000,000 és 15,000,000 tartományban, egy 2ghz körüli proci 50mp-ig szenved vele kb. Ha indítási paraméternek 1-et kap a primszam.exe, akkor ki is írja a megtalált számokat.
Prím-bencmarkra fel! :D
[Szerkesztve]
Aktív témák
- HIBÁTLAN iPhone 13 128GB Red -1 ÉV GARANCIA - Kártyafüggetlen, MS3536,100% Akkumulátor
- Dell USB-C dokkolók: (K20A) WD19/ WD19S/ WD19DC + 130W, 180W, 240W töltők
- HP ZBook Firefly 14 i7-1165G7 32GB 1000GB 14" FHD 1 év garancia
- GYÖNYÖRŰ iPhone 13 Pro 128GB Sierra Blue -1 ÉV GARANCIA - Kártyafüggetlen, MS3389, 94% Akkumulátor
- Bomba ár! Lenovo ThinkPad T470 - i5-G6 I 8GB I 256GB SSD I 14" FHD I HDMI I Cam I W10 I Garancia!
Állásajánlatok
Cég: PCMENTOR SZERVIZ KFT.
Város: Budapest
Cég: CAMERA-PRO Hungary Kft.
Város: Budapest