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

[thikim 117]

A dlaczego mam jechać:

2,4,2,4,6,2,6,4?

co mi da:

13,17,19,23,29,31,37,41?

ja bym jechał:

2,4,2,2,2,4,2,2,2

co mi da:

13,17,19,21,23, 27,29,31.

[Matcher 2]

W ten sposób naliczasz niepotrzebnie więcej liczb.. Po co sprawdzać liczbę 21 i 27 skoro dzieli się na 3??  Liczby z sumą cyfr 3,6,9 nie powinny być sprawdzane.

W ten sposób naliczasz niepotrzebnie więcej liczb.. Po co sprawdzać liczbę 21 i 27 skoro dzieli się na 3??  Liczby z sumą cyfr 3,6,9 nie powinny być sprawdzane.

 

Na każde 30 liczb sprawdzasz tylko max 8, a nie 12 Ciąg 13,17,19,23,29,31,37,41 jest najbardziej zoptymalizowany.

[thikim 117]

Hmm. A ja wróżka żeby wiedzieć że dzieli się przez 3?

Tzn. wiesz dla 21 i 27 to wiem. Ale ogólnie dla 34453484803508963476853 to już bym się musiał zastanowić - program też się musi chwilę zastanowić żeby to wiedzieć. To zastanawianie jest czasochłonne.

No i kwestia jest taka: żeby sprawdzić podzielność przez 3 to muszę najpierw tę liczbę otrzymać. Jak mam mieć liczbę do sprawdzenia jak Ty dodajesz 6 i ją pomijasz, zanim jeszcze sprawdzisz?

2,4,2,4,6,2,6,4?

Edytowane 27 października 2016 przez thikim

[Gość Astro]

to już bym się musiał zastanowić - program też

 

Też bym chciał napisać program, który się zastanawia; niestety, nie potrafię (pomijam oczywiście "pseudo zastanawianie się" jako generowane jakimś psudolosowcem czasu zwłoki). Thikim, wielki szacun dla Twoich umiejętności.

 

A ja wróżka żeby wiedzieć że dzieli się przez 3? Tzn. wiesz dla 21 i 27 to wiem. Ale ogólnie dla 34453484803508963476853 to już bym się musiał zastanowić

 

Wiele się zastanawiać nie trzeba. Suma cyfr to 110, więc nie dzieli się przez 3.

Edytowane 27 października 2016 przez Astro

[Matcher 2]

Hmm. A ja wróżka żeby wiedzieć że dzieli się przez 3?

Tzn. wiesz dla 21 i 27 to wiem. Ale ogólnie dla 34453484803508963476853 to już bym się musiał zastanowić - program też się musi chwilę zastanowić żeby to wiedzieć. To zastanawianie jest czasochłonne.

No i kwestia jest taka: żeby sprawdzić podzielność przez 3 to muszę najpierw tę liczbę otrzymać. Jak mam mieć liczbę do sprawdzenia jak Ty dodajesz 6 i ją pomijasz, zanim jeszcze sprawdzisz?

2,4,2,4,6,2,6,4?

 

Bo dodając 6 omijasz liczby, których sprawdzać nie trzeba.. Popatrz na pierwsze 1000 liczb pierwszych i przelicz sumę cyfr każdej z nich. Nigdy nie wyjdzie ani 3 ani 6 ani 9..   Licząc 2,4,2,4, 6,2,6,4  omijasz właśnie takie liczby..  Dzięki temu sprawdzasz sporo mniej liczb nieparzystych niż byłeś nauczony do tej pory

[thikim 117]

2,4,2,4, 6,2,6,4

A gdzie tu okres? Wiesz dla pierwszych 20-stu to ja mogę sobie ułożyć co mam dodawać. Fakt algorytm się mocno pokićka ale dałoby radę.

A co z pierwszym milionem? Kiedy dodać 2 i 4 to się da ułożyć prosto w powtarzalną strukturę: dodajemy trzy razy dwójkę, raz czwórkę i powtarzamy.

A gdzie jest struktura w tym co piszesz?

"2,4,2,4, 6,2,6,4"

Albo jest prosta struktura i łatwo to implementuje. Albo struktury nie ma i nie wiem co dodać dla liczby 32459039859043285098, bo skąd to mam wiedzieć?

