BOINC@Poland

No to super !!!  :respect: :respect: :respect: :respect: :respect: :respect: :respect: :respect: :respect: :respect:

Co do optymalizacji, to na podstawie moich wyobrażeń o GPU, przypuszczam, że największym problemem nie będzie optymalizacja samych obliczeń, ale organizacji wątków.

Na CPU program idzie z grubsza tak:
wchodzi w sito, najczęściej dosyć szybko zmienna sito staje się zerem, i przechodzi do następnej pętli. Bardzo rzadko przechodzi przez sito i testuje pierwszość.

Przy jednym wątku nie ma znaczenia, że za każdym razem wchodzimy w sito na inną głębokość, a przez całe sito przechodzimy tylko sporadycznie. Kiedy projektowałem algorytm, nie śniło mi się o obliczeniach na GPU.

Jeśli teraz bezpośrednio przeniesiemy ten algorytm na GPU, to jawi mi się taki scenariusz:

Wątki są wykonywane w paczkach po, bodajże, 16 wątków. Jeśli teraz te 16 wątków wejdzie w sito, to często zdarzy się, że 15 wątków się zakończy (zmienna sito się wyzeruje), ale 16-ty wątek będzie szedł głębiej w sito i może nawet dojdzie do testowania pierwszości. No i jeśli ja dobrze rozumiem działanie GPU, to te 15 wątków będzie czekało bezczynnie aż ten 16-ty skończy swoją robotę.

Prawdopodobnie to będzie wymagało jakiejś reorganizacji. Chociaż oczywiście powyższy czarny scenariusz nie oznacza, że program będzie chodził z 1/16 prędkości - w praktyce często wątki nie będą miały dramatycznej różnicy czasu spędzonego w sicie, ale prognozowanie na ile jest to problemem, to trochę wróżenie z fusów.

Ponadto nie wiem, jak wygląda sprawa operacji 64-bitowych, bo zdaje się, że w GPU większość jednostek wykonuje tylko operacje 32-bitowe, a tych 64-bitowych jest niewiele.

Jaką masz platformę testową? Czy zainstalowanie wszystkiego sprawiało dużo bólu, czy poszło raczej bezproblemowo?

W tej chwili nie mam pod ręką środków do wyliczenia procentowo, ile liczb odpada. Jest to sporo (chyba więcej niż połowa), ale nie należy się tym sugerować, bo wykonanie wielu operacji typu n%x też jest kosztowne i wiem z doświadczenia, że prędkość programu prawie nie zależała od liczby ifów na tym etapie (więcej ifów to mniej testowania pierwszości, ale też i więcej grzebania się w ifach, które to grzebanie w ifach częstokroć i tak kończy się testowaniem pierwszości). Ponadto program stosunkowo rzadko przechodzi przez sito.

Liczba n59 jest zawsze mniejsza od 2^48, natomiast samo n może być znacznie większe (2^57 lub w przyszłości nawet więcej) - stąd może się brać niepoprawność dzielenia.

Pominięcie ifów nie jest żadną zbrodnią, więc możesz to zrobić. Program może zwolnić, ale nieznacznie. Biorąc pod uwagę, że musiałbyś robić karkołomne sztuki dla poprawnego zaimplementowania n%x, to może teoretycznie być nawet opłacalne - ale raczej jest bez większego znaczenia.

Pamiętaj jednak, że program będzie wówczas drukował więcej ciągów, więc się nie zdziw, jeżeli plik z wynikami testowymi będzie inny (ma prawo być tylko większy - wszystkie dotychczas znajdowane ciągi muszą się pojawić). Program będzie równoważny w zakresie poszukiwań AP26, natomiast usuniecie ifów może mieć skutek uboczny w postaci nieco większej liczby znajdowanych AP25, AP24, ...

ksysju jest pierwszym liczydłowym, który znalazł już 3 nowe AP24  :respect: :respect: :respect:
Gratulacje !!!

