Liczby pierwsze w C - sito Erastotenesa

_jta_ wrote:

Pytanie: czy liczby pierwsze są wykorzystywane tylko sekwencyjnie,

W zasadzie są wykorzystywane dwa razy w programie.
Najpierw algorytm sita je znajduje droga eliminacji i robi to od razu do maksymalnego zakresu czyli np. fib(10) albo fib(52). Jest to parametr podawany jako drugi.
To jest to tworzenie tablicy właśnie, dla której pamięć alokuję od razu całą do ULONG MAX.
Czyli 8 bajtowej zmiennej bez znaku.
Później właśnie sekwencyjnie pętla robi obieg pomiedzy wartościami Ciągu Fibonacciego ale leci co 2 i omija parzyste startując od nieparzystej.
To jest ten fragment:

_jta_ wrote:

a jeśli tak, to czy nie okazałoby się bardziej efektywnym wykorzystywaniem pamięci trzymanie w niej różnic kolejnych liczb pierwszych - może podzielonych przez 2, czyli zaczynając od 3: 1 (5) 1 (7) 2 (11) 1 (13) 2 (17) 1 (19) 2 (23) 3 (29) 1 (31) 3 (37) 2 (41) 1 (43) 2 (47)...

Chyba rozumiem zamysł. Tylko szczerze nie wyobrażam sobie implementacji tego przezemnie do sita Erasto, a później odwoływania sie do nich. To już działa na bitach i każda liczba ma index odpowiadający pojedyńczemu bitowi. Jak by ta twoja propozycja miała oszczędzić pamięć? Chodzi Ci pewnie o typy zmiennych do przechowywania zakresu liczbowego, prawda? Jeśli to jest typ Char podzielony na 8 bitów to już chyba więcej sie tu nie wyciśnie mimo innej metody zapisu liczb. Te liczby też muszą miec swój indywidualny index. A to jest właściwie jeszcze nie problem, bo Fib(52) = 32951280099 to 32 milardy a liczba maksymalnego indeksu potrzebnego aby iść dalej to 18446744073709551615 czyli jakieś 18 trylionów.
Problemem jest sumowanie tych liczb i właśnie zauważam, w tym co proponujesz jakis sens. Lecz jak miała by być obliczona suma tych liczb jeśli zapisuję tylko różnicę kolejnych?
Na bitach mozna robić cuda, ale ja tak nie potrafię.

Przykładowo jeśli podałeś 3 liczby pocztkowe od:

(3) 1 (5) 1 (7) 2 (11).
Jak wyznaczyć sumę liczb 1+1+2 aby dała tożsamy wynik z 3+5+7 ?

4 <> 15 , ale np. 4^2 - 1 = 15

Czy to się sprawdzi dalej?

(29) 1 (31) 3 (37) 2

1+3+2 = 6
6 <> 97 ale np. 6^2 = 36 i jak wtedy obliczyć, że to 97 aby wyznaczyć sumę liczb pierwszych w zbiorze?

Nie wiem jak tu oszczędzić czas i pamięć dalej na lepszych operacjach.

_jta_ wrote:

Trzeba w jakiś sposób kodować, ile bajtów zajmuje taka różnica - np. wykorzystywać 7 bitów na kodowanie liczby (różnicy), a jeden bit przeznaczać na flagę, że to ostatni bajt.

No tak, ale potrzebna jest akurat suma. Suma liczb pierwszych w zbiorze.
Może być jej nawet połowa dla większych wartości, bo przy następnym kroku programu się nie zmieśći w najdłuższej zmiennej.
I to jest w sumie najlepszy pomysł dla umożliwienia dalszej kalkulacji.

_jta_ wrote:

To by wyglądało tak: mamy blok pamięci przeznaczony go na flagi dla np. 4 miliardów liczb (0.5GiB), przesiewamy te liczby przez sito Erastotenesa, i pakujemy do listy różnic; następnie przetwarzamy w ten sam sposób kolejne 4 miliardy...

W trakcie liczenia sumy liczb robisz podwójne sumowanie: jedno, żeby wyliczać kolejne liczby pierwsze, drugie, żeby je sumować: s=p; loop { p=p+d; s=s+p; }.

Krótko, zwięźle to tłumaczysz, ale niestety nie rozumiem.

Poszedłem w innym trochę kierunku, bo uznałem, że tutaj już wiele się nie ugra robiąc niepotrzebnie jakieś cykle procesora na sumowaniu liczb w ten sposób co proponujesz.
Sito bitowe jest już tym, co może być najepszego w robieniu kalkulacji dla liczb pierwszych ta metodą.
Zastosowałem w programie nowe funkcje z biblioteki dla działań arytmetycznych na dużych liczbach. Ta biblioteka to GMP - The GNU Multiple Precision Arithmetic Library.