Pomysł z tym nx30+y jest dobry jeśli działa dla większych liczb pierwszych. Na razie nie wiem. Sprawdzę jak znajdę czas.

Póki co nadrabiam: gameplayowanie, yutubowanie i blogowanie

 

 

Licząc 2,4,2,4, 6,2,6,4 omijasz właśnie takie liczby

Ja to wiem,  a Ty wiesz co dalej i dalej i dalej? Co mam dodać za milion pierwszym razem? Tu nie chodzi o wygenerowanie pierwszych 20-stu liczb pierwszych, tylko o wygenerowanie pierwszych 20 miliardów np.

Edytowane 27 października 2016 przez thikim

[Jajcenty 314]

 

 

Ja to wiem,  a Ty wiesz co dalej i dalej i dalej? Co mam dodać za milion pierwszym razem? Tu nie chodzi o wygenerowanie pierwszych 20-stu liczb pierwszych, tylko o wygenerowanie pierwszych 20 miliardów np.

Otóż to.

 

Bo dodając 6 omijasz liczby, których sprawdzać nie trzeba

Fajnie by było, gdybyś mógł zrealizować ten pomysł w postaci działającego kodu. Moglibyśmy spróbować porównać sprawność np. z tym co zrobił Afordancja. Jeśli nie możesz, to opublikuj choć pseudokod - znajdzie się ktoś kto przerobi to na działającą wersję w wolnej chwili. Nadchodzący długi weekend to idealny moment.

[thikim 117]

Sprawniej już będzie jak się doda co czwarty raz 4 zamiast 2. To dobry pomysł. Powinno dać z 25 % przyspieszenia.

Ale o wiele lepszy jest ten sposób który opisał Matcher wcześniej (jeśli działa):

Jeśli n x 30 + y działa to jest to o wiele większe ulepszenie bo przyspieszenie będzie:

na 30 liczb sprawdzam 8 zamiast 15 normalnie, zamiast 12 w wersji z dodawaniem 4.

Czyli zysk niemal 50 %.

Ponieważ wykorzystać można tylko jeden z pomysłów to wolę ten z "30".

A hoy - odpalam Visuala

PS1. Wersja pierwotna programu daje wyniki:

10000000 (nr liczby pierwszej)  -  179390017 ( liczba pierwsza) Czas pracy:83,7580807 s

PS2. Niby szybciej, ale coś nie poszło, metoda z "4":

10000000  -  158115259 (inna liczba pierwsza, albo i nie pierwsza i to solidnie inna )  Czas pracy:64,5526448 s

No i wyszło szydło z worka.

Program który zrobiłem wcześniej miał błąd:

Teraz jest tak, 10 mln liczba pierwsza 179424691:

wersja normalna: 80 s

wersja z "4": 78 s.

spodziewałem się większego przyspieszenia. Wychodzi na to że koszt generowania "4" jest niemal tak wielki że zżera całą oszczędność.

Użycie 4 daje nam odrzucenie liczb podzielnych przez 5, a te i tak przecież odrzucamy dość szybko dzieląc modulo przez 5. Stąd jednak mała oszczędność czasu. Spodziewałem się większej

Teraz biorę się za metodę z "30".

Dla "30" wyniki:

10000000  -  179424719 (liczba trochę większa bo zaczynałem od "11")

Czas pracy:79,0722152 s

Ogólnie: pupa. Nakład obliczeniowy na generację niweluje korzyści z ograniczenia ilości liczb do sprawdzenia. Zwłaszcza że ich gro odpada szybko po podzieleniu przez "3" i "5"

Natomiast jako że otrzymałem liczbę pierwszą podobną do tej otrzymanej innymi metodami to wygląda na to że rzeczywiście każdą liczbę pierwszą można opisać:

yx30+x.

PSn:

Jeszcze porównajmy liczby pierwsze w ok. 10 000 000 miejsca wygenerowane klasycznie i "30".

10 000 000 - 179424691

10 000 001 - 179424697
10 000 002 - 179424719 i to jest ta liczba wygenerowana "30".

A że normalnie zaczynałem od 5 a dla "30" od 11 to wszystko się zgadza