Do dnia dzisiejszego po 2 nowe AP24 na swoim koncie mają:
stachu @ fiddex
SG Arsenic (SETI.Germany)
mfl0p ([H]ard|OCP)
[XTBA>TSA] IvanleFou (Xtrem Team Boinc Addicted)

mindc ma wyraźnego pecha - pomimo ponad 560K przeliczonych próbek ma na koncie tylko jedno nowe AP24  :(

To zaskakujące, że tak proste elementy, jak ta pętla, nie przenoszą się bezpośrednio na GPU.

Najważniejsze, żeby program produkował poprawne wyniki.

Rozumiem, że CPU i GPU dają inne rezultaty.

No to trzeba wyśledzić, gdzie obliczenia CPU i GPU się rozjeżdżają.

Na końcu getMagic trzeba wydrukować *pMagic oraz *pShift

Na końcu mulmod trzeba wydrukować r

Trzeba porównać wyniki drukowane przez CPU i GPU.

getMagic i mulmod nie mają prawa zwracać innych wyników na GPU niż na CPU - obliczenia muszą przebiegać identycznie.

Dla każdej testowanej liczby pierwszej będzie drukowanych kilkadziesiąt liczb, więc trzeba wybrać jedną liczbę, dla której test pierwszości na CPU i GPU wypada inaczej, i uruchomić śledzenie dla tej liczby.

W tym samym katalogu wersja trzecia - powinna być nieco szybsza.

W katalogu
http://www.math.uni.wroc.pl/~jwr/cuda/PrimeQ_gen/
jest druga wersja PrimeQ_gen31 wraz z programem testującym prędkość.

Jeśli wyśledzisz, że test.c oraz test31v2.c produkują inne wyniki, daj znać - dla wszelkich sensownych danych powinny działać tak samo.

Na oko działają tak samo szybko - superdokładnych testów nie robiłem. W argumencie podajemy liczbę parzystą.

Teoretycznie mogą być wyrazy mniejsze od 2^32, ale nie jest znany żaden AP21 lub dłuższy o wyrazie mniejszym niż 2^32.

Jednak boję się, że mogą być takie wredne d>2^32, dla których to dzielenie przez floaty da zły wynik. Nie ma też specjalnej kontroli nad dzieleniem przez anc.

Chyba najbezpieczniej będzie dopracować wersję z PrimeQ-gen31.

Jak będę miał chwilę czasu, to spróbuję to zrobić i pomyślę o jakichś optymalizacjach.

Cytat: sesef w 04 Wrzesień 2009, 01:12
Sprawdziłem jedną rzecz, zamieniłem to dzielenie całkowite na dzielenie zmiennoprzecinkowe

float q1f = (float)two63 / (float)anc;
float q2f = (float)two63 / (float)d;

Wyniki wystarczy zaokrąglić w dół (tyle GPU potrafi na typach float, więc nie będzie problemów) i jest taki sam jak przy dzieleniach całkowitych.

Ale tu jest wredna pluskiewka. Otóż liczby anc i d na ogół są dość losowe, czyli duże. Ilorazy są stosunkowo małe, więc floaty są zazwyczaj wystarczająco dokładne, aby pamiętać zaokrąglenia (tych małych liczb) w odpowiednia stronę. Boję się, że jeśli anc i d będą małe, wyniki mogą być dość losowe. Będzie też problem, gdy ilorazy będą bardzo bliskie liczbie całkowitej - float nie spamięta wystarczającej dokładności, aby zaokrąglić w odpowiednią stronę. To się zdarzy niesłychanie rzadko, niemniej jednak jest to pluskwa, bo program nie zadziała poprawnie dla wszystkich możliwych danych. Spróbuj wypisać takim programem liczby pierwsze z przedziału 100-200. Boję się, że nie będzie żadnej, bo obliczenia się losowo zwichrują.

Iloraz two63/d może w tej metodzie być błędnie liczony zarówno dla małych d, jak i dla takich d, że two63/d jest prawie całkowite i małe, np. dla d około two63/3, two63/5.

Ponadto nie wykluczam, że PrimeQ-gen31 będzie działać szybciej - dla testów prędkości trzeba zwiększyć przedział testowy, a znalezionych liczb pierwszych nie wypisywać, tylko zliczać. Chociaż najprawdopodobniej różnica prędkości nie będzie zauważalna, bo getMagic zabiera stosunkowo mało czasu w stosunku do całego testu pierwszości.

PrimeQ-gen31 będzie działał dla wszystkich zakresów, jeżeli w linijce:


   } while (p<=122);
   