Program mimo to działa dalej szybko jak przedtem bez użycia bibioteki, czego się nie spodziewałem. Różnice czasowe sa marginale dla argumentów do Fib(50).
Obecnie obliczyłem ile jest liczb między Fib(52) i Fib(53). Jest ich tam 831993816.
Ale wynik różni się od innego podanego mi przez pewnego użytkownika o jedną cyfrę. Twierdził On że liczb jest tam 831994816. Co robi równo 1 tysiąc różnicy.
No i teraz nie wiem czy mam w programie błąd. Bo dotychczas nie kalkulowałem na tak dużych liczbach i z takiej bibiloteki nie korzystałem.
Mam jeszcze jedna sprawę w związku z implementacją nowych funkcji do programu niezbyt jasną.
Nie wiem jak obliczać liczbę niewymierną, odpowiednik float albo double. Są do tego jakieś funkcje ale nie mogę znaleźć odpowiedniej.
Konkretnie chodzi o takie działanie,


... które zastąpiło zwykłe dzielenie w postaci



i wynik nie jest dobry. Średnia avg_p ma zmienioną postać na typ mpf_t, zmienna approx_phi to też taki typ. Mimo to wynik nie wychodzi. subset_end to typ unsigned long long.

Jaką funkcję wybrać aby z tego dzielenia wyszła liczba niewymierna?

Zawsze trzymałem się z dala od takich programistycznych bibliotek, bo to czasem więcej problemów niż pożytku. Ale trzeba przyznać, że jest szybka.

Jeszcze słowo o sumie liczb tego podzbioru.
Jeśli nie mam pomyłki, to jest ona różnicą... 35859516946159618347 - 53316291173 = ???.

_jta_ wrote:

Nie wiem, jak wykorzystujesz mapę bitową liczb pierwszych, ale mam wrażenie, że przetwarzanie różnic na liczby pierwsze powinno być szybsze od wyszukiwania bitów (a pewnie najwolniejsze jest odznaczanie liczb złożonych).

Masz pewnie rację.

Tylko, że algorytm sita pochodzi oryginalnie ze strony:

https://www.geeksforgeeks.org/bitwise-sieve/

Mnie jego analiza pomogła jedynie przystosować do programu w C po zmianie typów zmiennych.
Wydaje mi się, że już bardziej optymalnie być nie może. Można policzyć to tak:

Tablica na liczby pierwsze do Fib(53) = 53316291173 zajęła mi 80% pamięci operacyjnej z 8GB. To daje jakieś 6.4 GB zajęcia pamięci na potrzeby tablicy. A to są ponad 53 miliardy bitów. Czyli 6664536396.625 bajtów.... -> 6.2 GB.
Bita bardziej nie scisnę.
A ty podajesz szacunowe obliczenia, że:

4 miliardy liczb to (0.5GiB), co daje bardzo przybliżoną do 6.2 GB wartośc dla tablicy z 53 miliardóami liczb.
Także tutaj na wykorzystaniu pamięci już nie ugramy. Nie wydaje mi się aby była możliwość zrobienia sita Erasto lepiej z mniejszym zużyciem pamięci, ale gdyby i takie cudo było możliwe i nie trzeba rezerwować pamięci dla liczb złożonych to znów można by tablicę skrócić i zrobić postęp w obliczeniach na moich 8GB RAM.

Co do samej metody zapisu w tablicy liczb pierwszych jako różnicy to nie potrafię tak przesuwać bitów w pętli aby mi się nie pogubiły.

Aktualnie pętla wygląda tak:


Gdzie n to maksymalny zakres na tablicę, i,j,k to typy unsigned long long.



Nie zrozumiałem, co oznaczają zmienne w twoim podanym poprzednio przykładzie.



Co to jest za zmienna s? Suma? P to liczba pierwsza? D w takim razie będzie oznaczało połowę różnicy miedzy kolejnymi liczbami pierwszymi?

_jta_ wrote:

Jakkolwiek używanie tabeli liczb pierwszych powinno być jeszcze szybsze, a chyba potrzebne jest przechowywanie tylko tych liczb pierwszych, dla których będziesz sprawdzał, czy są dzielnikami kandydatów na dalsze liczby pierwsze. Niestety nie orientuję się, jak gęsto są rozmieszczone duże liczby pierwsze - na pewno im większe, tym rzadziej, i przy odpowiednio dużych przechowywanie różnic, albo nawet wartości liczb pierwszych zajmie mniej pamięci, niż mapa bitowa.

Chyba nie jest jak mówisz, bo potrzebuję wszystkie liczby pierwsze z każdego podzbioru.
Tylko gdyby przechowywać ich różnicę to pętla programu miała by zdecydowanie inną postać.
W jaki sposób index w zmiennej najdłużeszgo typu, przerobic w pętli for na różnicę wartości na które wskazuje tego nie wiem.

