Goldbach's Conjecture Project

[Troll81]

Że jest problem to ja widzę.... natraciłem już prądu na tym projekcie....

[Kryniek]

Że jest problem to ja widzę.... natraciłem już prądu na tym projekcie....

Już daj spokój, po co łykałeś tyle próbek jak wiesz że projekt jeszcze działa jako beta... albo nawet jeszcze nie.

[Troll81]

:D ale pomarudzić sobie mogę????  %)

[Hani]

Hehe... A tam prąd. Robert nie narzeka.
A tak przy okazji sorka za brak uprzedzenia o przerwie w działaniu dedyka. Stoi niewiadomo czyj (robert sobie zapomniał) a wymiana szafy była w nocy. Mam nadzieje że za bardzo to nie zawaliło sprawy.

[Rysiu]

Właśnie zastanawiałem się co jest nie tak  ;)

Napisałem całą arytmetykę do działania na dużych liczbach (wystarczyło: dodawanie, odejmowanie, porównywanie, modulo i pierwiastek) ale okazuje się, że dla liczb wielkości 10^20 sprawdzanie pierwszości metodą naiwną idzie lekko mówiąc tragicznie.

Jak będę miał chwilkę to podrzucę kod na forum. 64-bit to zaledwie 18* 10^18 i nie wiem czy warto na wbudowanych typach kombinować z BOINC tym bardziej, że app byłaby tylko na 64-bit OS.

[Hani]

Hm.... U mnie 50% to systemy 64bit...
Ale ogolnie to pewnie kolo 5% wiec only 64bit to troche niewypal

[sesef]

Napisałem całą arytmetykę do działania na dużych liczbach (wystarczyło: dodawanie, odejmowanie, porównywanie, modulo i pierwiastek) ale okazuje się, że dla liczb wielkości 10^20 sprawdzanie pierwszości metodą naiwną idzie lekko mówiąc tragicznie.

Zainteresuj się testem Millera-Rabina, i pokombinuj jednak z tym GMP albo MPIR bo te biblioteki kompilowane na konkretną platformę będą szybsze od większości rzeczy które samemu się napisze, a im większe liczby tym większą różnice widać.

[Rysiu]

Zainteresuj się testem Millera-Rabina, i pokombinuj jednak z tym GMP albo MPIR bo te biblioteki kompilowane na konkretną platformę będą szybsze od większości rzeczy które samemu się napisze, a im większe liczby tym większą różnice widać.

Tyle, że z tego co pamiętam test ten zwraca z pewnym prawdopodobieństwem czy dana liczba jest pierwsza czy też nie, a coś takiego odpada.

Najszybszy i w pełni deterministyczny jest ponoć AKS.

Z tymi bibliotekami to jest pat, bo kompletnie nie potrafię ich ugryźć, a byłoby to świetne rozwiązanie.

[sesef]

Zainteresuj się testem Millera-Rabina, i pokombinuj jednak z tym GMP albo MPIR bo te biblioteki kompilowane na konkretną platformę będą szybsze od większości rzeczy które samemu się napisze, a im większe liczby tym większą różnice widać.

Tyle, że z tego co pamiętam test ten zwraca z pewnym prawdopodobieństwem czy dana liczba jest pierwsza czy też nie, a coś takiego odpada.

http://edu.i-lo.tarnow.pl/inf/alg/001_search/0018.php
"Test Millera-Rabina daje złe wyniki (p złożona) dla co najwyżej 1/4  baz a < p. Zatem dla jednego przebiegu prawdopodobieństwo błędu wynosi 1/4. Dla n przebiegów przy różnych podstawach a prawdopodobieństwo błędu spada do (1/4)^n. Już dwadzieścia testów daje szansę 1 do 1099511627776, iż liczba złożona p zostanie potraktowana jako pierwsza."

Przy AP26 wywoływane jest tylko 1 raz i starcza, ale jak chcesz mieć pewność to możesz sobie ustawić parametr funkcji zamiast na 1 to na 5 albo 10 i prawdopodobieństwo jest już sporo mniejsze, poza tym dla liczb, które zostaną uznane za złożone, można zastosować inny algorytm (nawet jak będzie powolny to raz na kilkadziesiąt mld wywołań nie będzie powodował problemów)