// instead of 122 take 62+number_of_significant_bits_of_d


dokona się odpowiedniej korekty. W tym celu należy wyznaczyć liczbę bity taką, że
2^(bity-1) < d < 2^bity
a następnie zamiast 122 umieścić 62+bity

Ja na szybko robiłem wersję, która miała sprawdzić, czy to w ogóle pójdzie, więc wpisałem ręcznie liczbę odpowiednią do danych testowych. Liczby w moim teście były 60-bitowe.

Liczba, którą podajesz, jest 56-bitowa, więc dla celu testów możesz zmienić 122 na 118. Ale na poważnie, to trzeba w programie bity wyliczyć w zależności od d.

Sito i PrimeQ to są dwie dość niezależne rzeczy, więc można przetestować na grafie samo PrimeQ - do takiego testu nadaje się test31.c.

Co do sita, to ja nad tym jeszcze poważnie nie myślałem, ale być może da się je inaczej zorganizować.

Jeśli chodzi o cytowanego przez Ciebie if-a, to z grubsza raz na 7500^n pętli będzie prawdziwy n+1 razy.

Lub inaczej:

Pętli w każdym K powinno być ok. 47,000,000.

2 x zdarzy się ok. 18,000 razy w każdej próbce (ok. 6,000 razy w każdym K).

3 x zdarzy się średnio 2.5 raza w każdej próbce (mniej niż raz w każdym K).

4 x zdarzy się średnio raz na 3,000 próbek.

5 x zdarzy się średnio raz na 22,500,000 próbek - zakładając, że AP26 będzie trwać np. 30,000,000 próbek, 5 x w jednej pętli trafi się może raz albo dwa, a szanse na wystąpienie 6x są mniejsze niż 0.02%, czyli na 99.98% 6x się nigdy nie pojawi.

Liczby, które podaję powyżej, mogą nie być dokładne, ale powinny mieć właściwy rząd wielkości - jeśli gdzieś nie popełniłem błędu w obliczeniach, to raczej nie mylę się więcej niż o czynnik 2. Jeśli zliczysz wszystkie pętle dla testowego K oraz pętle z 2x, będziesz wiedział, w którą stronę i o ile się mylę.

W pliku

http://www.math.uni.wroc.pl/~jwr/cuda/PrimeQ-2009-09-03.zip

są 2 testy.
test.c jest do uruchomienia na CPU jako wzorzec - powinien drukować to samo, co test31.c:


1 1000000000000000003
2 1000000000000000009
3 1000000000000000031
4 1000000000000000079
5 1000000000000000177
6 1000000000000000183
7 1000000000000000201
8 1000000000000000283
9 1000000000000000381
10 1000000000000000387
11 1000000000000000507
12 1000000000000000523
13 1000000000000000583
14 1000000000000000603
15 1000000000000000619
16 1000000000000000621
17 1000000000000000799
18 1000000000000000841
19 1000000000000000861
20 1000000000000000877
21 1000000000000000913
22 1000000000000000931
23 1000000000000000997
Naciśnij dowolny klawisz, aby kontynuować . . .


Czy wygląda na to, że da radę bez większego bólu uruchomić test31.c na grafie?

Dzielenie two63/d wobec two63=2^31 jest de facto 32-bitowe (dla d>2^31 jest zero, a dla d<2^31 wykonujemy dzielenie 32-bitowe).

Cytat: sesef w 03 Wrzesień 2009, 11:54
Widziałem ta procedurę największy problem to pozbycie się uint64_t q1 = two63/anc; i uint64_t q2 = two63/d; z getMagic.

To wytłumacz mi, w czym problem. Czy na grafie nie ma dzielenia uint64 ? To jakie operacje są dostępne?