Wyszło mi wstepnie cos takiego: Tym razem od 2.
Tablica,jest wypełniona jedynkami,a następnie zerami.
Takie bardziej klasyczne sito.
/// zgaś

To jest wedle algorytmu z wikipedii, które w pseudokodzie wyglada tak:
https://en.m.wikipedia.org/wiki/Sieve_of_Eratosthenes


Ledwie ogarniam tą postać, a jak tu dodać aby robiło przesunięcia bitowe dla różnicy kolejnych liczb pierwszych to nie mam pojecia.

_jta_ wrote:

Czy zakres uint64_t jest za mały na liczby pierwsze, z którymi masz do czynienia?

Jest wystarczający aby robic jeszcze dalsze obliczenia, kilka ładnych iteracji pętli programu.
Problemem była suma liczb zbioru, która wyszła przy Fib(53) właśnie poza zakres, dlatego zdecydowałem się na zastosowanie biblioteki GMP.
Pozdrawiam.
Jeszczę dzisiaj przedstawię kod tej wersji i licze, że może ktoś się zdecyduje puścić to u siebie na komputerze z większą ilością RAMu.
Pozdrawiam.

_jta_ wrote:

Jakby tak do niej wpisywać tylko liczby nieparzyste, to by zajęła tylko 3332268199 bajtów.

Obawiam się, że to niemożliwe, a kolega nie zrozumiał starożytnej idei sita Erasto.
Polega ona na eliminacji czynników, które nie spełniają warunków. Więc one z założenia są na początku i tworzą sito. Później dopiero je usuwamy. Można je zapisywać zamiast usuwać, ale muszą być w tablicy.
Podczas odczytu z tej tablicy można tylko kroki zrobić takie aby omijać parzyste i to mam zaimplementowane w algorytmie, co przyśpiesza działanie programu o 50% średnio.
Chyba, że rzeczywiście możliwe jest zrobienie tablicy na podstawie innej metody niż Sito Erasto, ale ja takiej nie znam, jeśli chodzi o implementację algorytmu w jakims języku programowania. Ale może trzeba poszukać, bo metody wyznaczania liczb pierwszych jakieś inne i równie skuteczne pewnie są.
No może poza tym jednym algorytmem w C++, którym podzielił się ze mną jeden użytkownik internetowych forów. Wektorowy kontener typu bool jednak jest za duży i program wykorzystuje za dużo pamięci. Jednak nie rozpracowałem tego algorytmu, bo może na bitsetach w C++ dało by radę uzyskać lepsze efekty. Ale na razie dla mnie wystarczy to co mam w C.
Tylko zapis do plików binarnych chcę zrobić i na duży dysk posłać wynik.

_jta_ wrote:

Skoro Fib(52)=32951280099, Fib(53)=53316291173, to liczby pierwsze w tym przedziale stanowią ponad 4%; jeśli jeszcze pominiemy parzyste, to wyjdzie 12 bitów na liczbę pierwszą - czyli tu nie ma co liczyć na dużą oszczędność pamięci. I chyba nieprędko można by na nią liczyć, skoro przy zwiększeniu liczb o czynnik miliard gęstość liczb pierwszych maleje o czynnik około 5 (w przedziale od 50 do 100 jest 10 liczy pierwszych).

4% to prawda. Ale nie wiem jak wyliczyłeś 12 bitów na liczbę pierwszą. Chodzi ci o jakąś średnią? Obecnie używam jeden bit na liczbę naturalną i nieważne czy pierwsza czy złożona.
No ale zapis do tablicy pojedyńczych bitów wskazujących na liczby pierwsze według inkrementowanego pojedyńczo indeksu jest możliwy tylko gdy ten index idzie według kolejności liczb naturalnych. Gdyby zrobić to tylko dla liczb pierwszych to by oznaczało chyba, że wynaleźliśmy formułe na wyznaczenie n-tej liczby pierwszej. Ale takie cuda to nie za bardzo są możliwe w C. Może na Javie tylko

_jta_ wrote:

Ciekawe, ile jest liczb pierwszych mniejszych od 2^32 - spodziewam się, że znacznie mniej, niż miliard, i pewnie by się zmieściły w 3GB (jako 32-bitowe).

Liczby które kalkuluję za pomoce tej procedurki mają już zakres ponad 32 bitowy.
A liczb pierwszych w ostatnim podzbiorze było ponad 800 milonów. Nie od początku n=1, tylko od n = Fib(52) do n = Fib(53).
Owszem one by mogłby być zapisane w plikach binarnych aby tylko jak najmniej miejsca wyszło na dysku. Pliki tekstowe z takim zbiorem są zbyt duże do tego typu kalkulacji.
Ten zakres gdzie n > 2^32 to niemałe liczby. Ale ta bibiloteka jest do dużych właśnie liczb więc może ... się doliczy kiedyś do liczb Fib(n) bliskich końcowym wartościom 64 bitowych zmiennych. Może do Fib(89) = 1,779,979,416,004,714,189.