[Rysiu]

Ja potrzebuję całkowitej pewnościczy dana liczba jest pierwsza. Co z tego, że tutaj szansa na błąd będzie wynosić 1 do 1099511627776 skoro takich testów będzie się wykonywało ilościowo o rzędy wielkości więcej i bardzo możliwe, że gdzieś jakiś bubel się trafi. Wtedy wszystko leciałoby do kosza.

Tutaj nawet prawdopodobieństwo błędu 1/n gdzie n jest dowolnie wielką liczbą nie będzie zaakceptowane.

Można byłoby faktycznie wkoptować tego Millera-Rabina, a potem jeżeli on stwierdzi, że liczba jest pierwsza to upewniać się dodatkowym testem ale to bankowo wyjdzie wolniej niż normalnie deterministycznie.

[sesef]

Można byłoby faktycznie wkoptować tego Millera-Rabina, a potem jeżeli on stwierdzi, że liczba jest pierwsza to upewniać się dodatkowym testem ale to bankowo wyjdzie wolniej niż normalnie deterministycznie.

Tylko, że test Millera-Rabina będzie szybszy od każdego testu deterministycznego przy 2-krotnym sprawdzeniu liczby masz prawdopodobieństwo 0.0625 więc jak trafi się jakaś liczba złożona to zawsze można ja sprawdzić deterministycznie. Nie ma sensu pchać testu deterministycznego na wszystkie liczby skoro w 99% przypadków sprawdzi się test Rabina-Millera czy jakiś inny.

[Rysiu]

Wydaje mi się, że w praktyce tak różowo nie będzie. Chyba jednak warto spróbować tymbardziej, że implementacja takie rozwiązania zajmie dosłownie chwilę.

Jednak największą barierą jest ta precyzja  ???

Dostałem nowy serwer: IBM xSeries. Nie jest to może najnowsze cacko ale do replikacji bazy musi wystarczyć.

Już drugi dzień motałem się jak zainstalować na tym czymś system. Zmarnowałem chyba z 10 płyt CD bo próbowałem  zapodać tam jakąś dystrybucję Ubuntu Server. Instalowałem wszystkie kolejno od 7 przez 8.04 LTS i 9.04 do 9.10 ale wszystkie się sypały. Zrozpaczony już nawet chciałem zainstalować jakąś Desktopową wersję ale co się okazało też żadna nie chciała przejść. To jeden błąd przy instalacji [jakiś dziwny ze sprzętem - brak kompatybilności?] to drugi. Na 9.04 już się nawet zainstalował ale nic więcej bo podczas startu miał jakieś problemy z montowaniem dysków SCSI. W Internecie wyczytałem tylko, że to jakiś bug i potrafi się sypać gdy pod maską mamy jakieś kontrolery dysków z kosmosu.

Zassałem czystego debiana netinstall [150 MB] zainstalowałem i co się okazało działa  %) Nie mam pojęcia co tam panowie od Ubuntu sknocili ale szkoda słów.

Do tego w domowym PC padł mi się dysk Maxtor 60 GB. Można powiedzieć, że działał nonstop 9 lat także chyba swoje zrobił. Na szczęście dwa dni temu przeniosłem wszystkie dane i gruntowanie go sformatowałem [przypadek?]. Dziad uruchamia się normalne - słychać jak startuje i wirują dyski ale kontroler jego nie widzi. Także teraz siedzę tylko [brak jakiegoś "ludzkiego" dysku do desktopa] na ebook'u ASUS Eee PC  %) %)

[TJM]

Ubuntu ma niestety sporo niedoróbek. To chyba bardziej system 'dla mas' na typowy sprzęt, niż na serwery gdzie często siedzi jakiś bardziej egzotyczny hardware. Sam się o tym przekonałem wojując ostatnio z kompem który miał kilka kontrolerów HDD - najbardziej rozbawiło mnie to, że Ubuntu 9.04 się odpalało z dysku który później znikał i za chiny nie szło go już w żaden sposób podmontować  :D
Maszyna do replikacji nie musi być potężna - wystarcza byle słabizna, ja nawet zrezygnowałem z osobnej jakiś czas temu (względy ekonomiczne - koszt prądu) i mam po prostu dwa serwery mysql na tej samej maszynie, drugi ma swój własny dysk tylko na potrzeby backupu.