Geoff Reynolds umieścił w
http://www.geocities.com/g_w_reynolds/AP26/PrimeQ_gen.zip
procedurę testującą pierwszość przy wykorzystaniu jedynie arytmetyki 64-bitowej. Wygląda, że jest to znacznie lepsze rozwiązanie od tego, które ja proponowałem.

Być może da się to jakoś wsadzić na grafę i tam testować pierwszość.

Poprawności procedury Geoffa nie sprawdzałem, milcząco zakładam, że jest OK.

Myślę, że w razie potrzeby można ją trochę przyspieszyć.

Niezależnie od sposobu liczenia powinno wyjść
195008071104087968748069929440865585042

Natomiast obawiam się, że proponowana przeze mnie procedura testowania pierwszości nie jest najlepsza  :shame:
Geoff Reynolds umieścił w
http://www.geocities.com/g_w_reynolds/AP26/PrimeQ_gen.zip
procedurę testującą pierwszość przy wykorzystaniu jedynie arytmetyki 64-bitowej.

AP26 ma się z założenia mieścić (lub prawie mieścić) z używaną pamięcią w pamięci podręcznej procesora.

Teoretycznie można sobie wyobrazić, że nawet na wielordzeniowym procku o cache wspólnym dla kilku rdzeni, jeden wątek pójdzie na cache, a dwa wątki się przymulą sięgając do RAM-u. To trochę tak, jak gdyby na kompie z 2GB RAM puszczać program używający 1.5 GB. Jeden wątek pójdzie gładko, a dwa się zamulą wchodząc z pamięcią na dysk - tego akurat łatwo doświadczyć.

To jest tylko teoria. Nie wiem, czy ktoś takie zjawisko był w stanie zaobserwować w praktyce w odniesieniu do styku cache/RAM.

Same dane liczbowe używane przez AP26 zajmują sto parędziesiąt kB. Nie wiem, ile zajmuje cała aplikacja BOINC-owa.

Cytat: sesef w 24 Lipiec 2009, 20:09
Może głupie pytanie, ale pomoże uniknąć potem szukania głupich błędów.

W Fun96 te 2^96 jest traktowane jako

2^96 = 79 228 162 514 264 337 593 543 950 336
2^96 - 1 =79 228 162 514 264 337 593 543 950 335 (tyle wejdzie maksymalnie wejdzie w zmienną)

Ja jak wiadomo muszę zastosować wersje 2^96-1 bo inaczej dojdzie do przepełnienia i teraz nie wiem czy na końcu dodawać 1 po tym odejmowaniu czy nie.

I jeszcze mam pytanie o Mul192High tutaj mam pomnożyć te górne 96 bit czy wykonać mnożenie 192bit*192bit i dopiero z wyniku takiego mnożenia wyciąć te 96bit

Fun96(n) ma zwrócić 2^96-2n. Można obliczyć (2^96-1)-2n+1. Można też obliczyć 2*(2^95-n).
Liczbę (2^96-1)-x można obliczyć zmieniając wszystkie 96 bitów liczby x na przeciwne.

Mul192High(a,b) ma zwrócić 192 górne bity 384-bitowego iloczynu a*b.

Cytat: mindc w 23 Lipiec 2009, 18:20
AP26 tasks
Completed tests   369869
Found of length 20   594
Found of length 21   155
Found of length 22   34
Found of length 23   7
Found of length 24   2

hmmm... wygląda na to że mam dwa AP24  :attack:

Oczywiście, że masz 2 AP24, ale tylko jeden nowy, a jeden znany wcześniej, znaleziony przez Ciebie w początkowej fazie poszukiwań.

Szczegółowa lista AP23 i dłuższych jest tutaj:
http://www.primegrid.com/forum_thread.php?id=1182

Przy okazji: Gratuluję przekroczenia 5M kredytów w AP26.

Teraz robią na przemian paczki po 100,000 próbek z shift 0 i 100,000 z shift 64.

Próbki z shift 0 mają K o ok. 10,000,000 większe od tych z shift 64.