Narazie ostatni wynik jeszcze do potwierdzenia wskazuje, że pomiedzy Fib(53) i Fib(54) jest grubo ponad miliard liczb pierwszych: 1,320,232,935.

Wynik nie jest z moich eksperymentów. Ale niedługo go sprawdzę, jak sie przesiądę na komputer z większą ilością RAM.

Załączam listing. Program działa z biblioteką GMP. Strona projektu. https://gmplib.org/



W tej wersji program oblicza sumy zbiorów ponad zakres 64 bitowej zmiennej.
Jeden mankament to taki, że nie oblicza przybliżenia do Złotej Liczby, bo typ zmiennej nie dobrałem odpowiednio.
Ale dopiero zainstalowałem tą bibliotekę, a nie jest jakoś wyjątowo trudna, jednak trochę słabo opisaną dokumentację ma moim zdaniem.

_jta_ wrote:

Ilość bitów dla liczb w zakresie / ilość liczb pierwszych w tym zakresie to około 12.24.

To co z tym ułamkiem? Nie lepiej brać wiekszy zakres o skromny 1 bit.

Wcześniej nie sprawdzałem tej zależnosci ale sprawdźmy:

Między Fib(10) = 55 -> Fib(11) = 89 jest 8 liczb pierwszych, a 34 liczby naturalne.
to 34 bity dla liczb n w zakresie i 8 bitów z liczbami pierwszymi co daje współczynnik 4.25 bitów na liczbę pierwszą

Dalej.

Fib(21) = 10946 -> Fib(22) = 17711 jest 704 liczb pierwszych, a 6765 liczb naturalnych. co daje współczynnik 9.609375 bitów na liczbę pierwszą.

I ten wskaźnik sie zwieksza pewnie wraz ze wzrosten n. Bo liczby występują coraz rzadziej chyba.

Także nie rozumiem jak wyliczasz 12 bitów miedzy granicami podzbiorów, na liczbę pierwszą.
To nie jest stała wartość. Jeśli rozumiem ten algorytm to tak to właśnie wyglada.

_jta_ wrote:

Z mojego programu wyszło, że w zakresie do 2^32 jest 203280221 liczb pierwszych

Też liczysz? Pokaż procedurkę jeśli możesz. Ja mam inną jeszcze, ale jest strasznie wolna, tylko do zakresu Fib(30) liczyła mi przez ponad godzinę. Tylko, że to wogóle inna metoda i bazuje na wzorach do wyznaczania liczby Fibonacciego, które są autorstwa francuskiego matematyka Bineta.
Natomiast to niezbyt krótki algorym i niepotrzebnie procesor się nad tym męczy.
Dużo lepsze jest zwykłe sumowanie w krokach pętli kolejnych wyrazów ciągu jak zrobiłem to w ostatniej wersji programu.

Z kolei metoda do wyznaczania liczb pierwszych jest następująca.
Ale nie potrzeba sita i tyle pamięci. Tylko z każdą liczbą naturalną sprawdza po kolei czy się dzieli bez reszty przez cały zakres liczb tylko w dwóch przypadkach.
Przy sporych wartościach liczbowych metoda sita wydaje się dużo szybsza. Ponad 3600 razy szybsza niż metoda z wzorem Bineta i poniższym kodem na wyznaczanie. liczby pierwszej.




Tylko nie robiłem jeszcze eksperymentu aby połaczyć w kodzie te dwie metody programowania. Usunąć wzór na wyznaczanie Fibonacciego autorstwa Bineta, który nawet może powodować kiepskie wyniki dające słabe przybliżenie do liczby Fibonacciego. Oraz zastosować wyznaczanie Pierwszych ale bez sita.
Ciekaw jestem ile to będzie straty na czasie poprzez niepotrzebne cykle procesora.
Najlepiej jak zrobię w tym celu eksperyment.
No ale kosztem większego czasu na obliczenia, zużycie pamięci będzie dużo mniejsze.

_jta_ wrote:

Można by trzymać te liczby w tabeli uint32_t, a oprócz nich reszty z dzielenia, żeby do zaznaczania liczb złożonych wykonywać tylko dodawania; przetwarzać liczby zakresami po 2^32 i znaleźć wszystkie liczby pierwsze mniejsze od 2^64, używając poniżej 2GB RAM (jeśli do przechowywania kandydatów używałoby się mapy bitowej), albo poniżej 4GB (a dokładniej, 3600MiB, jeśli używałoby się bajtów), w obu przypadkach przechowywałoby się tylko informację o liczbach nieparzystych.

