Skocz do zawartości


Zdjęcie

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


  • Zaloguj się, aby dodać odpowiedź
275 odpowiedzi w tym temacie

#21 ~Astro

~Astro
  • Goście

Napisano 16 marzec 2016 - 22:16

Tak

 

Nie wiem, może wywaliłbym deklarację uint/ ulong zmiennej tmp przed pętlę? ;)



Reklamy Google

#22 Weinreb

Weinreb

    Górnik

  • Nowi użytkownicy
  • Pip
  • 2 postów

Napisano 17 marzec 2016 - 10:51

Słyszeliście pewnie o projekcie BOINC? 

 

http://www.primegrid.com

 

http://primes.utm.edu/primes/home.php ,

 

https://oeis.org/A000040,

 

polecam też zerknąć tu:

 

http://factordb.com


  • 0

#23 Xitami

Xitami

    Górnik

  • Użytkownicy
  • Pip
  • 7 postów

Napisano 17 marzec 2016 - 11:19

Dwa nieporozumienia

1 - przecie nie chodzi o najmłodszą cyfrę

2 - testowanie pierwszości przez dzielenie


  • 1

#24 radar

radar

    Lis major

  • Użytkownicy
  • PipPipPipPipPip
  • 1290 postów

Napisano 17 marzec 2016 - 11:50

Dwa nieporozumienia 1 - przecie nie chodzi o najmłodszą cyfrę 2 - testowanie pierwszości przez dzielenie

No ba, testy "pierwszości" istnieją, ale są probabilistyczne i/lub opierają się na jeszcze nieudowodnionych twierdzeniach.

 

My tu mówimy o amatorskim obliczaniu, które mimo "amatorskości" wykracza zakresem dużo dalej niż badali naukowcy z artykułu. Przy amatorskim algorytmie, gdzie dzielimy, najmłodsza cyfra ma sens, bo testujesz tylko 4 liczby z 10.


  • 0

#25 Jajcenty

Jajcenty

    padawan młody

  • Użytkownicy
  • PipPipPipPipPipPip
  • 3233 postów

Napisano 17 marzec 2016 - 12:07

A co tu jest do "wykrywania"? Wszystko co się kończy na 0 lub 5 jest podzielne przez 5, czyli nie jest liczbą pierwszą dla n>5
 

Och, tak. Ale dopóki trzymamy się poniżej 19 cyfr znaczących to sprawdzanie podzielników na podzielność przez 5 dokłada roboty. Chyba że umiemy z 2n+1 wywalić te podzielne przez 5 nie używając modulo?

 

Nie wiem, może wywaliłbym deklarację uint/ ulong zmiennej tmp przed pętlę?

Nic to nie zmieniło, ale rzecz jest do dalszego śledztwa - mimo nastaw x64 kompilator z uporem produkuje win32. Włoski strajk?

 

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.

 

Oto największy 64 bitowy prime: 18446744073709551557


W jednym odcinku było o funkcji dzeta, a konkretnie o hipotezie Riemanna. Jeśli mnie pamięć nie myli jakiś fizyk z matematykiem na konferencji naukowej w przerwie na kawę (sic!), wzorem tym opisali orbitale we wszystkich atomach.

To chyba nadaje się jako osobny wątek do dyskusji bo w ferworze walki nam to umknęło. Widziałem jedną alternatywną teorię orbitali atomowych, ale jej twórca nie zyskał sobie uznania. 


  • 0

#26 Afordancja

Afordancja

    Nadsztygar

  • Użytkownicy
  • PipPipPipPip
  • 604 postów

Napisano 17 marzec 2016 - 12:21

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


Użytkownik Afordancja edytował ten post 17 marzec 2016 - 12:31

  • 0

#27 Jajcenty

Jajcenty

    padawan młody

  • Użytkownicy
  • PipPipPipPipPipPip
  • 3233 postów

Napisano 17 marzec 2016 - 12:50

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

Użytkownik Jajcenty edytował ten post 17 marzec 2016 - 12:55

  • 0

#28 radar

radar

    Lis major

  • Użytkownicy
  • PipPipPipPipPip
  • 1290 postów

Napisano 17 marzec 2016 - 12:50

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


  • 0

#29 Afordancja

Afordancja

    Nadsztygar

  • Użytkownicy
  • PipPipPipPip
  • 604 postów

Napisano 17 marzec 2016 - 13:29

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)


Użytkownik Afordancja edytował ten post 17 marzec 2016 - 13:01

  • 0

#30 pogo

pogo

    1010011010

  • Moderatorzy
  • 2868 postów

Napisano 17 marzec 2016 - 14:15

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?


  • 0

#31 Afordancja

Afordancja

    Nadsztygar

  • Użytkownicy
  • PipPipPipPip
  • 604 postów

Napisano 17 marzec 2016 - 14:22

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.


Użytkownik Afordancja edytował ten post 17 marzec 2016 - 14:25

  • 0

#32 Jajcenty

Jajcenty

    padawan młody

  • Użytkownicy
  • PipPipPipPipPipPip
  • 3233 postów

Napisano 17 marzec 2016 - 15:05

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


  • 0

#33 ~Astro

~Astro
  • Goście

Napisano 17 marzec 2016 - 15:34

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


Użytkownik Astro edytował ten post 17 marzec 2016 - 15:36


#34 Jajcenty

Jajcenty

    padawan młody

  • Użytkownicy
  • PipPipPipPipPipPip
  • 3233 postów

Napisano 17 marzec 2016 - 15:37

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;

Użytkownik Jajcenty edytował ten post 17 marzec 2016 - 16:02

  • 0

#35 ~Astro

~Astro
  • Goście

Napisano 17 marzec 2016 - 16:03

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


Użytkownik Astro edytował ten post 17 marzec 2016 - 16:10


#36 Jan

Jan

    Górnik

  • Użytkownicy
  • Pip
  • 6 postów

Napisano 17 marzec 2016 - 16:19

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

  • 1

#37 Jajcenty

Jajcenty

    padawan młody

  • Użytkownicy
  • PipPipPipPipPipPip
  • 3233 postów

Napisano 17 marzec 2016 - 16:21

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.


Użytkownik Jajcenty edytował ten post 17 marzec 2016 - 16:25

  • 0

#38 ~Astro

~Astro
  • Goście

Napisano 17 marzec 2016 - 16:31

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



#39 Jan

Jan

    Górnik

  • Użytkownicy
  • Pip
  • 6 postów

Napisano 17 marzec 2016 - 16:42

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

#40 Jajcenty

Jajcenty

    padawan młody

  • Użytkownicy
  • PipPipPipPipPipPip
  • 3233 postów

Napisano 17 marzec 2016 - 16:47

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 .


Użytkownik Jajcenty edytował ten post 17 marzec 2016 - 16:56

  • 0