[Rysiu]

Ze słabych to ja miałem tylko jakieś AMD 350 MHz i podobne do tego kiedyś próbowałem postawić tam system ale poddałem się  %) [coś nie tak z hardware].

Muszę jednak powiedzieć, że różnica między serwerami "składakami", a markowymi maszynami jest wielka. Przynajmniej pod względem jakości wykonania i samego projektu  :ph34r:

Nawet na przednim panelu mam wyświetlacz z informacjami o statusie maszyny, a obudowę zdejmuję jednym przyciskiem. Małe a cieszy.

[Troll81]

bo to jest serwe przewidziany dla admina który nie ma czasu się pierdzielić ze sprzętem jak serwer leży... :D

[TJM]

Ja mam serwer w takiej rozbieranej obudowie desktop od jakiegoś Fujitsu-Siemensa. Z wierzchu wygląda jak kawałek śmiecia, zwłaszcza że jest niezbyt nowa - kupiłem na allegro za 20zł od gościa który miał tego tony. Jednak rozbierana po prostu bajecznie - przez naciśnięcie w dół i podniesienie do góry - otwiera się zatrzask i cała góra już zdjęta. Wszystkie karty mocowane plastikowymi zaciskami - pstryk i karta włożona/wyjęta bez żadnych śrubek. Koszyki na hdd 3.5 cala wyciągany - wystarczy odpiąc kable i można dyski wyjąć. Drugi koszyk na urządzenia 5,25 i dodatkowe 3,5 cala z zatrzaskami. Oryginalnie był też panel z jakimiś przyciskami i wyświetlaniem stanu niektórych podzespołów, ale jako że działa to jedynie z płytami Fujitsu-Siemens (dodatkowe złącze) amputowałem go uzyskując dodatkowe miejsce na dysk.
Oprócz tego wentylacja jest super - niejedna buda za kilkaset zł pewnie nie ma lepszej. Praktycznie starcza wiatrak w zasilaczu do chłodzenia wszystkiego.

[Troll81]

Dlatego ja pobawię się z tą obudową SUNa :D

[Rysiu]

U mnie to tylko skargi słyszę, że nowy nabytek jest lekko mówiąc "nie cichy". Pod maską jakieś tunele powietrzne, a wentylaatory które tam siedzą nie mam pojęcia ile obrotów wyrabiają. Całość oczywiście w Rack'u siedzi.

Teraz wyłączyłem jego to on nawet jak jest wyłączony to podtrzymuje coś energią. Jakieś diody mrygają... Zasilacze w kieszeniach Hot-Swap działają ale po co? Można powiedzieć, że jak jest wyłączony to pracuje tak głośno jak normalny komputer  :ph34r: %) %)

[Troll81]

Bo to z założenia ma stać w osobnym pomieszczeniu. a przynajmniej szafie....

[Rysiu]

Już sobie sprawiłem osobne pomieszczenie. Tylko teraz podczas stawiania systemu mam jego u siebie - tam jeszcze nie mam warunków [KVM, monitor] ale to kwestia czasu.

Po co jednak działają zasilacze i te cuda "mrygają" gdy jest wyłączony?

[TJM]

A cholera go wie. W normalnym kompie też masz obwody pod napięciem po wyłączeniu - zależnie od konstrukcji różnie to bywa, ale np. nierzadko pozostawiona jest pod napięciem sieciówka, żeby można było zdalnie włączyć kompa magic pakietem.
W zasilaczu od mojej obudowy F-S oprócz złącza ATX było drugie, coś podobnego jak w AT. Było tam +5V SB i oba ujemne napięcia (-5 i -12) nawet po wyłączeniu, po co - tego do dziś nie wiem. Co więcej, zasilacz ten nie był wcale włączany przez zwarcie PS-On do masy jak normalny ATX, tylko w środku miał pomocniczy zasilacz i przekaźnik sterowany właśnie z PS-On. Prawdopodobnie dzięki temu zasilany tym komputer mógł się całkowicie odciąć od sieci w razie potrzeby - być może znów dla ułatwienia życia adminowi, np. zdalne całkowite wyłączenie w razie problemów.