Ale ja trzymam w tablicy typu CHAR czyli 8 bitów (255 unikalnych wartości) gdzie jeszcze podzieliłem go na 8. Czyli jeden bit na liczbę dziesiętną czyli 2 wartości na liczbę 0 albo 1. Tutaj bardziej się zoptymalizować już raczej nie da. Gdybyś wyrzucił wartości parzyste. To i tak jak zapisać o nieparzystych informację inaczej w 1 bicie. Po prostu go zgasić czyli 0.
A zapalić 1 da odpowiednie wartości dziesiętne wedle wskazanego indeksu, czyli liczby naturalnej, która jest albo nie jest liczbą pierwszą.

_jta_ wrote:

Sumy liczb pierwszych dość szybko przestaną się mieścić w uint64_t, a nawet 96 bitów będzie za mało w zakresie, jaki można w ten sposób wygenerować - wypadnie użyć (tylko do sumowania) liczb 128-bitowych. A poza tym wypadałoby podzielić te obliczenia na wiele rdzeni, a nawet wiele komputerów - przesianie przez sito Erastotenesa liczb w zakresie do 2^64 na jednym rdzeniu pewnie by zajęło kilka tysięcy lat... Czyli nie pamięci jest mało (jak jej rozsądnie użyjemy), a szybkości procesorów.

Tak, sumy już wykraczają poza zakres. Ale według mnie to program może wykonac jeszcze kilka iteracji tylko, bo tak jak mówisz za wolne procesory na sumowanie tylu liczb. Ale przypuszczam, że nie tak długo jak sądzisz, by to potrwało na 128 bitowym komputerze z dużą ilością RAM na tablicę Sita, która jest chyba jednak najszybszą metodą wyznaczania liczb pierwszych.

_jta_ wrote:

Największa różnica liczb pierwszych w zakresie do 2^32 to 336 - połowa tej liczby (czyli 168) mieści się w uint8_t, i trzymając różnice zamiast liczb można zaoszczędzić około 580MiB pamięci RAM - czyli używać bajtów (bo szybciej) i robić obliczenia używając 3020MiB.

Ale ja trzymam całą tablicę w tym typie elementu uint8_t, który daje 2^8 − 1 = 255 wartości.
Tylko w inny trochę sposób zapisuję liczby. Wydaje mi się tutaj, że twoja uwaga, mogła by skrócić typ zmiennej indexu tablicy, bo liczby indexu nie musiałały by być tak wielkie aby potrzebny był typ unsigned long long. Co rzeczywiście dało by kolejne oszczędności.
Ale jak potrafiłbyś przedstawic ta idee za pomoca kodu albo pseudokodu, to było by czytelniej.
Głównie chodzi o to aby pozbyć się z tablicy bitów zbędnych, nie trzymających jakby wskaźnika do liczb pierwszych.

_jta_ wrote:

203280221 liczb pierwszych w zakresie do 2^32 oznacza, że mniej więcej co 20-ta liczba jest liczbą pierwszą, a po zapisaniu flag pierwsza/złożona tylko dla nieparzystych oznacza, że co 10-ta flaga będzie 'pierwsza'; zapisanie informacji o tym, które liczby są pierwsze, przez podanie ich różnic (a raczej połówek różnic) pozwoliłoby użyć 8 bitów na liczbę pierwszą, a więc zaoszczędzić 20% pamięci - ale to nie jest duża oszczędność, a pamięci, przy rozsądnym jej używaniu, i bez tej oszczędności wystarczy.

Aaa teraz Cię lepiej rozumiem.
Prezentujesz całkiem inne podejście do sprawy i to mnie zainteresowało, ale 8 bitów na liczbę to nie było problemem zrobić. Wystarczyło ustawić odpowiedni typ zmiennej dla tablicy. W tym przypadku CHAR i odczytywać tylko flagę 1 lub 0. Nie przechowywałem nic wiecej w tablicy, tylko flagę 1 lub 0, albo gdyby to był typ bool w nowszym standardzie C to true albo false. Czyli i tak 8 bitów na liczbę.
Uzyskane wyniki to były liczby z zakresu ponad 2^32. Fib(49) = 7778742049 jest wieksze od 4294967295 bo to najwieksza wartość 32 bitowej zmiennej typu Integer bez znaku. Ale ten krok mam już za sobą. Obliczenia na 8 bitowej zmiennej w tablicy zajmowały bardzo mało czasu.
Dla średnich wartości 32 bitowych 2^32 ta procedura robi to w ułamku sekundy.
Do Fib(47) dojeżdzała mi w czasie 135 sekund, sumując wszystkie zbiory.
Maksymalnie na tego typu tablicy zajęły prawie 50 minut, dla najwiekszego zbioru.