Pierwsze 10 mln liczb pierwszych spełnia warunek y*30+x gdzie x={13,17,19,23,29,31,37,41}, y={0...N).

Niestety nie optymalizuje to szybkości ich poszukiwania (chociaż oczywiście ktoś inny może algorytm lepiej zapisać).

Edytowane 28 października 2016 przez thikim

[Jajcenty 314]

 

 

Pierwsze 10 mln liczb pierwszych spełnia warunek y*30+x gdzie x={13,17,19,23,29,31,37,41}, y={0...N).

Ja tam się na tym nie znam, ale w tym co pisze Mather widzę jakąś kompilację sita Atkina i reguł podzielności 

[thikim 117]

Możliwe. Tak samo "6" pojawiająca się przy przeskokach powinna wykazywać jakąś okresowość.
Ale implementacja tego będzie dosyć trudna. Tzn. możliwa za pomocą tablic ale prawdopodobnie szybciej jest po prostu sprawdzić podzielność przez 3, bo to pierwsze sprawdzenie w sicie programu (dwójkę eliminujemy generując liczby co 2).

Teraz druga sprawa. Metoda sprawdzania czy dzieli się przez 3 poprzez sumowanie cyfr. Można ale nie jest tak prosto rozłożyć liczbę na jedności, dziesiątki, setki, tysiące itd. Trzeba by wykonać wiele dzieleń modulo.
Można to zrobić prościej binarnie. Ale najprościej jednak napisać: liczba % 3 Jedna operacja modulo zamiast kilku
Naturalnie, prościej nie znaczy szybciej. Być może wersja binarna byłaby szybsza. Ale działałaby tylko dla dzielenia przez 3. A liczba % liczba pierwsza - zadziała w całym sicie bez tworzenia dodatkowych pętli, sprawdzeń itp.

Edytowane 28 października 2016 przez thikim

[Jajcenty 314]

 

 

Ale najprościej jednak napisać: liczba % 3 Jedna operacja modulo zamiast kilku

U mnie poniższy fragment wykonuje się 1,3 sekundy. Miejsca na zysk nie ma, o ile posługujemy się typem wspieranym przez sprzęt. Gdyby trzeba było podzielić liczbę stu cyfrową, to byłby dobry moment na rozważanie co się da zaimplementować efektywniej: modulo czy reguła podzielności.

 

            numerator = ulong.MaxValue - 1;

            denominator = 3;

            for (int i = 0; i < stomilionów; i++)  // 1e8

            {

                if (numerator % denominator != 0)

                {

                    result = false;

                }

            }

[thikim 117]

Też się zastanawiałem jak jest dla większych wartości.

Puszczę dla 100 mln

[wilk 103]

 

 

Miejsca na zysk nie ma, o ile posługujemy się typem wspieranym przez sprzęt.

 

A od czego wątki? Niech te pozostałe rdzenie do czegoś się przydadzą.

[Gość Astro]

to byłby dobry moment na rozważanie co się da zaimplementować efektywniej: modulo czy reguła podzielności

 

Podejrzewam, że z domowymi implementacjami może być kłopot (choć chętnie dam się zaskoczyć przez niezwykle zdolnych forumowiczów, których na KW nie brakuje), polecam zatem całkowicie wolną (choć wystarczająco szybką ) bibliotekę GMP:

https://gmplib.org/

szczególnej uwadze polecam:

https://gmplib.org/manual/Low_002dlevel-Functions.html#Low_002dlevel-Functions

 

Ed. Jajcenty. Nie wiem jak Twój kompilator, ale podsunąłbym myśl w kontekście optymalizacji. Zapodaj w pętli zamiast

if (numerator % denominator != 0)

if (numerator % 3 != 0)

Osobiście jako starozakonny napisałbym:

if (numerator % 3)

 

Właściwie to nie ma potrzeby tracenia czasu na całą pętlę, bo wynik Twojego algorytmu jest znany z góry.

 

 

numerator = ulong.MaxValue - 1;

denominator = 3;

for (int i = 0; i < stomilionów; i++) // 1e8

 {

   if (numerator % denominator != 0)

    {

      result = false;

    }

  }

 