[Troll81]

serwy mają często z tyłu wejście na dodatkowy kabelek :D

W compaq to ILO czyli integrated lights out. Serwer padnie a ty i tak sie zalogujesz i go uruchomisz zdalnie :D fajna opcja i wiele firmowych serwów ma coś podobnego :D

[Rysiu]

Długo nic się nie działo, a ja zastanawiałem się jak obejść niedogodności.

W pełni deterministyczne sprawdzanie pierwszości olbrzymich liczb jest strasznie problematyczne. Trzeba na to starsznie dużo czasu i realnie niemożliwy jest na dzień dzisiejszy  rozkład liczb większych niż 10^20 na sumę liczb pierwszych - trzeba stosować specjalne myki.

Najprawdopobniej zdecyduję się cały test oprzeć na algorytmie Millera-Rabina, z tym, że świadkowie pierwszości 'a' nie będą generowani losowo.

Dla przykłądu jeżeli testujemy liczbę mniejszą niż 341 550 071 728 321 wystarczy przetestować pod kątem świadków 2, 3, 5, 7, 11, 13 i 17. Jeżeli liczba przejdzie wszystkie testy pozytywnie to znaczy, że jest deterministycznie pierwsza.

Gorzej wszystko wygląda gdy chcemy badać znacznie większe zakresy - dalej już mało zdołano konrektnie udowodnić.

Zhang, Z. w swoim artykule domniema, że do 10^36 w zupełności wystarczy Psi[20] ale jak łatwo można się domyślić pewnie długo nikt tego nie udowodni.

Rozkład na sumę liczb pierwszych w oparciu o takie założenia jest błyskawiczny - algorytm cachuje się kosztem rzędu log n.

O ile na dzień dzisiejszy portugalski profesor Tomás Oliveira e Silva deterministycznie dowiódł, że wszystko jest ok do ok. 10^20 to z tym engine na BOINC można dojechać chyba do 10^50.

Same założenia trzeba byłoby jakoś "na boku" weryfikować. Pisałem kilka miesięcy temu do adminów PrimeGrid z zapytaniem czy mają jakąś bazę, ze wszystkimi odkrytymi przez NIch liczbami pierwszymi i czy mogliby mi ją udostępnić ale odpowiedzi nie dostałem  %)

Aplikację mam już prawie gotową - jak już trochę liznąłem GMP to wielkość liczb nie gra roli  %)

[Peciak]

Trzymam kciuki i liczę że aplikacja będzie generować trochę dłuższe zadania

[Rysiu]

Aktualna aplikacja to nie aplikacja.

Myślę nawet czy odnośnie tego Millera-Rabina nie napisać do PrimeGrid - można byłoby pomyśleć nad jakimś podprojektem w tą stronę. Jakąś aplikację pewnie bym teraz mógł napisać, a i pisałem z J. Wróblewskim - admini tam całym wpięciem app pod platformę BOINC i administracją się zajmą. Sam niestety nie mam czasu, ani umiejętności aby na tyle frontów działać. Na wyniki takich analiz jednak zwielką chęcią bym zerknął.

[Troll81]

 :parrrty: szacun za włożoną pracę

[Rysiu]

Jutro [lub w weekend] może pokażę kod to sprawdzicie wydajność.

[Rysiu]

Tutaj można znależć kod: http://s2.goldbach.pl/file/GSCE-SV-2.0.0.cpp

Chyba nie ma sensu abym dodawał także bin'y - jak skompilowałem u siebie na Linuxie app to na innych kompach nie chciało działać - trzeba było oddzielnie na nich kompilować  %)

Na Windowsie pewnie nie byłoby takiego problemu ale niestety sam Windows'a nie posiadam i nie mogę takowej gotowej app załączyć.

