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

[Afordancja 57]

W każdym razie mój naiwny, jednowątkowy algorytm dostarczył 100 liczb pierwszych w 54 minuty, na dobę jakieś 2500. Obciążenie procesora mniejsze od 25% Czyli kicha, słabo i nędza z mułem. Postawiłem sobie za punkt honoru, że w wolnym czasie wyduszę z niego 10 razy więcej.

 

 

hm..jesteś pewien?

Mój algorytm, (pisany w javie, czyli raczej wolniej niż Twój), ale z trochę innym podejściem, zwraca w 5 minut i 34 sekundy 455 052 511 liczb pierwszych,  zakresu 1 do 10  miliardów.

w 11 czy 12, minyt, razy 2 mniej wiecej, potem zaczynaja sie male schody dla mnie (wydajnoscoiwe ale jeszcze nie sprawdzalem) 

Myślę, że na drugim komputerze, mogę na luzie dojść do zakresu 100 miliardów, potem schody, ale mam pewną myśl optymalizacyjną, wiec schody przełożę na trochę wyżej (Ale to na drugim kompie).

 

[Edit]

A te 100 pierwszych liczb to leciałeś od góry(MAX LONG?) tak?, aż sprawdzę tzn. moje plus 100 pierwszych od góry (w tym momencie mój algorytm raczej będzie słabszy niż teraz, bo z założenia szuka od dołu

Edytowane 17 marca 2016 przez Afordancja

[Jajcenty 314]

A te 100 pierwszych liczb to leciałeś od góry(MAX LONG?) tak?,

Właśnie  Piersze co zrobię to isPrime() jako inline. Potem wątki.

 

            ulong Number = ulong.MaxValue;

            ulong howMuch = 100;

 

             do

            {

                if (isPrime(Number))

                {

                    file.WriteLine(Number.ToString());

                    howMuch--;

                }

            } while (--Number > 0 && howMuch > 0);

 

 

tak, wiem, formalnie powinno być howMany, ale mu tu wszyscy kochamy dźwięk "hałmać".

Edytowane 17 marca 2016 przez Jajcenty

[radar 104]

 

 

hm..jesteś pewien? Mój algorytm, (pisany w javie, czyli raczej wolniej niż Twój), ale z trochę innym podejściem, zwraca w 5 minut i 34 sekundy 455 052 511 liczb pierwszych, zakresu 1 do 10 miliardów

O! To mój nawet szybciej, ale Jacenty robi to na liczydle

[Afordancja 57]

O! To mój nawet szybciej, ale Jacenty robi to na liczydle

 

O a o ile szybciej? I czy używasz wątków ? Bo oprócz wątków(bo ich nie mam, z resztą komp gówniany bo tylko 2 rdzenie :/ ) mam  z dwa, trzy miejsca gdzie mogę dość przyspieszyć (ale pisać mi się nie chce, bo wolę jak komp liczy, niż ja piszę ) i nie wiem czy czuć wyzwanie?

A i w czym? w C?  

 

Możesz podać jakiś zakres np. od 1 do 100 miliardów (i ile tam masz liczb pierwszych? i w jakim czasie to liczysz) Wieczorem przysiąde i coś skrobnę.

Kurcze, zapomniałem ze w javie Long jest signed, a nie mam zamiaru, bawić się w Big, wiec sprawdzę maks połowę mniej.

@Radar i podaj czas dla tego co liczy @Jajcenty bo to raczej trochę inna klasa problemu, nie sądzę abyś miał jakieś rzędy wielkości szybciej.(ja niestety nie mogę podać po tylko signed long)

Edytowane 17 marca 2016 przez Afordancja

[pogo 102]

A nie lepiej byłoby dzielić tylko przez znalezione już liczby pierwsze? Czyli sprawdzanie koniecznie od najmniejszych.

Jak będę miał chwilę to dołączę do konkursu. I od razu zastrzegam, że chcę pisać wielowątkowo... co się pewnie wysypie jak będą korzystać ze wspólnych tablic.

 

Myślę jeszcze jak ograniczyć największą liczbę przez jaką jest sens dzielić. Chyba do momentu gdy kwadrat tej liczby będzie większy od testowanej, a może jeszcze bardziej?

[Afordancja 57]

A nie lepiej byłoby dzielić tylko przez znalezione już liczby pierwsze? Czyli sprawdzanie koniecznie od najmniejszych.

Tak właśnie robię

Tylko wymyśliłem mały update, który wieczorem wdrożę i mam nadzieję, że przyspieszy dość znacznie.

 

 

 

Chyba do momentu gdy kwadrat tej liczby będzie większy od testowanej, a może jeszcze bardziej?

 

I tak też pewnie wszyscy robią.

 

No nic zobaczę jak mój update wpłynie na szybkość, wielowątkowość oleję, bo tylko 2 rdzenie.

 

Moj pierwszy cel to sprawdzić w jakim czasie jestem w stanie wygenerować liczby pierwsze od 2 do signed long max. 

(liczę tylko maks 8-12 godzin, nie lubię więcej czkać, ile wyliczę przez ten czas na tylu będę wykonywał badania.

Potem badanie liczb dopiero.

Edytowane 17 marca 2016 przez Afordancja

[Jajcenty 314]

 

 

Myślę jeszcze jak ograniczyć największą liczbę przez jaką jest sens dzielić

Nie wiem, czy o to chodzi: szukamy podzielników N w zakresie 2 do sqrt(N) +1 .  Bo wystarcza nam jeden, jakikolwiek podzielnik. 

 

Moj pierwszy cel to sprawdzić w jakim czasie jestem w stanie wygenerować liczby pierwsze od 2 do signed long max.

Z tym jest trochę problem. Masz zamiar zapamiętać wszystkie pierwsze mniejsze od 2⁶³? To całkiem sporo bajtów Rzędu 10¹⁷

Pozostaje je tylko policzyć.

 

[ myślę że od tego miejsca należałoby to wydzielić jako offtop ]

 

Historia: zbadano kilkanaście milionów liczb pierwszych rzędu 10¹² i stwierdzono pewne regularności sugerujące nielosowość liczb pierwszych.

Oprotestowałem to, twierdząc że ja i mój wierny laptop potrafimy lepiej. Po wstępnym zmierzeniu się z problemem muszę trochę odpuścić z pierwotnych założeń.

Ponieważ część z nas nie ma dostępu do 64 bitowych liczb bez znaku, możemy sformułować następujące wyzwanie:

Wygenerować i zapamiętać 10⁸ największych 63 bitowych liczb pierwszych. W ten sposób uzyskamy 100 milionów liczb pierwszych (oni tylko kilkanaście milionów) rzędu 10¹⁷. Ci najbardziej zaciekli powtórzą i zweryfikują obliczenia z artykułu. Ale to już fakultatywnie

[Gość Astro]

Jak będę miał chwilę to dołączę do konkursu.

 

Nie zostaje Mariuszowi zatem nic innego, jak ogłosić już właściwie ogłoszony konkurs (musi pomyśleć o nagrodzie ).

Ponieważ biblioteka podlinkowana przeze mnie wyżej operuje również do uint64 i wygląda na wysoce zoptymalizowane segmentowe sito, to proponuję jazdę po całym zakresie i podawanie własnych wyników procentowo (zestawionych z primesieve). Wyniki wyżej 100% zapewne mile widziane (dodatkowa nagroda ). Kod do testowania proponuję wysyłać modom (Pogo i Wilk). Pogo, przykro mi, ale wykluczyłem Cię z konkursu; ktoś musi to przetestować… Znajdziesz zapewne innego arbitra i wrócisz do gry.

 

ale Jacenty robi to na liczydle

 

Podobne jest raczej kopaniu studni od dołu, ale jeszcze nam szczęki mogą opaść gdy Jajcenty drukiem ogłosi swoją inline isPrime().

(ponieważ nigdy nie ufałem inline, to czemu nie zatrudnić preprocesora? )

 

Edycja:

Wygenerować i zapamiętać 10⁸ największych 63 bitowych liczb pierwszych.

 

Protestuję. Tak postawiony problem nie pozwoli na zrobienie statystyki, o której jest mowa w artykule. Może być bez znaku, ale muszą być wszystkie. Oczywiście analiza może być w drugim konkursie.

Edytowane 17 marca 2016 przez Astro

[Jajcenty 314]

 

 

Protestuję. Tak postawiony problem nie pozwoli na zrobienie statystyki, o której jest mowa w artykule. Może być bez znaku, ale muszą być wszystkie.

 

Pozwoli, pozwoli. W końcu będzie ich z 50 razy więcej do analizy i będą z ciągłego podzbioru N. Oczywiście mogę ci wygenerować wszystkie, ale Ty dajesz dyski 

 

ale jeszcze nam szczęki mogą opaść gdy Jajcenty drukiem ogłosi swoją inline isPrime(). (ponieważ nigdy nie ufałem inline, to czemu nie zatrudnić preprocesora?

Niestety inline urwało tylko 2 minuty z 54 na 52 minuty.  Nie tędy droga.

Wreszcie! Po latach! Użyłem! GOTO! I jest to pełnoprawne użycie wyklętej przez teoretyków, ale jak widać niezbędnej instrukcji.

 

            do

            {

                if (Number % 2 == 0) continue;

                if (Number % 3 == 0) continue;

                if (Number % 5 == 0) continue;

                if (Number % 7 == 0) continue;

                if (Number % 9 == 0) continue;

 

                for (ulong dvd = 11; dvd < Math.Sqrt(Number) + 2; dvd += 2)

                {

                    if (Number % dvd == 0)

                        goto NotPrime;

                }

                file.WriteLine(Number.ToString());

                howMuch--;

 

            NotPrime: continue;

 

            } while (--Number > 0 && howMuch > 0);

 

 

edit: poprawiłem błąd z powodu upodobania do ostrych nierówności;

Edytowane 17 marca 2016 przez Jajcenty

[Gość Astro]

jak widać niezbędnej instrukcji.

 

Nie jest niezbędna.

Nie bardzo rozumiem po co w for testujesz np. dzielenie przez 15… Nie bardzo rozumiem też celowość każdorazowego wywoływania w for Math.Sqrt(Number)…

 

Edycja: Jajcenty, kogo jak kogo, ale Ciebie chyba nie trzeba prosić o jakąś netykietę (modyfikacja).

 

 

ale Ty dajesz dyski

Nic z tego. Kto pierwszy rzucił rękawicą?

Moim skromnym zdaniem chłopcy zrobili kawał solidnej roboty, ale każdy programista (z definicji ) musi pokazać, że ma dłuższy ulong.

Edytowane 17 marca 2016 przez Astro

[Jan 2]

Masz zamiar zapamiętać wszystkie pierwsze mniejsze od 2⁶³? To całkiem sporo bajtów Rzędu 10¹⁷

Pozostaje je tylko policzyć.

to będzie około 2^63/log(2^63)*4B ~= 8.4486e+17 ~= 850 PB. Powodzenia 

 

Przy takiej ilości rozsądne wydaje się przygotować stałą listę pierwszych mniejszych od 2^32 czyli około 740 MB, później sprawdzać blokami co 2^32, analiza co blok danych (z małą nakładką z poprzedniego bloku), następny blok...

[Jajcenty 314]

Nie jest niezbędna.

Tak oczywiście mogę ustawić flagę, wykonać break  i sprawdzenie flagi żeby zobaczyć jak wyszło z wewnętrznej pętli. Walczymy o każdy cyk zegara, więc goto i posprzątane,

 

 

po co w for testujesz np. dzielenie przez 15

Ponieważ wykrycie że dvd == 15 albo ogólnie sprawdzenie (dvd > 5 && dvd%5==0) jest kosztowniejsze. Obracamy się w rejestrach procesora i 500/24 jest tak samo kosztowne jak 5555555/2358. Gdybym użył biblioteki do obliczeń z dużą liczbą cyfr, wtedy byłoby się o co bić.

 

 

Nie bardzo rozumiem też celowość każdorazowego wywoływania w for Math.Sqrt(Number)…

Good point. Sprawdzę to, ale jestem pewien że kompilator liczy to raz przy konstruowaniu pętli - sprawdza warunki pirewrszego wejścia. 

 

 

 

stałą listę pierwszych mniejszych od 2^32 czyli około 740 MB, później sprawdzać blokami co 2^32

Będizie sporo tych bloków zanim dojedziemy do 2^63. Jakieś 2^31.

Edytowane 17 marca 2016 przez Jajcenty

[Gość Astro]

 

 

Walczymy o każdy cyk zegara, więc goto i posprzątane,

 

Nie bardzo mam czas na obalenie tezy, więc tymczasem hipoteza: NIEKONIECZNIE.

 

 

 

Ponieważ wykrycie że dvd == 15 albo ogólnie sprawdzenie (dvd > 5 && dvd%5==0) jest kosztowniejsze.

 

Spójrz na koncept Radara. Nie musi być wielowątkowe, ale zdecydowanie rokuje lepiej.

 

 

 

jestem pewien że kompilator liczy to raz przy konstruowaniu pętli

 

Cieszę się Twoją pewnością. Ponieważ optymalizacja tymczasem to jeszcze nie AI, to wolę osobiście o to zadbać.

[Jan 2]

 

 

Będizie sporo tych bloków zanim dojedziemy do 2^63. Jakieś 2^31.

    

[Jajcenty 314]

Spójrz na koncept Radara. Nie musi być wielowątkowe, ale zdecydowanie rokuje lepiej.

Muszę zobaczyć cudzy gotowy kod używający tej własności. Wtedy będę wiedział. Na razie odsuwam to koniec listy.

 

 

Cieszę się Twoją pewnością.

I dobrze. Masz rację. Cymbał kompilator liczy to za każdym razem. Duży plus dla Ciebie, a ja się czuje zrobiony w bambuko - jestem prawie pewien, że powinien to zoptymalizować do stałej.

 

 

 

Edycja: Jajcenty, kogo jak kogo, ale Ciebie chyba nie trzeba prosić o jakąś netykietę (modyfikacja)

A tu nie wiem o co chodzi - skomentowałem przeca edycję? Nie zmiąchałem też, za dużo?. Ot 1 zmieniła się na 2 .

Edytowane 17 marca 2016 przez Jajcenty

[Gość Astro]

 

 

Cymbał kompilator liczy to za każdym razem. […] jestem prawie pewien, że powinien to zoptymalizować do stałej.

 

Ponieważ Twój namber jest zmienną (szczególnie, że ją zmieniasz ), to dostrzegam jednak w kompilatorze cechy mądrości.

 

 

 

A tu nie wiem o co chodzi

 

Wydaje mi się, że edycje napisanego już tekstu na poziomie "technicznym" (korekta językowa) jest ok., jednak dodawanie na początku posta nowego tekstu już niekoniecznie. Lepiej wygląda dodanie niżej po "Edit", "Edycja", "Oj, zapomniałek", "Oj, nie zauważyłek" itp.

[Jajcenty 314]

 

 

Ponieważ Twój namber jest zmienną (szczególnie, że ją zmieniasz ), to dostrzegam jednak w kompilatorze cechy mądrości.

 

No nie wiem. Nie widzę jak zmienna Number miałaby się zmienić w ramach pętli for. Ale OK, nie pierwszy raz mamy kontrowersję z kompilatorem.

 

Lepiej wygląda dodanie niżej po "Edit"

Skoro tak uważasz - nie ma sprawy.Specjalnie dla Ciebie będę sufiksował, nigdy prefiksował. 

[radar 104]

O kurcze, dopiero zobaczyłem, że tu się konkurs zrobił.D

Dla javowców, BigInteger nie posiada ograniczenia z góry, więc można i 2¹⁰⁰ jak ktoś ma tyle pamięci

[Gość Astro]

 

 

No nie wiem. Nie widzę jak zmienna Number miałaby się zmienić w ramach pętli for

 

No chyba już ustaliliśmy, że kompilator to żadna AI. Swoją drogą, przykładów konstrukcji bardzo prostej pętli wywołującej funkcję z Twoim namberem można mnożyć; funkcja może wywoływać pińcet innych i nawet Tobie tygodnia może braknąć by rozstrzygnąć, czy się w końcu zmienia, czy nie. Może być też zmienną globalną, ale trzymajmy się może jednego – kompilator jest głupi, a inteligencji oczekujmy od piszącego kod.

[radar 104]

Ale piszmy wszyscy jednowątkowo, bo inaczej czasy będą nieporównywalne

[Jajcenty 314]

Ale piszmy wszyscy jednowątkowo, bo inaczej czasy będą nieporównywalne

I tak będą nieporównywalne bo mamy różne maszyny. A jednowątkowo  to się nawet nie zbliżymy do jakiś rozsądnych czasów.

 

Tak się zastanawiam. Skoro w publikacji chodzi o korelację między ostatnimi cyframi, to może nie trzeba pamiętać wszystkiego, a wystarczy tablica 10x10 do zapamiętania częstości par.

 

 

 

funkcja może wywoływać pińcet

Tak, zajarzyłem w końcu. Przyczyną jest funkcja. Kompilator słusznie nie chciał uronić ni jednego  efektu ubocznego. Dobry krzemiak.

 

EDYCJA: 

Po ostatnich zmianach 48 minut / 100 największych. Urwaliśmy 6 minut z 54. Astro urwał 4. Brawo Astro!

Edytowane 17 marca 2016 przez Jajcenty

[Afordancja 57]

 

 

to będzie około 2^63/log(2^63)*4B ~= 8.4486e+17 ~= 850 PB. Powodzenia 

 

Ja tego nie muszę nigdzie zapisać aby zrobić badanie, wystarczą mi dwie kolejne a potem je zapominamy  

 

 

 

Muszę zobaczyć cudzy gotowy kod używający tej własności. Wtedy będę wiedział. Na razie odsuwam to koniec listy.

 

Myślę, że mamy podobny koncept z radarem, i sprawdzałem (mimo, że w javie i parę rzeczy mam hm..delikatnie rzecz mówiąc, na szybciora (teraz to poprawię)) Twoje liczenie o tyłu (chociaż nie tak to sobie ułożyłem) i znalezienie 100 ostatnich zajmuje mi 20 minut. Przeczytam forum i zasiadam do poprawek, mam nawet mega koncepcję, która narodziła się w samochodzie, ale muszę to przemyśleć.

 

 

 

 

O kurcze, dopiero zobaczyłem, że tu się konkurs zrobił.D Dla javowców, BigInteger nie posiada ograniczenia z góry, więc można i 2100 jak ktoś ma tyle pamięci

Oj tam od razu konkurs, lepsza motywacja, do co BigInteger, to ja dziękuję już wole liczyć 2 razy mniej, wydajnością bym raczej padł.

 

 

 

Ale piszmy wszyscy jednowątkowo, bo inaczej czasy będą nieporównywalne

dobra koncepcja ale i tak nie będą, o kompy różne, ja będę na pewno pisał jednowątkowo (Aż tak serio do tego nie podchodzę)

[pogo 102]

@@Jajcenty

Jak pozbędziesz się dzielenia na 5 to urwiesz kolejne 20%. Wystarczy zrobić pętlę, która w środku będzie miała od razu 4 liczby do policzenia z 1, 3, 7 i 9 na końcu. Do tego redukujesz ilość obiegów pętli, co też poprawi wydajność.
Analogicznie można pomijać dzielenie liczb z 5 na końcu. Kod się robi długi i niezbyt ładny, ale bardziej optymalny.

Do zabawy będę mógł dołączyć dopiero w sobotę, więc pewnie będzie już wtedy po wszystkim.

Inna sprawa, że nie szczególnie podoba mi się koncepcja powtarzania cudzych badań, wolałbym poszukać innych zależności.

[Afordancja 57]

 

 

Do zabawy będę mógł dołączyć dopiero w sobotę, więc pewnie będzie już wtedy po wszystkim.

 

Nie byłbym tego taki pewien

 

 

 

 

Inna sprawa, że nie szczególnie podoba mi się koncepcja powtarzania cudzych badań, wolałbym poszukać innych zależności.

Ależ akurat ja chcę zbadać trochę inne zależności (patrz mój pierwszy post). Tzn. chcę ich badanie bardziej uogólnić, bo przecież ostatnia cyfra to nic innego jak -> liczba pierwsza % 10. A dlaczego ta 10 taka uprzywilejowana ?

[radar 104]

 

 

Wystarczy zrobić pętlę, która w środku będzie miała od razu 4 liczby do policzenia z 1, 3, 7 i 9 na końcu. Do tego redukujesz ilość obiegów pętli, co też poprawi wydajność.

No ja tak dokładnie robię. Zamieszczę potem timingi.