No więc jak w puli jest kilkaset tysięcy próbek, to są wymieszane oba typy.

Z tym 3-cim miejscem też łatwo nie będzie  :(

O 8.00 było 2412 próbek straty do L'Alliance Francophone, a o 11.00 było 2293 - przez 3 godziny odrobione 119, a zostało 9 godzin.

Natomiast ksysju ma 7-me na wyciągnięcie ręki (o 10.45 jedna próbka straty do SG-Booster, o 11.00 26 próbek).

Cytat: Jarek Wróblewski w 18 Lipiec 2009, 15:29
To jest pierwsze AP24 znalezione przez kompa z systemem Darwin 9.7.0

I to jakaś kobitka znalazła.
http://www.primegrid.com/forum_thread.php?id=1246&nowrap=true#17005
Miło widzieć, że panie się skutecznie włączają w poszukiwania  :) :) :)

Cytat: sesef w 21 Lipiec 2009, 20:56
Chyba coś admini się nie przegotowali, po osiągnięciu 7 mln miał być przesunięcie o 128 a ja właśnie dostałem WU 872469_872472_64 czyli przesunięcie o 64, czy w czymś to przeszkadza? i czy przy shifcie o 128 dawałoby to jakieś korzyści?

Wszystko jest OK. Do shiftu 128 jeszcze daleko - to jest dopiero 872,469 na shifcie 64. Do 7 mln jeszcze daleko.

Shift 128 pojawi się jak shift 0 dojdzie do 17 mln, a shift 64 do 7 mln. Przesunięcia shiftu są o 64.

Taka kolejność obliczeń, jaką zaproponowałem, zwiększa szanse szybszego znalezienia AP26 - zaczynamy od obszarów, gdzie ta szansa jest największa.

Tak, oni na PrimeGridzie pisali wyraźnie, że ten zegar bierze czas z lokalnego komputera.

Na stronie głównej mają obok listy z liczbą dostępnych próbek ichni UTC time, tylko trzeba ręcznie odświeżać stronę w przeglądarce.

Ja nie podejmuję się wyrokować jak jest lepiej, muszę jednak przyznać się, że czasami celowo popełniam drobne błędy, jeśli dzięki temu tekst jest bardziej zrozumiały lub brzmi zgrabniej.

Nagminnie stawiam przecinki tam, gdzie być ich w zasadzie nie powinno, ale ich umieszczenie ułatwia czytanie długiego zdania.

Używam określenia w stylu Dana jest liczba całkowita n>4. A przecież n>4 to nie jest liczba, tylko nierówność. Poprawnie byłoby Dana jest liczba całkowita n spełniająca nierówność n>4. Ale za to mniej zgrabnie.

Zwrot projekt miesiąca sierpnia podkreśla, że mamy do czynienia z cykliczną comiesięczną zabawą. Osobie niezorientowanej, o co chodzi, może dać dokładniejszy opis niż projekt sierpnia. Szczerze mówiąc, nie umiem sobie wyobrazić jak przeciętny odbiorca newslettera odbierze jeden i drugi zwrot, nie wiem więc czy w tym wypadku celowe użycie niepoprawnej formy zostałoby zrekompensowane lepszą zrozumiałością.

Cytat: Troll81 w 20 Lipiec 2009, 15:17
podwójne cyferki poprawione. Wynik zostawiam taki jaki jest bo ostatnio wysyp i co godzinę będę musiał poprawiać :D

A podwójne cyferki po stronie Reszty Świata okazały się prorocze, bo już jest 6:10  XD

W każdym razie Reszcie Świata ostatnio sypnęło nowymi AP24.
Jako kibic BOINC@Poland się smucę :(
Jako autor programu AP26 zacieram ręce :)

Wyniki meczu wyglądają mało optymistycznie (jedna cyferka dla B@P, dwie cyferki dla RŚ, np. ja widzę wynik 6:08).

Ponadto znaleziono kolejny AP24, więc wynik ulegnie zmianie (nie wiem, w którą stronę). Nie ma co czekać na wyjaśnienie z rozsyłaniem, ale po prostu przed rozesłaniem sprawdzić, czy już wiadomo.