Mam nadzieję, że sesef jakoś to skompiluje  %)

Całość działa niebotycznie szybciej [a jeszcze można troszkę wydusić] i nie ma już "większego" limitu co do wielkości rozkładanych liczb.

U siebie nie mam co testować jak szybko to idzie [stary trump i na dodatek zamulony]. W wolnym czasie sprawdzę jak idzie to na S3 [dopiero jak pisałem post o tym pomyślałem].

Przydałoby ustalić jak duże mają być badane zakresy. Jak ktoś będzie testował szybkość to bez wypisywania wyników na ekran [zakomentowane PRINTF-RESULT] - to trochę spowalnia. Zakresy tak jakoś powyżej 10^20 i trzeba obadać jak daleko można dojechać w czasie wykonywania się takiej jednej próbki [kilku godzin?].

Kod oczywiście jeszcze nie gotowy ale testować można, a nawet trzeba  %)

[Peciak]

Chciałbym pomóc ale kompletnie nic nie zrozumiałem. Jeżeli mam coś potestować coś na mojej maszynie to proszę o łopatologiczne instrukcje co mam zrobić.

[Rysiu]

A jaki system?

[Peciak]

Vista 64
procek Phenom II 965BE @3,7
karta 5850

[sesef]

Jutro jak wrócę z uczelni to postaram się to skompilować. Jak na razie od 2 dni walczę z dnetką i chyba udało mi się pozbyć tych niekończących się  WU.

[emik]

linux 64bity + procek C2D = z jakimi flagami kompilować? (proszę o podanie całej składni) :parrrty:

[Rysiu]

Nie wiem jak wygląda to z flagami -O1/2/3 - u mnie coś ich nie łapało  %)

Wystarczy

gcc -c GSCE-SV-2.0.0.cpp

i

gcc -o GSCE-SV-2.0.0 -march=nocona GSCE-SV-2.0.0.o -lgmp

To ponoć jakoś optymalizuje pod 64-bit ale za bardzo nie testowałem różnych flag.

Musisz mieć bibliotekę GMP i trochę innych [w sumie standardowych].

[emik]

Kod [Zaznacz] Rozwiń


emik@suse:~/Pulpit/gcc> gcc -c GSCE-SV-2.0.0.cpp
GSCE-SV-2.0.0.cpp:35:15: warning: missing whitespace after the macro name
GSCE-SV-2.0.0.cpp:543:34: warning: extra tokens at end of #ifdef directive
emik@suse:~/Pulpit/gcc>


[Rysiu]

Te worningi nic nie specjalnego oznaczają

Po pierwszych kalkulajach wychodzi na to, że zadania mogą obejmować sprawdzenie zakresu 250.000.000 liczb w ciągu ok. 10h na przeciętnym procesorze.

[sesef]

Binarka bez szczególnych optymalizacji pod x64 i x86

Z wypisanem na ekran
www.sesef.pl/pliki/Release.zip

Bez wypisywania na ekran
www.sesef.pl/pliki/Release2.rar

A i nie rozumiem sensu pisania tego testu millera-rabina skoro taką samą funkcje masz w GMP, która najpewniej jest szybsza.

[Rysiu]

A i nie rozumiem sensu pisania tego testu millera-rabina skoro taką samą funkcje masz w GMP, która najpewniej jest szybsza.

Pewnie że jest tylko, że sprawdza dla losowych świadków. Trzeba byłoby grzebać w bibliotekach i ją przerabiać. Może się tak zrobi, ale trzeba to wygrzebać.

Poprawiony link do drugiego archiwum: (domyślam się, że zawartość dobra ale głowy nie daję)

http://www.sesef.pl/pliki/Release2.rar

[Rysiu]

Co ciekawsze na uczelni próbowałem odpalić app. Myślałem, że na Windows'ie nie będzie żadnych problemów ale jednak czepia się, że bibliotek jemu brakuje.

[sesef]

Przekompilowałem binarkę tak, żeby nie wymagało posiadania redistributów (stąd ten błąd)

www.sesef.pl/pliki/gol.zip