_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.