Taka tam optymalizująca modyfikacja

 

            numerator = ulong.MaxValue - 1;

            denominator = 3;

            if (numerator % denominator) result = false;

 

 /*   taki tam fajny komentarz

            for (int i = 0; i < stomilionów; i++)  // 1e8

            {

                if (numerator % denominator != 0)

                {

                    result = false;

                }

            }

   */

Ed. W ogóle, to może przed "szatańskim świętem" (Halloween! ):

https://www.youtube.com/watch?v=KWmD_HcOcfU

Edytowane 28 października 2016 przez Astro

[Matcher 2]

Thikim tak jak dla 10mln tak samo i dla 100mln, i do nieskończoności wzór (x*30)+y będzie prawdziwy

 

Zauważ jeszcze,że liczbę 179 424 719 możesz wygenerować poniżej sekundy stosując tylko wzór, lecz jeśli wygenerujesz dalsze liczby, to nie będziesz wiedział czy są one liczbami pierwszymi na 100%. W tym cała zabawa Należy to tak obejść, by nie bawić się w sprawdzanie.. Ale to chyba nie wykonalne.

 

Dobrze zrobiłeś,że porównałeś wydajność takiego algorytmu z "klasycznym". Czy w tym algorytmie generowałeś tylko liczby pierwsze? Jeśli tak to w jaki sposób?

 

Ja bym każdą kolejną liczbę opisaną wzorem (x*30)+y dzielił przez liczby od najmniejszej opisanej tym samym wzorem do liczby najwyższej nie większej od dzielonej liczby,lub nie wyższej od jej pierwiastka. Czyli np. liczba 127 zostanie podzielona za każdym razem przez liczby (11,13,17,19..itd) Jeśli nie podzieli się całkowicie, to jest liczbą pierwszą

[Gość Astro]

 

 

Ja bym każdą kolejną liczbę opisaną wzorem (x*30)+y dzielił przez liczby od najmniejszej opisanej tym samym wzorem

 

Matcher, ale mówimy dalej o algorytmie generowania KOLEJNYCH liczb pierwszych (tak się zaczął ten wątek)? Załóżmy, że masz "wstępną" tablicę liczb pierwszych, załóżmy, że do mizernego miliona. Czyli jak, lecisz ze wszystkimi y przez ową tablicę, po wszystkich naturalnych x od 2 do obliczeniowego "w χ_υ^ι"?

Ed. By nie było wątpliwości. Twój "algorytm" 30x+y działa "w tył", ale nie działa "w przód", czyli nie pozwala na znalezienie wszystkich większych liczb pierwszych.

[Matcher 2]

Astro algorytm je znajduje tylko TY nie wiesz które to są

 

Po co mi tablica 1mln liczb pierwszych... Do generowania KOLEJNYCH liczb pierwszych wystarczy mi tylko 8 liczb pierwszych. Jeśli zaczynam generowanie od pewnej liczby L to sprawdzę czy kończy się ona cyfrą (1,3,7,9) i sumą cyfr (1,2,4,5,7,8). Potem wystarczy policzyć gdzie ona się znajduje i dodawać do niej następne liczby oraz dzielić ją przez poprzednie liczby wyrażone wzorem.

 

Przykładowo Liczba 179 424 719 podzielona przez 30 da wynik 5980823,96667  Jeśli część całkowitą 5980823 pomnożymy przez 30 to otrzymamy 179 424 690 czyli jest to liczba o 29 mniejsza od 179 424 719.       29 to jedna z liczb pierwszych początkowych i jest ona 6-sta z nich. Liczba 6 to ważna informacja.

I teraz liczymy,że Liczba 179 424 719 znajduje się DOKŁADNIE na miejscu o numerze (5980823*8)+6 = 47 846 590

Nie jest to numer liczby pierwszej, tylko liczby ze zbioru wyrażonego wzorem (x*30)+y, a zbiór jest nieskończony.

 

W RSA szyfrowanie skupia się na iloczynie liczb pierwszych. NP. (LP1 * LP2) = L

 

Wnioskuję ,że liczby LP1, LP2, oraz L należą do zbioru wyrażonego wzorem (x*30)+y szkoda,że matematykiem nie jest, bo może opisałbym lepiej te zależności.

[thikim 117]

Porównanie dla 100 000 000 liczb pierwszych:

