Tour de Primes 2021

[RoKro]

Tak kdo se chystá na celoúnorovou honbu za prvočíslem?
Jakou strategii chcete uplatnit? Najít cokoliv, co se vejde do TOP 5000, aby byl aspoň nějaký odznáček? Takže drtit co nejvíc malých jako GFN 16 na GPU a PPSE na CPU? U toho bacha, u PPSE dosud záleží na rychlosti odevzdávání, tam nejsou malé a velké tasky (protože i ty velké jsou malé).
Nebo risknete nižší pravděpodobnost, ale chcete vyšší výhru, tzn. ulovit nějaké mega-prvočíslo? Takže PPS-Mega na CPU a GFN17 Mega na GPU?
Nebo míříte ještě výš a chcete nějaké dvoumegové?
Nebo zvolíte jiný přístup pro CPU a jiný pro GPU?
Pochlubte se.
Já o tom zatím přemýšlím, asi nepojedu PPSE ani GFN16.

[® Plšák Ráďa ®]

Těším se, to určitě. Ale kazí mne představa, že zde je už Amper a šance se ztenčila na PF
Vidím to na GFN 17 low + PPS a kdyby vyšlo to malé prvočíslo přešel bych na GFN 17 Mega + PPS

[Honza]

Mezi GFN low a GFN MEGA není velký rozdíl v čase výpočtu, navíc GFN17 Mega má další badge, ale GFN 17 Low nebude tak populární a má lepší šanci na PF, to je asi správná úvaha.

Podle mě je lepší, když se na začátku jedou menší kandidáti na alespoň nějaký úlovek, pokud má člověk řekněme domácí výkon.
Přejít pak na MEGA.
Pokud má člověk MEGA, tak jít na SR5 či GFN18 - tady se může https://www.primegrid.com/img/badges/tdp_2019_red.png, tedy největší provčíslo během TdP.
V podstatě stačí být poslední, kdo reportuje v daném podprojektu prvočíslo.
Kdyby se nenašlo žádné větší než GFN17, stačí reportovat nejnovější nález, který bude o pár číslic větší.

Mě se tato taktika osvědčila, ale bylo v tom i nemálo štěstí...
beijinghouse reportoval 2019-02-28 10:26:29 MEGA dlouhé 1,087,166, mě se poštěstilo 2019-02-28 17:56:52 s velikostí 1,087,268, kdežto další 288larsson oidevzdal až další den 2019-03-01 12:02:33 s velikostí 1,087,414

[RoKro]

Nojo, Ampere je tady, pokrok nezastavíš.
Krátce jsem sjel pár úloh na RTX 3070 MSI Ventus Dual a to samé na rychlé vodou chlazené RTX 2080. Jen pro zajímavost ... 3070 jsou ty kratší časy.
Asi pojedu GFN 17 Mega. Na 16 je strašná konkurence a 17 Low je o ničem, není to mega a počítá se to jen o něco málo rychleji.

obrázek_2021-01-18_223831.png (38.02 KiB) Zobrazeno 4880 x

[RoKro]

Myslím, že PPSE už bude letos dost nevýhodnou volbou. Když to vezmu velmi hrubým odhadem, tak PPS se počítá 2x tak dlouho, co PPSE, ale u PPS jsem první vždy (používá ultrakrátké ověřovací jednotky), ale u PPSE budu se štěstím první v 50%, takže se počet jednotek dokončených jako první vyrovná, ale PPS jsou skoro 2x tak velká, kolem tisící pozice v TOP 5000, bude za ně víc bodů, kdežto PPSE se umísťují až za 4. tisícovkou a brzy budou z TOP 5000 vytlačeny novějšími nálezy. Tak to jen taková úvaha.

[Honza]

Ještě není od věci zohlednit samotnou šanci na nalezení.
Tedy např. že jít do GFN18 s mým výkonem není zrovna perspektivní vyhlídka na úspěch a že bych se - alespoň zpočátku - měl spokojit s nižším cílem.

[Albert]

Loni členové CNT nalezli celkem 13 mega prime a z toho sedm v únoru, což je skoro neuvěřitelné, o RoKrově třech ani nemluvě .

[RoKro]

Vloni to bylo asi opravdu extrémní štěstí. Letos asi pojedu od začátku do konce GFN17, a to na jediné RTX 2080.

[RoKro]

