Liczby pierwsze nie są rozłożone losowo?

[taśma9 1]

Witam, dyskusja zamarła, ale obserwowałem ją i była moim napędem do pisania programu.

Nie wiem czy wyjdzie szybciej, ale mi się skończyły pomysły na przyspieszanie.

Wrzuciłem projekt (w javie) na githuba: https://github.com/marioc8/primeSentinel30.

Udało mi się osiągnąć 10^9 w niecałe 2 sekundy. Jednowątkowo.Wielowątkowo nie umiem, javy uczę się trochę ponad rok.

Nie starałem się wymyślić wzoru, ale i tak trochę czasu mi zajął nawet w takiej formie.

Jest jeszcze wiele bugów do ogarnięcia, ale ogólnie z eclipse program chodzi bez problemu, i można robić benchmarki.

[thikim 119]

10^9 to czym jest?

Każdy wątek kiedyś umiera.

[taśma9 1]

Skróty myślowe, zakres od 1 do 10^9 przegląda w niecałe 2 sekundy na procku i5, poprawiam.

[thikim 119]

I ile liczb pierwszych znajdujesz w tym zakresie?

[taśma9 1]

Dokładnie to jest to zakres od 7 do 1_000_000_020, znajduje w nim 50,847,534 pierwszych.

Wielokrotności 2,3 i 5 są całkowicie pominięte w całym procesie.

Edycje mam wyłączoną, chyba jeszcze nie zapracowałem na nią. W powyższym zakresie znajduje 50,847,536 liczb pierwszych.

[thikim 119]

Swoją drogą zrób trochę większy zakres. np. do 100 mld.

Przy 2 sek. to ciężko ocenić szybkość.

[taśma9 1]

zakres do 100 mld. jest dla mnie na razie nie osiągalnym musiałbym pomyśleć o robieniu tablicy int, long albo użyć dysku.

Java pozwala mi na maksymalnie 64_410_000_030 tablicę bajtową, potem jest problem z adresowaniem.

Wyniki dla i5 7600k 3.8 GHz:

64_410_000_030    128.697 s2,701,477,379 liczb pierwszych

poprzedni się nie liczy , jeszcze raz:

 

64_410_000_030      128.697 s    2,701,477,379   pierwszych - maksymalna osiągalna wartość tablicy byte w technologii modulo 30 na bitach

50_000_000_010        97.805 s    2,119,654,578   pierwszych

10_000_000_020        17.035 s       455,052,512   pierwszych

[Eratorka 0]

po przeczytaniu całego topi'cu duzo się nauczyłam, nawet bardzo duzo.

[Matcher 2]

Taśma9 zrób test na swoim procku moim "starym" programem

 

Powinno być sporo wolniej Ale da mi to odniesienie do Twoich paru sekund

 

PS:

wątek może i umarł, ale tylko dlatego, że nie było zbytnio co testować. Mój stary notes ciągle czeka na nowe pomysły i możliwości, a skończyło się na RAMKACH i sposobie ich przedstawienia oraz kilku "dziwnych" pomysłach, które zakończyły się ślepą uliczką...

Oblicza liczby pierwsze max optymalizacja.zip

[taśma9 1]

takie mam wyniki bez OC:

 

  78,499   pierwsza to   1000003,   czas:      14s      mój: 0.003s

148,934   pierwsza to   2000003,   czas:      39s      mój: 0.008s

216,818   pierwsza to   3000029,   czas: 1m17s      mój: 0.008s

 

ale jest duże ALE, ponieważ nie mam Windowsów, test robiłem na wine-2.0.2 pod Ubuntu 17.10, tylko taki mam system.

Od czasów możesz odjąć jakieś 5 sekund, przez które wpisywałem numer liczby pierwszej, a po zakończeniu działania programu wciskałem Enter.

Przy dużych liczbach ( 100 milionów ) Wine nie dawało rady, wywalało się.

Już od jakiegoś czasu w planach miałem maszynę wirtualną z darmowym XP, więc chyba po prostu przyspieszę wykonanie zadania, i przeprowadzę ponowne testy

[Matcher 2]

Pewnie dlatego taka rozbieżność, bo u Ciebie operacje są wykonywane na liczbach bitowych, a u mnie na dziesiętnych

 

