Elektroda.pl
Elektroda.pl
X

Search our partners

Find the latest content on electronic components. Datasheets.com
Elektroda.pl
Please add exception to AdBlock for elektroda.pl.
If you watch the ads, you support portal and users.

Liczby pierwsze w C - sito Erastotenesa

09 Jul 2019 01:03 1785 79
  • #31
    _jta_
    Electronics specialist
    Pytanie: czy liczby pierwsze są wykorzystywane tylko sekwencyjnie, 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)...

    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.
  • #32
    User removed account
    Level 1  
  • #33
    _jta_
    Electronics specialist
    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; }.
  • #34
    User removed account
    Level 1  
  • #35
    _jta_
    Electronics specialist
    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). 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.

    Czy zakres uint64_t jest za mały na liczby pierwsze, z którymi masz do czynienia?
  • #36
    Dżyszla
    Level 42  
    Odnośnie dywagacji na temat liczb pierwszych jako takich, to temat po pierwsze wykracza daleko poza programowanie, a po drugie raczej wymaga wiedzy na poziomie wyższym; w poruszanych zagadnieniach przede wszystkim znajomość statystyki, która jest jedną z trudniejszych dziedzin matematyki. Myślę, że nie ma sensu ciągnąć już dłużej tego tematu.
  • #37
    _jta_
    Electronics specialist
    Myślę, że (1) autor tematu ma jakąś orientację co do "gęstości" liczb pierwszych; (2) informacja o tym może pomóc lepiej dobrać technikę obliczeń. A czy wystarczy mu to, co do tej pory znalazł, czy chce poszukać takiej technik, która mu pomoże policzyć coś więcej, to jest jego wybór.
  • #38
    User removed account
    Level 1  
  • #39
    _jta_
    Electronics specialist
    Tablica na liczby pierwsze do Fib(53) = 53316291173 zajęła (...) 6664536396.625 bajtów.

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

    Obecnie obliczyłem ile jest liczb między Fib(52) i Fib(53). Jest ich tam 831993816.

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

    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). Może dobrze byłoby mieć je w "poręcznej" postaci do przesiewania liczb ponad 2^32? Tych większych nie trzeba trzymać w pamięci - można by przesiewać zakresy np. po 4G.
  • #40
    User removed account
    Level 1  
  • #41
    _jta_
    Electronics specialist
    nie wiem jak wyliczyłeś 12 bitów na liczbę pierwszą

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

    Z mojego programu wyszło, że w zakresie do 2^32 jest 203280221 liczb pierwszych - zaczynają się od 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 263 269 271 277 281 283 293 307 311 313 317 331 337 347 349 353 359 367 373 379 383 389 397 401 409 419 421 431 433 439 443 449 457 461 463 467 479 487 491 499 503 509 521 523 541 547 557 563 569 571 577 587 593 599 601 607 613 617 619 631 641 643 647 653 659 661 673 677 683 691 701 709 719 727 733 739 743 751 757 761 769 773 787 797 809 811 821 823 827 829 839 853 857 859 863 877 881 883 887 907 911 919 929 937 941 947 953 967 971 977 983 991 997 1009 1013 1019 1021 1031 1033 1039 1049 1051 1061 1063 1069 1087 1091 1093 1097 1103 1109 1117 1123 1129 1151 1153 1163 1171 1181 1187 1193 1201 1213 1217 1223 1229 1231 1237 1249 1259 1277 1279 1283 1289 1291 1297 1301 1303 1307 1319 1321 1327 1361 1367 1373 1381 1399 1409 1423 1427 1429 1433 1439 1447 1451 1453 1459 1471 1481 1483 1487 1489 1493 1499 1511 1523 1531 1543 1549 1553 1559 1567 1571 1579 1583 1597 1601 1607 1609 1613 1619 1621 1627 1637 1657 1663 1667 1669 1693 1697 1699 1709 1721 1723 1733 1741 1747 1753 1759 1777 1783 1787 1789 1801 1811 1823 1831 1847 1861 1867 1871 1873 1877 1879 1889 1901 1907 1913 1931 1933 1949 1951 1973 1979 1987 1993 1997 1999, a kończą na 4294966447 4294966477 4294966553 4294966583 4294966591 4294966619 4294966639 4294966651 4294966657 4294966661 4294966667 4294966769 4294966813 4294966829 4294966877 4294966909 4294966927 4294966943 4294966981 4294966997 4294967029 4294967087 4294967111 4294967143 4294967161 4294967189 4294967197 4294967231 4294967279 4294967291.

    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.

    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.

    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.
  • #42
    User removed account
    Level 1  
  • Helpful post
    #43
    _jta_
    Electronics specialist
    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.

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

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

    Wyliczenie ciągu Fibonacciego do Fib(64)=10610209857723 wykonuje w czasie kilku ms skrypt:
    Code: tcl
    Log in, to see the code
  • #44
    User removed account
    Level 1  
  • #45
    _jta_
    Electronics specialist
    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).

    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ść.

    W Tcl-u na starszym komputerze obliczenia Fib po zwiększeniu zakresu skończyły się na Fib(92), ale na nowszym program doliczył do Fib(128)=251728825683549488150424261, a jak kazałem liczyć do 256, to policzył i Fib(256)=141693817714056513234709965875411919657707794958199867, i nawet Fib(1024)=4506699633677819813104383235728886049367860596218604830803023149600030645708721396248792609141030396244873266580 345011219530209367425581019871067646094200262285202346655868899711089246778413354004103631553925405243 (w ciągu 40ms). Wygląda na to, że i Fib(4096) mu niestraszny (856 cyfr), ale już zajmuje prawie 2s.
  • #46
    rajszym
    Level 20  
    sylvi91 wrote:
    Dlatego szukam innych algorytów.

    Jeśli masz duuuużo czasu, to sprawdź kod poniżej (częściowo wg. koncepcji przechowywania liczb pierwszych przedstawionej przez @_jta_).
    Code: c
    Log in, to see the code
  • #48
    rajszym
    Level 20  
    Szybkość spada w tempie geometrycznym :)
  • #50
    rajszym
    Level 20  
    Weź pod uwagę, że w kodzie powyżej jest prymitywny algorytm sprawdzania liczb pierwszych przez dzielenie modulo przez poprzednio znalezione.
    _jta_ wrote:
    Szybkość sita też spada - ale ja pytam, jak te szybkości się porównują.

    do przedziału fib(46) - fib(47): 30 sekund / 3 godziny (tak z grubsza)

    Dodano po 1 [godziny] 33 [minuty]:

    Nieco szybsze od sita Eratostenesa jest sito liniowe.
    Przy obliczeniach do przedziału fib(50) - fib(51): 4 minuty (sito Eratostenesa) / 3 minuty (sito liniowe)
  • #51
    User removed account
    Level 1  
  • #52
    _jta_
    Electronics specialist
    Ten program jest tylko dla liczb do 2^32 (i z użyciem zmiennych uint32_t). Jeśli jakaś liczba w tym zakresie jest złożona, to musi mieć podzielnik < 2^16. A wygenerowane w ten sposób liczby pierwsze wystarczą do "przesiania" liczb do 2^64 - każda złożona w tym zakresie dzieli się przez którąś < 2^32.
  • Helpful post
    #53
    rajszym
    Level 20  
    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
  • #54
    _jta_
    Electronics specialist
    W asemblerze można dwie liczby 64-bitowe traktować jako 128-bitową - ale dane mamy co najwyżej 64-bitowe (do liczby pierwszej, która się nie zmieści w 64 bitach, nie dojdziesz - zajęłoby to tysiące lat) i tylko suma się nie zmieści - więc można dodawać do mniej znaczącego słowa, i jak będzie przepełnienie, to zwiększać o 1 bardziej znaczące.

    Tylko potem trzeba pewnie wypisać wynik - w tym celu należy sumę podzielić przez 10^19 (tyle jeszcze się mieści w 64 bitach, w C typ unsigned long long) i wypisać iloraz, a po nim resztę jako liczbę 19-cyfrową z zerami na początku (w C format %019Lu). Ciekawostka: 2*10000000000000000000=1553255926290448384.
  • #55
    User removed account
    Level 1  
  • #56
    rajszym
    Level 20  
    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.
  • #57
    User removed account
    Level 1  
  • #58
    rajszym
    Level 20  
    Code: text
    Log in, to see the code

    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). 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).
  • #59
    User removed account
    Level 1  
  • #60
    rajszym
    Level 20  
    sylvi91 wrote:
    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).

    Code: c
    Log in, to see the code
    Porównaj to co napisałem i o czym pisał również @_jta_ z tym co zrobiłeś.

    Dodano po 3 [minuty]:

    Biblioteka gmp jest zbędna.