Ja sobie wyobrażałem, że w jednym momencie będzie liczone tylko jedno K.

To wymaga przepisania sita, ale myślę, że z grubsza wiem jak to zrobić.
Funkcja void SearchAP26(int K, int SHIFT) daje się w naturalny sposób rozbić na praktycznie dowolną liczbę niezależnych funkcji (ta sama funkcja z różnymi parametrami), więc nawet przy jednym K można podzielić obliczenia na tysiące wątków.

Żeby to jednak zrobić, trzeba rozumieć całość algorytmu, no więc to robota dla mnie.

Cytat: sesef w 18 Lipiec 2009, 20:05
Liczba zmiennopozycyjna to to samo co liczba zmiennoprzecinkowa?

Ja u Kernighana, Ritchie, Język ANSI C, mam float i double opisane jako typy zmiennopozycyjne. Jak zwał tak zwał, chyba nic innego tu nie można rozumieć.

Cytat: sesef w 18 Lipiec 2009, 20:05
Działanie tego typu 9223372028264841216./p.hi owszem da się wykonać tyko teraz powstaje problem jak ma być to dokładne.

Będzie tak dokładne jak będzie. Cały algorytm obliczania odwrotności składa się z dwóch części:
1. Obliczyć odwrotność z jakąś dokładnością.
2. Zastosować wzorki zwiększające dokładność.

Ja nie żądam jakiejś konkretnej dokładności, ale muszę wiedzieć, z jaką dokładnością mamy do czynienia, bo od tego zależą wzorki zwiększające dokładność.

Pisząc program oparłem się na swojej wyobraźni o dostępnych operacjach i założyłem, że dzielenie 32-bitowe da przynajmniej 30 bitów precyzji.

Jeżeli rzeczywista precyzja będzie inna, to trzeba tylko wiedzieć jaka i program można banalnie poprawić.

Ja nie wiem jaką dokładność ma float, to nawet może zależeć od systemu. Jeśli testy pokażą, że mniejszą niż założyłem, to się zrobi proste poprawki, które to uwzględnią.

A w pliku PsPrimeQ.h jest algorytm testowania pierwszości.

Najważniejsze, żeby to w ogóle poszło i dawało poprawne rezultaty. Potem sobie można będzie optymalizować kawałek po kawałku.

Cytat: sesef w 18 Lipiec 2009, 18:49
Tak na szybko spojrzałem, problemów większych nie powinno być po za jednym.

result.hi.hi=(uint32_t)(9223372028264841216/p.hi);

9223372028264841216/p.hi da rade to jakoś zamienić czy muszę robić dzielenie 64 bit?

Cały dowcip polega właśnie na tym, żeby uniknąć pisania własnego dzielenia. Tu chcemy wykonać dzielenie zmiennopozycyjne z precyzją 32 bitową.

Ja napisałem "9223372028264841216." (z kropką na końcu) i mam nadzieję, że to zostanie wykonane jako działanie zmiennopozycyjne. Chodzi o to, że najpierw trzeba wyliczyć odwrotność p z dokładnością, powiedzmy ok. 30 bitów (ważne, żeby było zaokrąglane w dół).

No więc liczbę 2^63-2^33=9223372028264841216 trzeba zapisać w postaci zmiennopozycyjnej z dokładnością 32 bitów. Mam nadzieję, że napis "9223372028264841216." da taki właśnie efekt, ale może można to uzyskać inaczej.

Tę liczbę należy podzielić przez p.hi (górne 32 bity p) - w dzieleniu wobec zmiennopozycyjnej dzielnej to powinno być automatycznie zamienione na 32-bitową liczbę zmiennopozycyjną.

Następnie zmiennopozycyjny iloraz, który tu jest mniejszy od 2^32, powinien być zamieniony na liczbę całkowitą i wpisany do result.hi.hi (zaokrąglenie jest nieistotne - mieści się w granicach błędu).