100 mld nawet nie wpisuj, bo program był dawno temu kompilowany i tam ograniczeniem była granica liczby pierwszej 1mln Ja uzyskałem wtedy liczbę 500.000 -> 7368787 według tej strony http://liczby_pierwsze.republika.pl/ się zgadza.

Edytowane 15 listopada 2017 przez Matcher

[Jajcenty 314]

le jest duże ALE, ponieważ nie mam Windowsów, test robiłem na wine-2.0.2 pod Ubuntu 17.10, tylko taki mam system.

A czego chcesz się uczyć? Dlaczego wine? Nie masz Javy w Ubuntu? Eclipse?

Ubuntu daje wszystko co potrzeba

gcc version 5.4.0 20160609 (Ubuntu 5.4.0-6ubuntu1~16.04.5) 

 

jajcenty@Detrytus:~/sndbx/cnslapp$ dotnet --version

2.0.0

 

Python też jest. Po co wine? Masz  ulubione IDE?

 

p.s. Pobudzony ruchem tutaj bawię się sitem Atkina. Wydaje się wdzięcznym polem dla wyciskania efektywności z algorytmu.

Edytowane 15 listopada 2017 przez Jajcenty

[taśma9 1]

Jajcenty, maszyna wirtualna mi się przyda żeby sprawdzić jak instalować i uruchamiać programy pisane w Javie, żebym wiedział jak u znajomych którzy mają tylko Windowsy sprawdzić swój program, ale jakiś skrypt. Czysta potrzeba wiedzy

Z "C" dałem sobie spokój, dla mnie za trudne.

To co robiłem w "C" w kilka miesięcy w Pythonie zrobiłem w tydzień.

 

dotnet ? hmm, tego nie znam

 

Mam Javę a Eclipse to mój ulubiony IDE

I wygląda że tak już zostanie.

A dlatego Wine, ponieważ chciałem jakoś zrobić test, a innej możliwości pod Ubuntu nie znam, chyba że Dosbox

p.s.

Mój programik powstawał dosyć długo, koniec końców to jakaś odmiana sita Atkina, ale najpierw było to sito Eratostenesa operujące na kolumnach liczb z końcówką 1,3,7,9, zresztą jeszcze mam kod na pamiątkę Ale to właśnie na Eratostenesie zauważyłem że można odznaczać w każdej kolumnie liczbę że nie jest pierwszą bo jest pochodną, a następna pochodna np liczby 3, to 33, czyli indeks 0 + 3 = 3, czyli 3 * 10 + 3, wystarczyło obliczyć punkt początkowy, i dalej to już zwykła pętla dla każdej z czterech kolumn. Nie było łatwo

p.p.s.

Matcher, to znaczy że robisz wszystko w ascii ?

[Matcher 2]

W programie zadeklarowany był typ zmiennej int long long z tego co pamiętam.

 

Twoja tabelka więc wygląda tak?

 

11 | 13 | 17 | 19

21 | 23 | 27 | 29

 

Jak tutaj można wyznaczyć stałe reguły do wyznaczania LP?

 

Ja robiłem na takiej tabelce:

 

11 | 13 | 17 | 19 | 23 | 29 | 31 | 37 |

41 | 43 | 47 | 49 | 53 | 59 | 61 | 67 |

 

Na dodatek nie trzeba rysować całej tabelki, bo można przenieść się w Każde jedno jej miejsce.

[taśma9 1]

W mojej tabelce jest stała reguła do wykreślania liczb które nie są liczbami pierwszymi, np znajdujesz indeks [0,1] który ma wartość "0" (czyli 3) to znaczy że to liczba pierwsza, teraz tak,

indeks [3,1] zaznaczasz jako "1" ( czyli 33 ), indeks [6,1] zaznaczasz jako "1" ( czyli 63 ):

 

  1 |   3 |   7 |   9

11 | 13 | 17 | 19

21 | 23 | 27 | 29

31 | 33 | 37 | 39

41 | 43 | 47 | 49

51 | 53 | 57 | 59

61 | 63 | 67 | 69

 

czyli znalazłeś na indeksie 0 liczbę 3, i teraz w pionie w tym słupku dodajesz do indeksu tą liczbę ( 3 ) i skreślasz, i tak do końca zadeklarowanej tabelki, 3, 33, 63, 93, 123, 153, indeks cały czas zwiększasz o 3. Dla innych kolumn zmienia się tylko punkt startowy, dla zerowej kolumny to indeks "2", dla trzeciej kolumny to indeks "27", czyli pierwsza liczba która dzieli się przez "3" w danej kolumnie.