Zrobiłem jednak kolejny postep i jedna liczba pierwsza to jeden bit w tablicy Tylko flaga w postaci bitu. Czyli zysk jeszcze większy niż propoujesz. To dało mi możliwośc doliczenia zbiorów liczb pierwszych w przedziałach dla max Fib(51) i Fib(52).
Ze zużyciem pamięci w granicach 50% z 8GB.



Z 80% zużyciem doliczyłem do Fib(53). Ale chcąc iść dalej, to sitem chyba tego się nie zrobi na tej ilości pamięci. Bo gdybym puścił to przywiesi mi system, a SWAP nic nie pomoże.
Nie mam obecnie dostępu do komputera z wiekszą ilością pamięci. Dlatego szukam innych algorytów. Mam jeden szybki generator liczb pierwszych w C++, ale on ma takie typy zmiennych, że nie daje rady policzyć poza zakres 32 bit. Tablica jest na najmniejszej bool, czyli flaga jest 8 bitowa, że nie pozwala policzyć większych wartości niż do F(46).
Ale ta inna metoda wyznaczania pozwoliła mi chociaż sprawdzić dotychczasowe wyniki. Potwierdzają się.

_jta_ wrote:

To jest program, który wylicza liczby pierwsze w zakresie do 2³² i wypisuje ich różnice: A jak "p-op" wymienisz na "p", to wypisze po prostu liczby pierwsze.

Dzięki, że rzuciłes kodem. Będe miał co analizować. Te przesunięcia bitowe wyglądają troche skomplikowanie.

_jta_ wrote:

Na procesorze Xeon E5-1650 v3 @ 3.50GHz liczenie trwa 55 sekund (bez -O; z -O9 38 sekund).

Szybko i dobrze.

_jta_ wrote:

Wyliczenie ciągu Fibonacciego do Fib(64)=10610209857723 wykonuje w czasie kilku ms

Teraz dopiero zrozumiałem, że te funkcje rekurencyjne są okropne. Ograniczyłem już raz ich użycie, ale wogóle się ich pozbedę, bo to strata czasu.
Rekurencją do Fib(93) to bym chyba nie doczekał się. Kiedy ją usunąłem, to do Fib(93) : 12200160415121876738 obliczył w ciągu niecałej sekundy. Powyżej tej wartości to już licznik się przekręcił.
Także dopiero mi uświadomiłeś, jaki to był słaby punkt programu. Wielkie dzięki. Klikam pomógł oczywiście. Nawet jakbym mógł to ze 100 razy.

_jta_ wrote:

Ale mi chodzi o 8 bitów na liczbę pierwszą (a takich mam około 200 milionów), nie na każdą (jest ich około 4 miliardów), ani każdą nieparzystą (około 2 miliardów).

Dobrze. Próbowałem to uruchamiać u siebie. Faktycznie zużycie pamięci jest mniejsze i dla 32 bitowych zmiennych wynosi 3.2 GB.
Jest nawet trochę szybsze niż rozwiązanie BITWISE, którego kod zamieściłem wcześniej.
Liczy bezbłędnie na 32 bitowych zmiennych, ale nie moge go przystosowac do 64 bitowych zmiennych. Także maksymalny zasięg dla tego rozwiązania bez zmian to w mojej procedurze Fib(47) = 2971215073.
Po zmianie typu zmiennych algorytm zaczął mi gubić liczby.

Nie rozumiem tej pętli:



Zakres petli zapisany hexadecymalnie 0x10000 to 65536 ale powinno być chyba coś więcej dla 64 bitowej przestrzen?

Przesuwa bity w tablicy gdzie index jest 32 bitową zmienną, ale robi to o 2^6 czyli 64.
Nie wiem o ile miejsc musiałbym przesuwać gdyby zmienne i1 i2 oraz p były typu uint64_t.
Próbowałem ale gubi liczby.
Zmiana jedynie typu zmiennej dla tablicy podwaja zużycie pamięci, ale wyniki wtedy są też dobre.

_jta_ wrote:

Niemniej jednak, mając komputer posiadający 8GB RAM-u, mogę tych około 200 milionów liczb pierwszych trzymać w około 800 MiB RAM, w kolejnych 800 MiB reszty z dzielenia, i w 2 GiB flagi pierwsza/złożona (bajt na flagę) dla liczb nieparzystych z zakresu około 4 miliardów. Jest to spore marnotrawstwo - użycie 3.6 GiB na dane, które można by zmieścić w 1.3 GiB - ale chyba można sobie na to pozwolić, a zyska się nieco większą szybkość.

Odnoszę wrażenie, że ten twój algorytm jest szybszy i zabiera mniej zasobów.