Nemáš Honzo info o nějakém statistickém rozložení prvočísel v jednotlivých projektech? Něco jako že u GFN-17 to vychází v průměru jedno ze 30 tisíc testovaných (vycucáno z prstu).
Že by si člověk mohl otestovat a spočítat, kolik úloh daného podprojektu je schopen za únor odevzdat a porovnal by si to s nějakou tou statistickou četností aby viděl, co mu ještě dává smysl a měl data pro rozhodování, jak nízkou pravděpodobnost ještě risknout s vidinou větší výhry.
Od PPS-Mega asi bude velký skok k PPS-DIV a SR5 a další skok k TRP. V nic většího už podle mě nemá reálně smysl doufat, to už je fakt jen sázka do loterie.

[Honza]

Obával jsem se, že ta otázka padne

Myslím, že už jsem někde uváděl ve formátu průměrně jedno prvočíslo každých x testů.

Ono se to dá odvodit i od velikost kandidáta, viz níže.
To zhruba také odpovídá kreditu - pak by otázka byla, kolik musím propálit kreditu, abych našel...ale to je zase závislé na mnoha jiných věcech, jako FFT, efektivita HW (CPU, AVX-512, GPU, MT).

The difficulty of finding a prime is roughly proportional to X^3 * ln(X), where X is the number of digits in the prime.
So it's about 3000 times harder to find a million digit prime than it is to find a prime with one hundred thousand digits.
This takes into account both the fact that larger primes are much rarer as well as taking much longer to run each individual test.

K otmu kolik testů na prvočíslo je jednoduchá odpověď u SGS - lze to odvodit ze statistik, velikost testů se prakticky nemění.

Nejlepší odpověď, které věřím a je s příkladem je tato (sorry, tady to neumí mocniny a vůbec matematický zápis).
The number of candidates for one prime is e-γ log(N) / log(pmax) where γ is Euler's constant and pmax is the sieve limit.
For example, if N is a megaprime then N ~ 10^999999. For GFN-17, pmax = 250000·10^15.
Then 0.5614594836 log(10^999999) / log(250000·10^15) = 27525.
The probability of finding a prime is 1 / 27525 for GFN-17 Mega.

[Honza]

Ha, tak jsem něco našel, jsou to data asi 2 měsíce stará, takže platná.

Důležité podle mě je třeba mít na paměti, že prvočísla nejsou rovnoměrně od sebe - jsou nepředpověditelná. Někdy se stane, že na jednom projektu jsou vedle sebe, pak dlouho nic, pak jedno, pak dlouho dlouho nic a pak bac.
Jasně, tohle neovlivníme, jenom aby někdo nebyl zklamaný, že už na SGS udělal 15000 testů a nic. Jsou lidi, co najdou prvočíslo po 1000 testech, a jsou lidi, kteří třeba i po třínásobku průměru jsou na suchu.

Kód: Vybrat vše

Project                      Errorpercent       Completed tests  Primes found  Primeodds Possible bad results  Possible missed primes
321 Prime Search             0.000655883772445        1,258,351            10  125,835.1                825.3       0.006558837724455
Cullen Prime Search          0.000655883772445          394,408             2  197,204.0                258.7       0.001311767544891
Extended Sierpinski Problem  0.000655883772445          511,556            11   46,505.1                335.5       0.007214721496900
Generalized Cullen Woodall   0.000655883772445          433,067             4  108,266.8                284.0       0.002623535089782
Prime Sierpinski Project     0.000655883772445          380,245             4   95,061.3                249.4       0.002623535089782
Proth Prime Search           0.000655883772445       50,181,192          4743   10,580.1             32,913.0       3.110856732708800
Proth Prime Search Extended  0.000655883772445      144,177,546         16067    8,973.5             94,563.7      10.538084571881200
Proth Prime Search Mega      0.000655883772445        7,084,469           209   33,897.0              4,646.6       0.137079708441101
Fermat Divisor Search        0.000655883772445        2,498,903            44   56,793.3              1,639.0       0.028858885987600
Seventeen Or Bust            0.000655883772445          240,677             1  240,677.0                157.9       0.000655883772445
SR5                          0.000655883772445        2,638,343            58   45,488.7              1,730.4       0.038041258801837
SGS                          0.000655883772445       70,598,141          4869   14,499.5             46,304.2       3.193498088036930
TRP                          0.000655883772445        1,634,107            15  108,940.5              1,071.8       0.009838256586682
Woodall Prime Search         0.000655883772445          576,858            10   57,685.8                378.4       0.006558837724455