Dla 7 indeks będziesz się zwiększał o 7, dla 11 o 11.

p.s. tylko koniec końców wyszło że liczb pierwszych o 1 do 30 jest Osiem, więc pierwsze skojarzenie to bajt i 8 bitów, wierzę pan od primesievie wpadł na coś bardzo podobnego.

p.p.s a nawet nie osiem liczb pierwszych, tylko przy modulo 30 jest osiem słupków w których mogą być liczby pierwsze.

p.p.p.s ERRATA: dla drugiej kolumny to indeks "2" czyli liczba "27", a dla trzeciej kolumny to indeks "0". sorki, taki mały świerszczyk

4p.s.

Nie odpowiedziałem na pytanie, liczba pierwsza w sicie będzie miała wartość "0" bo nie została skreślona przez żadną poprzednią liczbę.

[Matcher 2]

Tak właśnie jest Osiem słupków i tylko tam znajdują się LP. Ogólnie to można zauważyć, że w tych słupkach są takie 10-tki liczb. np: zakres 10-20 - tutaj mogą być max 4 liczby P. Zakres 30-40 tutaj już tylko max 2 LP. Rozciągnij sobie taką tabelkę do nieskończoności.

 

PS:

Czy dla zadanego zakresu liczb Twój program dzieli tą tabelkę na wiele mniejszych części czy działa na całej tablicy?

 

PS:

Dodałem program ,który przy obliczeniach nie korzysta z żadnej tablicy (Sita). Ogranicza go tylko typ zmiennej Long Long int.

LiczbyPZapis2.zip

Edytowane 15 listopada 2017 przez Matcher

[taśma9 1]

Moja tabelka tak wyglądała, gdy robiłem na sicie Eratostenesa, to było na początek tak dla uproszczenia, łatwiej było znaleźć reguły, które potem ładnie przeniosły się na sito modulo 30.

 

Mój program działa na całej tablicy.

Matcher, ten program który teraz dodałeś w jaki sposób oblicza liczby pierwsze ? Zakładam że nie dodaje liczb 2,3,5 i 7 do wyniku.

[Matcher 2]

Program działa na tej tablicy o ośmiu kolumnach, ale nie posiada jej w pamięci. Jak by to najprościej wyjaśnić:

 

Po kolei program przechodzi przez każdy element tej tablicy [liczbę] i klasycznie dzieli go przez każdy element należący do tej tablicy, dzięki czemu nie potrzeba deklarować w pamięci drugiej tablicy na znalezione liczby pierwsze. Rozciągnij moją tabelkę do wielkiego zakresu i największą liczbę w tej tabelce dziel klasycznie przez elementy tej tabelki zaczynając od jej początku [11]. Jak się nie podzieli to liczba jest pierwsza.

 

Nie ma tutaj żadnego dodawania 2,3,5,7. Tu jest tylko wzór na każdy element [liczbę] tej tabelki.

Edytowane 15 listopada 2017 przez Matcher

[taśma9 1]

Mam wrażenie że będę musiał przestudiować jeszcze raz cały topik i przemyśleć temat

 

Tablica jest dobra dla mniejszych zakresów, ale im dalej w las, tym ciemniej - mniej LP.

Na tym moim programie można by było sprawdzić czy liczba jest pierwsza w zakresie od 1 do liczby z 4 z przodu i następnie 21 zerami,

co już trochę wykracza poza 64bity, co mam zresztą w planach Jeszcze muszę dopisać część zliczającą LP do Long.MAX_VALUE, i tutaj z czasami już może nie być tak wesoło.

 

Wzór na liczby pierwsze to musiało by być coś co adaptuje się do zmieniających się warunków, po co sprawdzać 80 tysięcy liczb w których nie ma LP ?

albo zajmować tym pamięć.

 

Na dzisiaj mi starczy

[Matcher 2]