_jta_ wrote:

Wygląda na to, że i Fib(4096) mu niestraszny (856 cyfr), ale już zajmuje prawie 2s.

Nigdy nie pisałem w Tcl.

Quote:

"rajszym"]
Jeśli masz duuuużo czasu, to sprawdź kod poniżej (częściowo wg. koncepcji przechowywania liczb pierwszych przedstawionej przez @_jta_).

Dzięki. Faktycznie trzeba sporo czasu, aby doszedł do wartości, które mnie interesują.
Trochę inne podejście. Dobre do weryfikacji rezultatów.

rajszym wrote:

sylvi91 wrote:

Może się mylę, ale aby kalkulacje na wyższych zbiorach szły sprawnie to już komputery kwantowe powinny robić Albo chociaż 128 bitowe.

To wypluł komputer kwantowy:

Code: text

Log in, to see the code

I to na tej aplikacji w C++? Zauważyłem tylko, że ona zużywa bardzo mało pamięci. Ale dokładnie nie analizowałem jej. Powiedz jeszcze ile zajeły te obliczenia? Wyniki wyglądają jak najbardziej na poprawne. Dzięki.

Ja tak daleko nie zaszedłem, próbowałem usprawnić i przystosowac metodę proponowaną przez @_jta_ do zmiennych 64 bitowych. Wydaje mi się, że oryginalnie niepotrzebnie przewymiarowało zakres dla wewnętrznej pętli. Dla zewnętrznej z kolei był raczej za mały dla moich potrzeb.
Zmieniłem pętlę do takiej postaci.



Przy takich typach zmiennych i zdefiniowanych stałych:




Wyniki obliczeń wskazują na zmniejszenie zużycia pamięci o kilka procent i przyśpieszenie obliczeń.
Pamięć 8GB.

Dla Fib(47) z 3.2% do 2.2% i czasie 34 s poprzednio do 27 sekund. (A było nawet 134 sekundy przy innej metodzie dla Sita)
Dla Fib(48) do 3.6% - wcześniej brak danych dla tej metody, czas obliczeń 45 sek.
Dla Fib(49) do 5.8% - wcześniej brak danych, czas obliczeń 74 sek.
Dla Fib(50) do 9.4% - wcześniej brak danych, czas obliczeń 122 sek.

Jest tylko w tej procedurze minus taki, że oblicza dla zakresu max Fib(50)=12586269025, a dla kolejnych wyrzuca błąd Segmentation Fault. Na razie nie wiem co jest przyczyną.

rajszym wrote:

sylvi91 wrote:

I to na tej aplikacji w C++?

Oczywiście nie. Na szybko zaimplementowałem algorytm zaproponowany przez @_jta_, nie wiem czy ma jakąś nazwę, więc proponuję rolling sieve (sito kroczące?) . Obliczenia zajęły ok. 90 minut.

Kolego, jak ty to zrobiłeś? Szybko i skutecznie. Doszedłeś do rzędu wyższych obliczen niż ja, a siedzę nad tym już kilka dni conajmniej. Możesz pochwalić się kodem? Jaki to język chociaż tej aplikacji. Ja próbowałem nawet bitsetu C++ ale nie mogłem nic wiecej wykrzesać.
Rzuciłeś okien na pętlę, którą próbuję jeszcze zmieniać? Nie moge na tym rozwiązaniu pojśc poza Fib(50) ale jest szybkie i mało pamięci zużywa. Mimo, że zmienne są 64 bitowe a były tylko 32 bitowe to nie mogę większego postępu zrobić niż o 3 kroki z Fib(47) do Fib(50).
Wydaje mi się, że zmienna p powinna mieć inaczej przesuwane bity, albo zmienna i1 pracować na innym zakresie.
EDIT:
Chyba znalazłem błąd, który był przyczyną. Pętla została bez zmian. Zmieniłem sposób alokowania pamięci. To pozwoliło mi uzyskać Fib(52) z 24.6% zużycia pamięci w czasie 351 sekund. Prawie 6 minut.


Aktualnie liczę do Fib(54) = 86267571272, przy zużyciu pamięci 64.5 %, jeśli rezultaty się potwierdzą z twoimi to dam znać i zrobię kolejny krok dla dalszego o jeden zakresu. Ale to już wtedy naprawdę będzie koniec przy takiej ilości pamięci.
Zdecydowanie lepiej mieć 8 bitów na liczbę pierwszą niż 1 bit na każdą liczbę naturalną w tablicy. Bo tak myślę, że właśnie działa ta zoptymalizowana procedura.

Dodano po 4 [godziny] 9 [minuty]:

rajszym wrote:

sylvi91 wrote:

I to na tej aplikacji w C++?

