Problem jest następujący.
Dane wejściowe: liczba całkowitan
Wyjście: najmniejsza liczba pierwsza większa niż n
.
Wyzwanie polega na podaniu najszybszego możliwego kodu. Przetestuję kod na wartościach zaczynających się od rozmiaru z grubsza 10^8
10^200
i podwajających rozmiar, aż zajmie to więcej niż minutę i 10 sekund na moim komputerze.
Zwycięski kod znajdzie kolejną liczbę pierwszą dla największego rozmiaru wejściowego.
Dla porównania, proste sito napisane w pythonie jest w stanie znaleźć kolejną liczbę pierwszą większą niż 10^8
za około 20
sekundy.
Wymóg, że mogę to przetestować na moim 4-GB RAM Ubuntu jest ścisły. Cały kod musi być wolny (w obu aspektach), a jeśli korzysta z bibliotek, muszą być również bezpłatne i łatwe do zainstalowania. Wszelkie zgłoszone fałszywe liczby pierwsze natychmiast zdyskwalifikują zgłoszenie.
Przyznam osobne wyróżnienia dla zwycięzców w każdym języku programowania, jeśli kod jest w całości napisany w tym języku bez użycia zewnętrznych bibliotek. Będę również utrzymywać bieżący stół w najszybszym czasie w trakcie trwania zawodów, aby ludzie mogli zobaczyć, jak sobie radzą.
Tabela do tej pory
- Pyton. Zdumiewającą
357
liczbą pierwszą343239883006530485749095039954069660863471765007165270469723172959277159169882802606127982033072727748864815569574042901856099399985832190628701414555752857600000000000000000000000000000000000000002872284792758930912601189043411951050852357613658978971208596097634095500808832510259693761982135208603287199546795000697807728609476163156438356035166156820611
była liczba końcowa poniżej 10 sekund z użyciem kodu dostarczonego przezprimo
. Czy ktoś pokona ten pierwszy wpis?
źródło
fast next prime function
.Odpowiedzi:
Python ~ 451 cyfr
Jest to część biblioteki, którą napisałem dla problemu podziału na czynniki pierwsze , z usuniętymi niepotrzebnymi funkcjami. Wykorzystuje test pierwotności Baillie-PSW , który jest technicznie testem probabilistycznym, ale do tej pory nie są znane pseudopierwsze - a nawet nagroda pieniężna, jeśli możesz ją znaleźć (lub za dostarczenie dowodu, że nie istnieje) .
Edycja : Nie zdawałem sobie sprawy, że Python ma wbudowane modułowe potęgowanie. Zamiana własnego na wbudowane powoduje wzrost wydajności o około 33%.
moja_math.py
Przykładowy skrypt testowy:
Wybrano współczynnik 317, ponieważ jest to w przybliżeniu pierwiastek kwadratowy z
10000
, dodając około 2,5 cyfry na iterację (i ponieważ podwojenie było zbyt wolne, aby usiąść). Dane wyjściowe pokazują bieżącą liczbę cyfr i czas potrzebny.Przykładowe wyniki:
Cały kod jest teraz kompatybilny z Python 3.
źródło
next_prime((2^520)*(10^200))
około 15 sekund na moim komputerze, więc na pierwszy rzut oka jest to dość imponujące. Jednak ...next_prime((2^520)*(10^200),proof=False)
zajmuje 0,4 sekundy, ponieważ sprawdza tylko pseudoprimality. Twoje twierdzenie, że „nie ma znanych pseudopierwszych liczb”, jest znikomo przekonujące, ponieważ liczba bitów przekracza 64. W przypadku 357 cyfr nie przekonuje mnie nawet brak kontrprób.C ++ z GMP: 567 cyfr
Wykorzystuje implementację Millera-Rabina w GMP. Może zwrócić fałszywie dodatni, ale powodzenia trafienie w jedno z prawdopodobieństwem 2 ^ -200.
Znajduje
10^200 * 2^1216 + 361
liczbę pierwszą (567 cyfr), zanim z czasem uruchomię ją na moim wolnym laptopie.źródło
Perl z modułem GMP, 1300 cyfr
Korzystanie z mojego modułu Math :: Prime :: Util i jego zaplecza GMP . Dokładny punkt podziału zależy od komputera i tego, czy masz najnowszą bibliotekę GMP. Cały kod jest bezpłatny (moduły znajdują się na github i CPAN, a GMP jest swobodnie dostępny). Uruchomiłem je na Ubuntu AWS, a także na Ubuntu na pulpicie (i Fedorze, AIX i NetBSD itp.).
Kod podstawowy znajduje się w C i C + GMP. next_prime z MPU widzi, że liczba jest za duża i przesyła ją do zaplecza GMP (lub czystego kodu Perla, jeśli zaplecze nie jest zainstalowane). To przekreślije i konwertuje na mpz, i przekształci wynik z powrotem w typ obiektu wejściowego lub Math :: BigInt. sam next_prime:
Prawdopodobny test główny to:
Wszystko przed ES BPSW to tylko optymalizacja, której oczywiście chcemy na next_prime. next_prime jest również zaimplementowany w Perlu przy użyciu modułu Math :: BigInt (w rdzeniu z opcjonalnymi zapleczami Pari i GMP). To robi AES BPSW (jak Pari), ale nie jest tak zoptymalizowany.
Myślałem o zaletach wersji opartej na sicie częściowym, wykorzystując zakres, na przykład, 2 zalet. Po prostu nie jestem pewien, czy to naprawdę byłoby lepsze, ponieważ przez większość czasu robiliśmy niepotrzebne przesiewanie, ponieważ przerwa była niewielka, a czasami dla dużej przerwy musielibyśmy to powtarzać wiele razy.
Biblioteka implementuje ECPP (w tym certyfikaty), abyśmy mogli przetestować wynik, ale 1200 cyfr jest naprawdę zbyt duże dla niewielkiego domyślnego zestawu dołączonych wielomianów (istnieje metoda pobierania większych zestawów - proofy zajęłyby nieco mniej 15 minut, co jest nieco szybsze niż APR-CL Pari, ale nieco wolniejsze niż mpz_aprcl WraithX). Jedną wadą ECPP w porównaniu z APR-CL jest to, że ma większą zmienność czasową, więc istnieje duża szansa, że przekroczy on 10 sekund w stosunku do pewnej liczby, zanim upłynie średni czas. Z dowodem uważam, że jesteśmy ograniczeni do czegoś w zakresie 400 cyfr, chyba że zezwolimy na oprogramowanie wielowątkowe.
Postanowiłem spróbować z tą samą sekwencją, której używał primo. Doszedł do 1191 cyfr, ponieważ w tym miejscu osiągnęliśmy lukę 18138. Testowałem również kod primo przy użyciu najnowszego my_math.py. Dochodzi do 630 cyfr z sekwencją 10 ^ e i 641 z jego sekwencją. Bardzo imponujące, jak na kompaktowy, całkowicie Pythonowy kod bez wielu testów wstępnych.
źródło
Math::GMP
w sposób, który nie jest zbyt marnotrawny w przypadku tworzenia / niszczenia referencji MPZ.$x = new Math::GMP(0); $x += 3 for 1..1000000
. Kiedy skończę, wyślę do cpan; będziesz jednym z pierwszych, którzy się dowiedzą;)