By wypisać liczby pierwsze trzeba omijać liczby złożone. Zobacz sobie mój arkusz kalkulacyjny excel, który pokazuje tzw. Ramki. Każda z nich posiada po osiem liczb złożonych wyróżnionych kolorem. Każda z tych liczb przypada na jedną z ośmiu kolumn. Jeśli dla liczby 11 stworzymy kilka takich ramek to położenie liczb złożonych mających dzielniki z 11 będzie takie samo dla każdej ramki, więc odstępy między nimi są takie same, co pozwala odpowiednio "w locie" działania programu omijać liczby z dzielnikami 11,13,17........ itd.

 

Problem jest w tym,że potrzebna jest tablica z danymi zawierająca przesunięcia dla każdego dzielnika, co będzie zapełniać RAM w nieskończoność. Aktualnie myślę czy można ominąć ten problem jakoś inaczej

[taśma9 1]

Patrzę na tą tabelkę i chyba wiem o czym mówisz.

Najprostsze rozwiązanie które widzę to robić sito za każdym razem jak znalazłeś nową LP:

 

np znalazłeś 2, robisz sito modulo 2, czyli binarne,

znalazłeś 3, robisz sito modulo 6,

znalazłeś 5, robisz sito modulo 30,

znalazłeś 7, robisz modulo 210 ... itd do nieskończoności, tylko że szybko zabraknie pamięci w komputerze,

bo okaże się że przy 10 LP musisz zrobić sito modulo 6,469,693,230 które jeśli będziesz przechowywać w bitach zajmie ponad 770MB co jeszcze jest do ogarnięcia,

ale przy 11 LP czyli "31" modulo dojdzie do wartości 200,560,490,130 a to już trzymane nawet w formie bitów zajmie przeszło 23GB.

Duży przeskok, ale następny to ponad 860GB, a następny to już ponad 34,5 TB, pod warunkiem że każda liczba to 1 bit.

 

Minusy są takie że:

albo musisz trzymać wtedy bit do każdej liczby, bo jeżeli stworzysz sito dynamicznie to będzie to najprostszy sposób na wyliczenie jaka to liczba,

albo musisz zapamiętywać LP, możesz to robić na zasadzie że poprzednie sito modulo tworzy nowe sito modulo, albo zapamiętywać LP w formie int lub long

 

 

RAM zawsze będzie się zapełniał w nieskończoność, jeśli będziesz liczył nieskończony zakres

 

 

Patrzę na arkusz i tak myślę, gdybyś wiedział jak ominąć ten problem, to byłby to wzór na liczby pierwsze

[Krzychoo 31]

Pewnie to znacie ale tak na wszelki wypadek podrzucę: http://ulamspiral.com/

[Matcher 2]

Tylko czy ktoś może tą Spiralę analizował głębiej? Na matrycy 2D ułożenie LP wydaje się chaotyczne, choć widać podobne kształty figur..

 

Ciekawy jestem, czy można by było zastosować tu sieć neuronową do nauki takiej planszy 2D, a potem wykorzystać do przewidywania dalszych LP.

 

Jeszcze jedna myśl: LP nie mają dzielników. W tabelce wypełniają tylko puste luki. A gdyby brakło jakiejś liczby, to nie powstałyby kolejne liczby w tabelce. Czyli LP to takie cegiełki, które muszą istnieć. Brak jakiejkolwiek z nich spowodowałoby zanik dalszych liczb złożonych. Powstałyby "dziury", których byłoby coraz więcej i więcej. hmn. ciekawe

[Jajcenty 314]

 

 

Tylko czy ktoś może tą Spiralę analizował głębiej?

Możesz się założyć, że tak. 

 

Jeśli zajrzysz do polskiej wiki https://pl.wikipedia.org/wiki/Liczba_pierwsza do sekcji "rozmieszczenie" zobaczysz obrazek na który widać dlaczego może się wydawać że istnieje prosta liniowa zależność między numerem liczby pierwszej a liczbą pierwszą. Po pierwsze liczby pierwsze są w postaci:

lp = 2n+1 co definiuje super prostą.

Z tej prostej wywalamy wszystkie liczby np w postaci notprime = 60n znowu prosta i znowu cykl - teraz wrażenie cykliczności już nas nie opuści.

[Matcher 2]

Czyli jak to jest z tą cyklicznością?

 

Na obrazku widać miejsca całkowite puste i również te w większości zapełnione. Nie wiem tylko czemu w tej spirali liczba LP wydaje się stała, choć wiadomo,że im dalej jedziemy tym mniej po drodze znajdziemy.. Co można jeszcze wywnioskować z tego obrazka?