10^9-ta liczba pierwsza poniżej 400 ms

Mieszcząc się poniżej 500 loc napisałem kod w c++, który oblicza 10^9-tą liczba pierwsza poniżej 400 ms i 10^10-tą poniżej 3400 ms. Na jednym wątku Apple M3 Pro. Wiem, że istnieje Kim Walisch, który robi tego typu rzeczy dużo szybciej, ale on ma około 50k loc i 5 zewnętrznych bibliotek. Pytanie brzmi czy ma to jakąkolwiek wartość?

@anckor: Spoko, zawsze lepiej dodawać do projektu kod bez zależności.
Wrzuć na GitHub.
W jakim języku pisałeś?

Ah zapomniałem dodać w pierwszym poście. W c++ ta implementacja powstała. Potrzebowałem to skonsultować z ludźmi bo LLMy na zmianę mi piszą albo że jest to rewolucja w matematyce warta zmonetyzowania albo, że jestem o rzędy wielkości za wolny. Zależy co im się wylosuje.

@anckor: Sam napisałeś, że Kim Walisch zrobił znacznie szybsze rozwiązanie.
To oznacza, że serio Twoje rozwiązanie nie jest rewolucyjne. Liczy się efekt końcowy.
Chyba, że opracowujesz rozwiązanie na platformy, które nie udźwigną większych aplikacji, to wtedy porównywanie 500 loc vs 50k loc ma sens.

Jeśli jego rozwiązanie jest open source i te zewnętrzne biblioteki są open source, to mógłbyś skonstruować minimalistyczną, niezależną wersję algorytmu.
I od tego miejsca dalej to optymalizować.

Sam napisałeś, że Kim Walisch zrobił znacznie szybsze rozwiązanie.

Tak ale to nie ma znaczenia. Kim Walisch jest open source ze swoją biblioteką ale to jest GPL, a wiadomo co się wiąże z GPL. Plus jest ciężki i ma dużo dependency.

Ja może nie do końca sprecyzowałem pytanie. Chodziło mi pierwotnie o to czy biblioteka tego typu na kilkaset linii kodu, bez licencji GPL i bez dodatkowych bibliotek może mieć jakąś wartość (edukacyjną, użyteczną, marketingową). Tak, jest wolniejsza od Kima, ale ja w tym momencie nie konkuruję jedynie szybkością, tylko całkowitym efektem na który składa się i lekkość i szybkość. Tak samo jak na przykład pyprimesieve, też nie jest najszybsza na świecie, ale ma dużą wartość i jest używana:

pyprimesieve outperforms all of the fastest prime sieving implementations for Python.

For comparison, on an Intel Core i7 2GHz, pyprimesieve populates an entire Python list of the first 50,847,534 primes in 1.40 seconds.

Mój kod jest szybszy niż pyprimesieve. No ale ja też nie użyłem Pythona.

No pewnie, ceni się, że jest małe i niezależne ;)

Ale z drugiej strony, ja nigdy w projektach nie potrzebowałem liczb pierwszych.

Podejrzewam, że jeśli miałbym jakiś projekt z nimi, to mógłbym określić ich zakres i dołączyć gotową bazę danych z liczbami pierwszymi do projektu.
Nie musiałbym ich nawet generować w swojej aplikacji.

Wiem, że istnieje Kim Walisch, który robi tego typu rzeczy dużo szybciej, ale on ma około 50k loc i 5 zewnętrznych bibliotek. Pytanie brzmi czy ma to jakąkolwiek wartość?

W sensie, czy jest wartość w tym, że masz wolniejszą implementację, ale mniej zależności i mniej linii kodu? No niebardzo. Nawet powiedzmy w szczególnym przypadku embedded, gdzie faktycznie może mieć wartość mniejsza ilość kodu, nikt nie będzie się bawił w liczenie takich rzeczy w runtime.

Nie kojarzę konkursu na najlepszy stosunek prędkości do ilości kodu. Ale wartość może to jak najbardziej mieć edukacyjną. Pokaż :)