[RoKro]

Díky moc za data. Dávám ti malej bezvýznamnej kudos

Snad to chápu správně a ta pravděpodobnost je ve sloupci Primeodds - bylo potřeba průměrně tolik testů, aby se našlo jedno prvočíslo.
Jasně že rozložení je nerovnoměrné, ale dává to aspoň nějaký obrázek.

[Honza]

A další apeskt, který už může být zahrnut v minulé tabulce (nejsem si jist), ale je důležitý - a sice kam až došel sieving.

Pokud by sievingh pro PPS Mega a PPS DIV by stejný, tak:
Očekávaných prvočísel v rámci PPG Mega je 2,5 více na testované kandidáty, než PPS DIV.

A když se vezme v úvahu délka výpočtu, tak najít PPS DIV je 15.6x obtížnější/náročnější, než PPS MEGA.

Tohle už není tak uživatelský přístup, ale chci tím osvětlit, že PG rozhodně neběží stylem "tady jsou kandidáti a chropejte", ale zvažuje se optimální sieving, ověřuje se kvalita stále se vyvíjejíchc aplikací a také se zpětně posuzuje, jestli výsledky odpovídají teoretickým předpokladům tohoto typu.

The likelihood that N is prime is e^gamma * log(p_max) / log(N) where p_max is the sieve limit and e^gamma ≈ 1.781.
If the sieve limits are identical for PPS mega and DIV (?),
Prob(mega) / Prob(div) = log(2^8388099) / log(2^3345000) = 8388099/3345000 = 2.5 times more likely.
If you take into account the computation time, the ratio is 2.5^3: 15.6 mega ⇔ 1 div.

[RoKro]

Ta tabulka je za celou historii PG, předpokládám, takže nemusí úplně odpovídat současné situaci, třeba byly dřív jiné hloubky sievingu, třeba se v nižších testovaných rozsazích ta prvočísla vyskytovala s jinou četností, než kde jsme dnes, třeba se u některého podprojektu za jeho historii hodně změnila velikost kandidátů a u jiného jen málo, třeba ...
Z historické tabulky třeba vychází poměr Mega:DIV = 33897:56793 => 1,67 krát víc provočísel Mega než DIV (ve stejně početném vzorku), kdežto ty píšeš o poměru 2,5 krát pro současný stav.

Mně šlo o nějakou řádovou představu, abych si po doplnění časů výpočtu udělal obrázek, jestli jsem u daného podprojektu se svým výkonem schopen za měsíc prozkoumat 5%, 40%, nebo 120% počtu kandidátů, ve kterém by se statisticky mělo vyskytovat jedno prvočíslo.
A ukazuje se třeba, že ačkoliv kandidáti SR5 jsou o něco málo menší, než PPS-DIV (2281172 číslic vs 2525929 číslic), a ačkoliv historická četnost nálezů SR5 je vyšší, než PPS-DIV, tak časy výpočtu SR5 jsou proti PPS-DIV o tolik vyšší, že je v reálu pravděpodobnější najít to větší PPS-DIV, než menší SR5.
Snad jsem tedy všechno pochopil a aplikoval správně
Nicméně se svým výkonem zůstanu ještě o level níž u PPS-Mega.

[Honza]

Určitě jsi do toho prokoukl dostatečně

S tím SR5 může být, že napočtené časy jsou ještě staré před optimalizací LLR2, která byla pro b<>2 nepříliš efektivní.
A také časy se mohou dost odrazit podle HW, typicky velikost CPU cache vs FFT, to je lepší vyzkoušet.

[RoKro]

Samozřejmě jsem pracoval se "svými" časy

[Albert]

Kde je ten příspěvek o tom předpočítávání ?

[RoKro]

Sám jsem si ho smazal, vyhodnotil jsem jako nevhodné to tu doporučovat.

[® Plšák Ráďa ®]

Sice turnaj začíná za 11 hodin , ale už jsem si spustil stroj. Večer má přijít mráz, tak ještě vyvětrávám byt a to teplo z výpočtů se bude hodit Pojedu na CPU 2x PPS a na GPU GFN17low.

[RoKro]

Na CPUčkách taky pustím PPS a kdyby se poštěstilo něco najít, pak bych přepnul na PPS-Mega.
GPU bude rovnou zkoušet GFN-17-Mega.
Držím palce všem CNŤákům!