Cytat: sesef w 18 Lipiec 2009, 18:49
I nie bardzo rozumiem działanie Fun96(Int96 n); ma policzyć 2^96 - 2n; ?

Tak, taki dziwoląg się pojawia we wzorze. Przy tym liczba n będzie ciut poniżej 2^95, zatem 2n będzie ciut poniżej 2^96. Tu można w liczbie 2n zmienić wszystkie 96 bitów na przeciwne i dodać 1.

Cytat: sesef w 11 Lipiec 2009, 00:43
Co do mnożenia na chwilę obecną wygląda to tak http://www.ee.pw.edu.pl/~jaworows/AP/BigInt.zip myślę że da radę jakoś to jeszcze przyspieszyć.

W tym samym stylu postarałem się napisać algorytm wyznaczania odwrotności. Okazuje się, że to jednak wymaga posługiwania się po drodze liczbami 192-bitowymi.

Algorytm obliczania odwrotności jest w pliku Inv.h w katalogu http://www.math.uni.wroc.pl/~jwr/AP26/GPU/

Jeśli dopiszesz brakujące makra, funkcja Inv powinna liczyć odwrotność z właściwą precyzją.

To jest chyba najbardziej upierdliwy kawałek procedury testowania pierwszości, dalej powinno być z górki  :)

To jest pierwsze AP24 znalezione przez kompa z systemem Darwin 9.7.0
http://www.primegrid.com/show_host_detail.php?hostid=115782

Cytat: Pigu w 18 Lipiec 2009, 10:47
jak mniemam celem tego projektu jest obalenie twierdzenia poprzez znalezienie pierwszej liczby która go nie spełnia?

Eeehmm... Wątpię. Każdy, kto się trochę poważniej tym problemem pobawił, nabiera przekonania, że twierdzenie jest prawdziwe, aczkolwiek beznadziejnie trudne do udowodnienia. Trudno więc oczekiwać znalezienia kontrprzykładu, bo takowy najprawdopodobniej nie istnieje.

Myślę, że bezpośrednim celem projektu jest znajdywanie rekordowych liczb - takich, od których trzeba wykonać możliwie dużo (w stosunku do rozmiaru liczby) iteracji, aby dojść do liczby 1.

Celem może też być osiąganie wyników w stylu: Hipoteza Collatza jest prawdziwa dla liczb mniejszych od ***.

Cytat: Troll81 w 12 Lipiec 2009, 13:36
myślę że niegłupim pomysłem byłoby przyjrzenie się temu pomysłowi

http://www.boincatpoland.org/wiki/12_lipca_2009_Pojawi%C5%82_si%C4%99_nowy_projekt_wykorzystuj%C4%85cy_CUDA

Z punktu widzenia programowania problem Collatza to pikuś. W tym problemie iteruje się operację:
x -> (3x+1)/2
Jedyne, co trzeba zaprogramować, to mnożenie przez 3, dodawanie 1 i dzielenie przez 2.

mfl0p, więc w meczu remis 6:6.

A pojawianie się AP24 jest losowe. Może nie być żadnego przez miesiąc lub prawie dwa, a potem kilka w ciągu tygodnia.

Cytat: sesef w 11 Lipiec 2009, 00:43

Cytat: Jarek Wróblewski w 09 Lipiec 2009, 21:06Co do remaindera, to muszę opracować algorytm wyznaczania go przy pomocy mnożenia przez odwrotność p. Ponieważ w teście pierwszości liczby p mulmod jest wykonywany z tym samym p, to p wystarczy odwrócić tylko raz.
Niby proste w założeniach, ale trzeba być ostrożnym, żeby się wszystkie bity przy zaokrągleniach układały jak trzeba, więc jest trochę żmudnej dziubaniny.

W czym takie posunięcie ma nam pomóc, i tak dzielenia się nie uniknie.

1. Dzielenie wykonamy raz, tzn. raz obliczymy 1/p, a potem 60 razy użyjemy mulmoda, który dzieleń zawierał nie będzie, ale wykorzysta 1/p.