kelog napisał(a):

W sensie, czy jest wartość w tym, że masz wolniejszą implementację, ale mniej zależności i mniej linii kodu? No niebardzo. Nawet powiedzmy w szczególnym przypadku embedded, gdzie faktycznie może mieć wartość mniejsza ilość kodu, nikt nie będzie się bawił w liczenie takich rzeczy w runtime.

OP wspominał też, że mniej zależności to również ominięcie licencji GPL.

kelog napisał(a):

Nie kojarzę konkursu na najlepszy stosunek prędkości do ilości kodu. Ale wartość może to jak najbardziej mieć edukacyjną. Pokaż :)

W grze EXAPUNKS histogramy ładnie wyglądają ;)

anckor napisał(a):

Mieszcząc się poniżej 500 loc napisałem kod w c++, który oblicza 10^9-tą liczba pierwsza poniżej 400 ms i 10^10-tą poniżej 3400 ms.

to bardzo ładnie, chyba podobnie jak każdy student informatyki.

Pytanie brzmi czy ma to jakąkolwiek wartość?

Nie ma, algorytmy stosowane w kryptografii są w stanie znaleźć liczbę pierwszą mające ponad 1000 cyfr w kilka milisekund, ta twoja ma zapewne zaledwie 20 parę cyfr i jest za mała żeby być do czegokolwiek użyteczna.
Ostatnia znaleziona liczba jest szacunkowo 10^24000000 z kolei, twoja 10^10 liczba brzmi przy tym śmiesznie.
Istniejące algorytmy potrafią znajdować nowe liczby szybciej niż je zapisywać na jakimkolwiek nośniku, liczby pierwsze wbrew intuicji są bardzo powszechne i jest ich naprawdę w cholerę dużo, dlatego odpadają takie metody optymalizacji jak sito czy cokolwiek polegające na zapisywaniu znalezionych już liczb bo szybko braknie ci nośników na świecie żeby je spisać - liczba liczb pierwszych mniejszych od największej znalezionej jest większa od ilości atomów we wszechświecie.

Nie jest nigdzie potrzebne generowanie ich po kolei i nie ma to sensu. Twoje optymalizacje zapewne nie mają zastosowania dla dużych liczb. Sprawdzenie ostatniej liczby zajęło około 300 000 godzin CPU, gdyby ci się udało to zoptymalizować to byłoby coś, ale już teraz używane są do tego mega sprytne sztuczki, skróty i metody szacowania przed właściwym sprawdzeniem i potrzebujesz do tego więcej niż jednego rdzenia M3.

Spine napisał(a):

Podejrzewam, że jeśli miałbym jakiś projekt z nimi, to mógłbym określić ich zakres i dołączyć gotową bazę danych z liczbami pierwszymi do projektu.

Cały sens z używaniem liczb pierwszych jest taki jest że można je łatwo wygenerować, jest ich bardzo dużo i żeby zdekodować klucz trzeba zgadnąć dokładnie te same liczby. Baza gotowych liczb pierwszych zupełnie pozbawia sensu ich stosowania. Chyba że ta baza miałaby wielkość kilkuset TB

anckor napisał(a):

Na jednym wątku Apple M3 Pro.

Zatem to dobrze świadczy o ich procesorach.

obscurity napisał(a):

Sprawdzenie ostatniej liczby zajęło około 300 000 godzin CPU, gdyby ci się udało to zoptymalizować to byłoby coś, ale już teraz używane są do tego mega sprytne sztuczki, skróty i metody szacowania przed właściwym sprawdzeniem i potrzebujesz do tego więcej niż jednego rdzenia M3.

Z tego co wiem, to nie robi się "właściwego sprawdzenia", bo przy tak ogromnych liczbach jest to niemożliwe. Do generowania dużych liczb pierwszych służą algorytmy probabilistyczne, sam jeden kiedyś na studiach implementowałem (Test Millera-Rabina). Jest też test AKS.