Klasycznie:

Liczba pierwsza  2038074751

Czas pracy:1812,9 s

 

„4”

Liczba pierwsza   2038074751

Czas pracy:1736,2757684

 

„30”

Liczba pierwsza  2038074769

Czas pracy:1743,2 s

 

Jak widać "4" która eliminuje liczby podzielne przez "5" daje największą optymalizację
Tylko po co w takim razie sprawdzamy później podzielność przez 5?

[Gość Astro]

 

 

Do generowania KOLEJNYCH liczb pierwszych wystarczy mi tylko 8 liczb pierwszych. Jeśli zaczynam generowanie od pewnej liczby L to sprawdzę czy kończy się ona cyfrą (1,3,7,9) i sumą cyfr (1,2,4,5,7,8). Potem wystarczy policzyć gdzie ona się znajduje

 

Wyłuszcz, proszę, nieco może dłużej (nikt się nie obrazi ), nie trzeba wersalików; odnieś się szczególnie do wytłuszczenia.

 

 

 

Przykładowo Liczba 179 424 719

 

Przykładowo wczoraj zrobiłem trzy kupy. Dzisiaj już tak nie było, i zapewne nie będzie jutro.

[Matcher 2]

Thikim napisz jak przebiega algorytm z tą "4"

 

Astro wytłumaczę to na tablicy 2-wymiarowej. Przykładowa tablica wygenerowana na podstawie (x*30)+y gdzie y = (11,13,17,19,23,29,31,37), x = numer wiersza.

 

0 (11,13,17,19,23,29,31,37)

1 (41,43,47,49,53,59,61,67)

2 (71,73,77,79,83,89,91,97)

 

11=(0*30)+11;

 

Według tej tablicy liczba na miejscu pierwszym to 11, na miejscu 12 - 49, na miejscu 24 - 97

 

Jeśli tablica jest nieskończona to liczba na miejscu 47 846 590 jest równa 179 424 719

 

I według logiki tablicy nie musisz nigdzie zapisywać, bo masz ją dostępną natychmiast.

[thikim 117]

Nic specjalnego: do ogólnej pętli dodającej +2 (czyli generującej liczby: 5,7,9,11,13,15,17 dodaję sprawdzenie:

                licznikdwojek++;
                if (licznikdwojek == 4)
                {
                    licznikdwojek = 0;
                    liczba = liczba + 2;
                }

które powoduje że pętla zamiast dodawać ciągle "2" w pewnym momencie dodaje "4". Co powoduje pomijanie: liczb z końcówką "5".

No i start muszę robić od 7. Wtedy generowane liczby są takie: 7,9,11,13,17,19..

Można zrobić to też za pomocą tablicy. Czy będzie szybciej? Wątpię.

Edytowane 28 października 2016 przez thikim

[Matcher 2]

Teraz pytanie: Czy da się to jeszcze bardziej zoptymalizować?

[thikim 117]

Ogólnie można jeszcze kombinować. Ale zauważ że nawet algorytm z "4" nie zadział dużo szybciej od klasycznego. Z 1812 sekund na 1736 sekund.

Opłaca się oczywiście.

Sprawa pierwsza. Drzewiej w assemblerze bywało tak że szybciej oznaczało więcej kodu.

Tak więc to że możemy to upchnąć w jedną linijkę czy dwie nie oznacza że to będzie szybciej, może być całkiem przeciwnie.

Można próbować jak pisałem wcześniej odrzucić liczba % 5. Bo takich liczb już nie generujemy. Przyrost szybkości powinien być: minimalny. Itd.

Jeżeli chcemy dużego przyrostu to tylko: wątki, GPU lub lepszy sprzęt.

Ja to uruchomiłem już na dość przyzwoitym, ale czas leci do przodu i postęp jest.

Edytowane 28 października 2016 przez thikim

[Matcher 2]

Stwórz Tablicę (2,4,2,4,6,2,6,4) zaczynając od 11 dodawaj te liczby i zapętlaj. Sprawdź czas wykonania algorytmu.

[thikim 117]

Zrobiłem podobnie z tablicą dla "30" wyniki masz wyżej. Było gorsze niż dla "4".

Edytowane 28 października 2016 przez thikim