Skocz do zawartości
Forum Kopalni Wiedzy
KopalniaWiedzy.pl

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

Rekomendowane odpowiedzi

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 przez Afordancja

Udostępnij tę odpowiedź


Odnośnik do odpowiedzi
Udostępnij na innych stronach
A te 100 pierwszych liczb to leciałeś od góry(MAX LONG?) tak?,

Właśnie :D  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 przez Jajcenty

Udostępnij tę odpowiedź


Odnośnik do odpowiedzi
Udostępnij na innych stronach

 

 

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 :D

Udostępnij tę odpowiedź


Odnośnik do odpowiedzi
Udostępnij na innych stronach
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? :D

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 przez Afordancja

Udostępnij tę odpowiedź


Odnośnik do odpowiedzi
Udostępnij na innych stronach

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?

Udostępnij tę odpowiedź


Odnośnik do odpowiedzi
Udostępnij na innych stronach
A nie lepiej byłoby dzielić tylko przez znalezione już liczby pierwsze? Czyli sprawdzanie koniecznie od najmniejszych.

Tak właśnie robię :D

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 przez Afordancja

Udostępnij tę odpowiedź


Odnośnik do odpowiedzi
Udostępnij na innych stronach

 

 

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 263? To całkiem sporo bajtów :D Rzędu 1017

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 1012 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ć 108 największych 63 bitowych liczb pierwszych. W ten sposób uzyskamy 100 milionów liczb pierwszych (oni tylko kilkanaście milionów) rzędu 1017. Ci najbardziej zaciekli powtórzą i zweryfikują obliczenia z artykułu. Ale to już fakultatywnie :)

Udostępnij tę odpowiedź


Odnośnik do odpowiedzi
Udostępnij na innych stronach
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 :D

 

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

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

 

Edycja:

Wygenerować i zapamiętać 108 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 przez Astro

Udostępnij tę odpowiedź


Odnośnik do odpowiedzi
Udostępnij na innych stronach

 

 

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  :P

 

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 przez Jajcenty

Udostępnij tę odpowiedź


Odnośnik do odpowiedzi
Udostępnij na innych stronach
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 :P

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

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

Edytowane przez Astro

Udostępnij tę odpowiedź


Odnośnik do odpowiedzi
Udostępnij na innych stronach

Masz zamiar zapamiętać wszystkie pierwsze mniejsze od 263? To całkiem sporo bajtów :D Rzędu 1017

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...
  • Pozytyw 1

Udostępnij tę odpowiedź


Odnośnik do odpowiedzi
Udostępnij na innych stronach
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 przez Jajcenty

Udostępnij tę odpowiedź


Odnośnik do odpowiedzi
Udostępnij na innych stronach
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. :D

 

 

 

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ć. ;):D

  • Pozytyw 1

Udostępnij tę odpowiedź


Odnośnik do odpowiedzi
Udostępnij na innych stronach

 

 

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

Udostępnij tę odpowiedź


Odnośnik do odpowiedzi
Udostępnij na innych stronach
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 przez Jajcenty

Udostępnij tę odpowiedź


Odnośnik do odpowiedzi
Udostępnij na innych stronach
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.

Udostępnij tę odpowiedź


Odnośnik do odpowiedzi
Udostępnij na innych stronach

 

 

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

Udostępnij tę odpowiedź


Odnośnik do odpowiedzi
Udostępnij na innych stronach

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

Udostępnij tę odpowiedź


Odnośnik do odpowiedzi
Udostępnij na innych stronach
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. ;)

Udostępnij tę odpowiedź


Odnośnik do odpowiedzi
Udostępnij na innych stronach

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

Udostępnij tę odpowiedź


Odnośnik do odpowiedzi
Udostępnij na innych stronach
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 przez Jajcenty

Udostępnij tę odpowiedź


Odnośnik do odpowiedzi
Udostępnij na innych stronach

 

 

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

Udostępnij tę odpowiedź


Odnośnik do odpowiedzi
Udostępnij na innych stronach

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

Udostępnij tę odpowiedź


Odnośnik do odpowiedzi
Udostępnij na innych stronach

 

 

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 ? ;)

Udostępnij tę odpowiedź


Odnośnik do odpowiedzi
Udostępnij na innych stronach

 

 

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.

Udostępnij tę odpowiedź


Odnośnik do odpowiedzi
Udostępnij na innych stronach

Jeśli chcesz dodać odpowiedź, zaloguj się lub zarejestruj nowe konto

Jedynie zarejestrowani użytkownicy mogą komentować zawartość tej strony.

Zarejestruj nowe konto

Załóż nowe konto. To bardzo proste!

Zarejestruj się

Zaloguj się

Posiadasz już konto? Zaloguj się poniżej.

Zaloguj się

×