2. Obliczenie 1/p może być łatwiejsze niż wykonanie dowolnego dzielenia. Także łatwiejsze do zaimplementowania. Postaram się rozpisać szczegółowo algorytm obliczenia 1/p z wymaganą precyzją.

Zacząłem robić luźne notatki (po angielsku, żeby obcy tez mogli poczytać) dotyczące algorytmu testowania pierwszości przy użyciu operacji 32-bitowych:
http://www.math.uni.wroc.pl/~jwr/AP26/GPU/

Cytat: Troll81 w 09 Lipiec 2009, 21:10
wynik meczu się wyrównuje

No, niestety, statystyki liczby przeliczanych obecnie próbek są nieubłagane  :(
A to w dłuższej perspektywie musi sie przełożyć na wynik meczu  :(

W/g stanu na 1 maja 2009:
1,300,274 próbek przeliczonych przez cały AP26 Search
BOINC@Poland 805,808 = 61.97%

W/g stanu na 9 lipca 2009:
2,632,259 próbek przeliczonych przez cały AP26 Search
BOINC@Poland 1,170,880 = 44.48%

Przyrost od 1 maja do 9 lipca:
1,331,985 próbek przeliczonych przez cały AP26 Search
BOINC@Poland 365,072 = 27.41%

Samo mnożenie liczb dowolnej precyzji zaimplementowałem kiedyś w oparciu o algorytm z książki Knutha.
Znajduje się ono w pliku mul.h w katalogu http://www.math.uni.wroc.pl/~jwr/cuda/

Jest ono dosyć niezdarne, bo zdaje się, że liczbę trzeba pamiętać w kawałkach 16-bitowych, które być może w pamięci komputera się nie kleją dobrze w większe kawałki - być może trzeba odwrócić kolejność wyrazów w tabeli. Ale powinno liczyć OK.

Co do remaindera, to muszę opracować algorytm wyznaczania go przy pomocy mnożenia przez odwrotność p. Ponieważ w teście pierwszości liczby p mulmod jest wykonywany z tym samym p, to p wystarczy odwrócić tylko raz.
Niby proste w założeniach, ale trzeba być ostrożnym, żeby się wszystkie bity przy zaokrągleniach układały jak trzeba, więc jest trochę żmudnej dziubaniny.

Cytat: sesef w 09 Lipiec 2009, 15:46
Mam kolejne pytanie co do samego mulmoda ile razy będzie wywoływany przy sprawdzaniu pierwszości? Wystarczy raz czy będzie go trzeba wywołać kilka/kilkanaście/kilkaset razy?

Będzie wywołany tyle razy, ile bitów ma liczba p, czyli około 60.

Oto przykładowy test pierwszości dla liczb 63-bitowych używający mulmoda i operacji na liczbach 64-bitowych:

Cytat
// zakladamy, ze p<2^63
int PSPrimeQ(unsigned long long p)
{
unsigned long long out=1;
int i;

for(i=62;i>=0;i--)
{
out=mulmod(out,out,p);
if((p>>i)&(1ULL))
{
out<<=1; // dla p>2^63 tu byloby przepelnienie, ktore w razie potrzeby mozna obejsc
if(out>=p)out-=p;
}
}
return (out==2)?1:0; // 0 oznacza liczbe zlozona, 1 liczbe pierwsza lub pseudopierwsza przy podstawie 2,
// co w praktyce jest rownowazne pierwszosci
}

Jak będziemy mieli funkcję PSPrimeQ, to do reszty (czyli sita) żadna superprecyzja nie będzie potrzebna. Zaimplementowanie powyższej funkcji to wszystko, czego trzeba, żeby na grafie testować pierwszość.

W powyższym kodzie można trochę pooptymalizować - np. kilka początkowych mnożeń (póki są małe liczby) wykonać bez mulmoda, tudzież wywalić ostatnie mnożenie (w razie potrzeby powiem jak), myślę jednak, że w pierwszej wersji liczy się prostota kodu, a nie superoptymalizacja, więc można najpierw zaimplementować powyższe jak jest, a jak będzie chodzić, to dopiero wtedy trochę podcyzelować.