Oczywiście nie. Na szybko zaimplementowałem algorytm zaproponowany przez @_jta_, nie wiem czy ma jakąś nazwę, więc proponuję rolling sieve (sito kroczące?) . Obliczenia zajęły ok. 90 minut.

Kolego, jak ty to zrobiłeś? Szybko i skutecznie. Doszedłeś do rzędu wyższych obliczen niż ja, a siedzę nad tym już kilka dni conajmniej. Możesz pochwalić się kodem? Jaki to język chociaż tej aplikacji. Ja próbowałem nawet bitsetu C++ ale nie mogłem nic wiecej wykrzesać.
Rzuciłeś okien na pętlę, którą próbuję jeszcze zmieniać? Nie moge na tym rozwiązaniu pojśc poza Fib(50) ale jest szybkie i mało pamięci zużywa. Mimo, że zmienne są 64 bitowe a były tylko 32 bitowe to nie mogę większego postępu zrobić niż o 3 kroki z Fib(47) do Fib(50).
Wydaje mi się, że zmienna p powinna mieć inaczej przesuwane bity, albo zmienna i1 pracować na innym zakresie.
EDIT:
Chyba znalazłem błąd, który był przyczyną. Pętla została bez zmian. Zmieniłem sposób alokowania pamięci. To pozwoliło mi uzyskać Fib(52) z 24.6% zużycia pamięci w czasie 351 sekund. Prawie 6 minut.


Aktualnie liczę do Fib(54) = 86267571272, przy zużyciu pamięci 64.5 %, jeśli rezultaty się potwierdzą z twoimi to dam znać i zrobię kolejny krok dla dalszego o jeden zakresu. Ale to już wtedy naprawdę będzie koniec przy takiej ilości pamięci.
Zdecydowanie lepiej mieć 8 bitów na liczbę pierwszą niż 1 bit na każdą liczbę naturalną w tablicy. Bo tak myślę, że właśnie działa ta zoptymalizowana procedura.


EDIT2:
Ostatnie wyniki obliczeń:



Jednak dla Fib(55) program nawet nie podaje żadnego komunikatu o błędzie. Ale pewnie chodzi o alokacje pamięci przez instrukcję malloc gdzie przy 1 bajcie, czyli ośmiu bitach na element tablicy trzeba aż 139583862445 bajtów pamięci, czyli 139.5 GB. Podzieliłem to na 16 ale też jeszcze za duża to przestrzeń.




Gdyby ktoś znał lepszą metodę na alokację pamięci dla zbiorów liczb to może jeszcze coś tu się da usprawnić.
Z braku pamięci RAM nie mogę robić dalszych eksperymentów tą metodą.

Wątek praktycznie do zamknięcia, ale jeszcze może ktoś chce coś dodać, to wstrzymam się dzień lub dwa. Dzięki wszystkim za pomoc, a szczególnie _jta_. Pozdrawiam.

rajszym wrote:

Jeśli zajętość pamięci wzrasta w kolejnych krokach iteracji, to jest błąd. Przy zastosowaniu tego algorytmu zajętość pamięci powinna być stała. Zapamiętujesz przecież tylko liczby pierwsze w przedziale <3; 2^32).

Niekoniecznie jest to błąd. Zrobiłem to inaczej niż Wy sugerowaliście pewnie. Zmieniłem bowiem typ zmiennych na 64 bitowe i takich używam w pętli for.
Ale zmiana jednego warunku granicznego dała mi właśnie możliwość alokacji pamięci zgodnie z drugim parametrem podawanym na wejściu przy uruchamianiu programu. Ponieważ cciałem zachować ta możliwość aby nie alkować za dużego bloku dla małych wartosci Fib(n) co zabierało niepotrzebnie sporo czasu.

Oryginalnie to co zaproponował _jta_ wyglądało tak:


... ja zmieniłem jeden warunek w pętli wewnętrznej na:


Gdzie limit to maksymalny zakres wyznaczony przez funkcję fib(n)...
i trochę inaczej zaczałem przesuwać bity:


To dało większą oszczędność pamięci niż dawał oryginalnie ten algorytm dla mojego programu. Około 1/3 oszczędności, przy 32 bitowych wartościach.

rajszym wrote:

W mojej uproszczonej implementacji jest to ok. 1,8GiB (256MiB - sito, ok. 780MiB - liczby pierwsze, ok. 780MiB - kolejna pozycja iteracji w następnym segmencie sita).

Ale jak ty to kolego uprościłeś to nie mogę sobie wyobrazić.
Rzuć kodem jeśli możesz.

Moja implementacja w całości wygląda tak i korzysta z GMP dla dużych liczb:
Niekóre zmienne niepotrzebne, nazwy zostawiłem aby było można łatwiej porównać przykład z oryginałem.