Algorytm Jarka Wróblewskiego

[Jarek Wróblewski]

Ja swoje algorytmy rozwiązujące różne zagadnienia matematyczne tworzę w pewnym sensie w izolacji, tzn. trudno mi znaleźć kogoś, kto byłby skłonny ze mną w tej materii współpracować. OK, nic na to nie poradzę, pogodziłem się, że jestem tu skazany sam na siebie.

Jeśli chodzi o uruchamianie programów, to jest lepiej, ale niewiele. W ostatnim czasie współpracę zaoferował mi Raanan Chermoni oraz PrimeGrid. Poza tym jestem skazany na samotną zabawę komputerami dostępnymi w pracowniach studenckich, na których programy uruchamiam dość prymitywnie, tzn. za pomocą skryptów odpalanych ręcznie.

Czuję pewien niedosyt, że nie udało mi się wciągnąć do współpracy więcej osób, zwłaszcza z Polski.

Nie wiem na ile jest to sensowne, ale chodzi mi po głowie następujący pomysł. Na stronie
http://hjem.get2net.dk/jka/math/aprecords.htm
odnotowującej rekordy związane z postępami arytmetycznymi liczb pierwszych, jest jeszcze parę rekordów, których pobicie nie powinno być zbyt trudne. Myślę, że byłbym w stanie wyprodukować program, który dawałby spore szanse na wpisanie się na listę rekordzistów, np. Smallest AP-k with minimal start k=19,20,21,22. Gdyby było takie zainteresowanie, chętnie przekazałbym w użytkowanie taki program BOINC@Poland. Ja umiem zrobić tylko procedurę liczącą, ale nawet przy braku systemu podziału zadań można ją odpalać ręcznie umawiając się kto bierze jaki przedział parametrów. Proszę spojrzeć na
http://hjem.get2net.dk/jka/math/simultprime.htm
gdzie część wyników została uzyskana przez zorganizowane projekty. W tabeli rekordów wymieniane są: nazwisko odkrywcy (czyli właściciela komputera), nazwa projektu oraz nazwa użytego programu.

Z takich poszukiwań pewnie nie byłoby punktów w różnych klasyfikacjach, ale byłaby spora szansa na wpis do tabeli rekordów. Może w ten sposób dałoby się przyciągnąć do projektu nowych użytkowników i spopularyzować ideę tego typu poszukiwań.

Jeśli ten pomysł wydaje się sensowny, jestem gotów rozpocząć przygotowania odpowiedniego programu.

[kempler]

Czy dobrze rozumiem że byłby to program do odpalenia na pojedynczym kompie ? Czy może chciałby pan zaadoptować algorytm do BOINC ?

[jurdziol]

Raczej pan Jarek by dostarczyl tylko procedure, ktora bedzie obliczac a 'ktos' by musial przygotowac reszte, czyli oprogramowanie projektu, podzial zadan itp.

[Jarek Wróblewski]

Ja się nie znam na BOINC. Mogę dostarczyć procedurę wykonującą obliczenia. Można ją łatwo odpalać na pojedynczym kompie albo podzielić pracę na wiele maszynek.

Z całą pewnością można to zaadaptować do BOINC (w końcu PrimeGrid to zrobił z podobnym programem), ale ja tego nie umiem i nie zrobię. Żeby nie było wątpliwości, program dzieli się w łatwy sposób na niezależne segmenty, więc nie ma problemu z rozdzieleniem pracy na wiele komputerów, które nie muszą się ze sobą komunikować. Wystarczy rozdzielić pracę i zebrać wyniki.

Wyobraźmy sobie, że ma być wykonana Procedura(n) dla n=1,2,3,...,1000000.

Można na jednym kompie odpalić
for(n=1;n<=1000000;n++)Procedura(n);
albo na milionie kompów na raz odpowiednio
Procedura(1);
Procedura(2);
Procedura(3);
...
Procedura(1000000);

Napisanie Procedury to mój problem. Do Was należałoby rozdzielenie pracy i zebranie wyników.

Raczej pan Jarek by dostarczyl tylko procedure, ktora bedzie obliczac a 'ktos' by musial przygotowac reszte, czyli oprogramowanie projektu, podzial zadan itp.

Tak właśnie. Przy czym w wersji próbnej do pomyślenia jest także ręczne rozdzielanie zadań, np. widziałem, że PrimeGrid ręcznie rozdziela przedziały sita, po prostu użytkownicy na forum zgłaszają, który przedział biorą. No ale docelowo wygodniejszy pewnie byłby jakiś system - to oczywiście zależy od możliwości technicznych.

******

Po zastanowieniu: wydaje mi się wręcz, że pierwszy tego typu program powinien być rozdzielany ręcznie przez umawianie się co do przedziałów obliczeń np. na forum w stosunkowo wąskim gronie testerów. Dopiero potem można ewentualnie myśleć o czymś poważniejszym. Pytanie podstawowe: czy jesteście zainteresowani taką zabawą?

[kempler]

Ja jestem zainteresowany. Myślę że po weekendzie odzew może być większy.

[emik]

ja również wspomogę moim komputerkiem

[kempler]

Może w dłuższej perspektywie wykluje się z tego jakiś projekt BOINC. Taka moja nadzieja, marzenie...

[Machloj]

hem - to i ja zapuszczę to cuś na swoim quadzie - jeśli w ten sposób nazwisko polskiego naukowca zostanie rozreklamowane to ja jestem za!  ;)
może TJM by się tym pobawił i zrobił z tego projekt BOINCowy - można by wtedy zamiast na skb@p pozbierać na serwer i do boju (może nawet Artur się wtedy dorzuci :D)

[Jarek Wróblewski]

Pierwsze zadanko znajduje się w katalogu
http://www.math.uni.wroc.pl/~jwr/BaP/
plik AP19.ZIP

[Machloj]

ok - no to przeczytałem opis kilkanaście razy - i dalej nic nie wiem :) jak z tego zrobić program? w którym pliku ustawić przedział? (mam vistę 64bity więc rozumiem, że nie muszę podmieniać PrimeQ64.h (co i tak by mi się nie udało bo nie wiem jak:) ) ja chętnie to zapuszczę na swoim kompie, ale musisz mi powiedzieć jak to skompilować/uruchomić (jak najprostszym językiem, bo na tym się w ogóle nie znam). ewentualnie poczekam jak ktoś to rozgryzie :)

[emik]

kompilujesz poleceniem: gcc -O3 -lm -lgmp -o ap19 AP19-64.c
uruchamiasz: ./ap19 <start> <stop> gdzie jako start i stop wpisujesz zakres

ja na początek biorę zakres od 1 do 100000

[Jarek Wróblewski]

Jak program będzie skompilowany, z ustawieniem przedziału nie powinno być problemu. Ja tego pod Windowsem kompilować nie umiem, trzeba mieć gmp. Jak ktoś umie, niech podpowie, bo ten problem będzie przy każdym programie. Ponadto trzeba chyba wywalić z AP19-64.c linuxowe czasomierze, czyli całą definicję microtime() i wszystkie linijki zawierające "time", to może zależeć od kompilatora.

Z kompilacją musicie sobie zrobić jakąś wzajemną samopomoc, bo ja umiem kompilować tylko u siebie na kompilatorze, który w systemie linuxowym jest utrzymywany przez administratorów sieci.

W teorii przedział [x,y] ustawiamy uruchamiając program z linii poleceń
ap19.exe x y
jeśli będzie skompilowany do ap19.exe albo wpisując do pliku AP19-ini.txt linijkę postaci
x y
i uruchamiając program w tym samym katalogu, co ten plik.

Np. na pierwszy test czy chodzi można dać
1 1000
i wtedy w SOL-AP15.TXT powinno się znaleźć
15 65 598396207
15 140 229480759

[emik]

w zakresie 1 1000 wyniki zgadzają się więc wszystko ok

oto wyniki z zakresy 1 do 100.000:

15 65 598396207
15 140 229480759
15 65 598396207
15 140 229480759
15 1156 337523821
17 6682 110101249
16 10579 1121933177
15 40013 1218234179
15 88889 87380341

[lukaszde]

Sugerowalbym, zeby ktos pokompilowal i udostepnil gotowe EXEki dla 32 i 64bit.
Umowimy sie co do przeliczanych przedzialow, ustalimy w jaki sposob liczymy, tzn ile prob dla jednego z przedzialow aby wynik byl wiarygodny, kazdy chetny zasugeruje co liczy i rozpoczniemy zabawe ;)

[Machloj]

zgadzam się z przedmówcą - jak ktoś skompiluje to pod windowsa to niech się pochwali :)

[emik]

myślę, że zakresy milionowe będą w sam raz - starczy na nockę

[Troll81]

MOże faktycznie zaopiekowałby się tym TJM :) a my dozbieralibyśmy na serwerek :D projekt prime@poland ?? :D

[AiDec]

@Jarek Wroblewski (badz osoba ktora juz sie tym zajmuje - np. emik):

1. Uprzejmie prosze o podanie przykladowego zakresu obliczen, mozliwego do wykonania dla `przykladowego` komputera w okreslonym czasie. W pelni satysfakcjonowalaby mnie odpowiedz w stylu: Q6600 2.40 z Ubuntu AMD64 w ciagu 24h przerobi zakres 1-10mln.

2. Czy mam racje uwazajac ze ten `skrypt` bylby dostepny na wszystkie platformy?

3. Nie znalazlem informacji (moze gdzies pominalem) jaki zakres mamy przeszukac (nieograniczony?).

4. Czy skrypt jest pisany natywnie pod kilka rdzeni (przetwarzanie rownolegle etc.), ew. jesli nie to, czy na procku 4-jajecznym nalezaloby odpalic cztery skrypty?

5. Czy w przypadku tego skryptu przewaga systemu 64-bit jest rowniez ogromna, czy to juz `inna bajka`?

[emik]

ad1.
T5500@1660 aplikacja 64bity zakres 1-10000 - 91sekund
T5500@1660 aplikacja 32bity zakres 1-10000 - 90sekund
ad3. zakres od 1 do 2^31-1
ad4. musisz odpalić cztery aplikacje

czasy zbliżone ale był mały zakres danych, więc trzeba by powtórzyć na większym obszarze

[Jarek Wróblewski]

Wolałbym żebyście sami sobie rozdzielali przedziały. Na początek chyba wystarczą posty w stylu: Biorę xM-yM. Myślę, że nie ma sensu przeszukiwania tego samego przedziału przez więcej niż 1 osobę.

@AiDec

1. Na Athlonie 64 3000 1K szło mi w 8-9 sekund. Najlepiej zapuścić sobie testowo jakiś krótki przedział i zmierzyć prędkość. Przy dalszych zakresach może trochę spowalniać, ale chyba nie za bardzo - to wszystko jest do przetestowania. Przy tej prędkości 10mln=24h, ale inny procesor może łatwo wyrabiać ze 2 razy więcej na każdy rdzeń. Trzeba sobie samemu zmierzyć prędkość i oszacować.

2. Ja się na tym nie znam, sądzę, że polecenia, których używam, powinny się z grubsza przenosić. Pod Windowsem może być problem z drukowaniem liczb większych niż 2^32, ale ten konkretny program tego nie robi. Zawsze najlepiej zapuścić testowy przedział i zobaczyć jak działa.

3. Teoretycznie nie dalej niż do 2^31-1, można dalej, ale trzeba byłoby zmienić typ liczb w programie.  W zasadzie to się decyduje w trakcie poszukiwań. Jak się znajdzie rozwiązanie, to można iść dalej, licząc na lepsze, albo sobie odpuścić.

4. Pod 1 rdzeń. Na 4 rdzeniach odpalamy 4 skrypty w różnych katalogach roboczych.

5. Nie testowałem, ale wydaje mi się, że też. W zasadzie program jest tego samego typu, więc i ten aspekt powinien wyglądać podobnie.

[sesef]

Dobra zadanie na dzisiejszą noc, skompilować to pod windows.

Na razie walczę z portem GMP na windowsy, a raczej z Visual Studio które nie lubi libów kompilowanych starszymi wersjami VS.

na razie dla testów próbuje skompilować appa ma x86 jak się uda to z przejściem na x64 nie powinno być już problemów (mam nadzieję)

Któryś z Linuxowców albo Pan Jarek mógłby mnie oświecić i powiedzieć jakie przedziały liczbowe dostarcza biblioteka GMP, może zamiast męczyć się z portem znalazła by się jakaś biblioteka co oferuje takie przedziały pod windows.

[Jarek Wróblewski]

Któryś z Linuxowców albo Pan Jarek mógłby mnie oświecić i powiedzieć jakie przedziały liczbowe dostarcza biblioteka GMP, może zamiast męczyć się z portem znalazła by się jakaś biblioteka co oferuje takie przedziały pod windows.

gmp jest potrzebne do zdefiniowania procedury

int PrimeQ(long long value)

która testuje, czy liczba 64-bitowa jest pierwsza (wartość procedury różna od 0) czy złożona (procedura ma dawać 0). Procedura ta jest zdefiniowana w PrimeQ32.h i PrimeQ64.h. Poza tym gmp nie jest używane.

Można się obejść bez gmp, ale trzeba mieć własną procedurę testująca pierwszość liczb 64-bitowych i wstawić ją do PrimeQ. Nie wiem, czy to łatwiejsze.

[Jarek Wróblewski]

Wygrzebałem ze starego pliku następujące paskudztwo:

*************

typedef unsigned int __attribute__ ((mode(TI))) uint128;

long long PowerMod(long long r, long long e, long long p)
{
        uint128 a;
        if(e==1) {return r;}
        else
        if(e==0) {return 1;}
        else
        if(e%2==0)
        {a=PowerMod(r,e/2,p); return (a*a)%p;}
        else
        a=PowerMod(r,e/2,p);
        a=(a*a)%p;
        return (r*a)%p;
};

int PrimeQ(long long p)
{
        return (2==PowerMod(2,p,p))?1:0;
};

**************

Pierwsza linijka w jakiś tajemniczy sposób pod 64-bitowym linuxem definiuje liczby 128-bitowe (kolega mi to pokazał, często działa, a często wysypuje kompilator gcc4 i trzeba używać gcc3). Nieważne. W każdym razie, jeśli mamy liczby 128-bitowe, to reszta nadaje się do testowania pierwszości - teoretycznie może to uznać liczbę złożoną za pierwszą, ale zdarza się to na tyle rzadko, że nie zakłóca programu. Dobrego rozwiązania nie pominie, a jak przepuści jakąś lipę, to się ją odsieje przy ręcznej weryfikacji.

W każdym razie jak nie mamy gmp, a mamy liczby 128-bitowe, to jest OK.

[sesef]

Pierwszy etap zakończony

Aplikacja na 32 bity pod windowsa http://www.speedyshare.com/212443438.html

Teraz jeszcze spróbuje skompilować na x64.

Co do x86 kompilowane na standardowym GMP bez optymalizacji pod jakikolwiek procesor oraz z wyłączonymi optymalizacjami kompilatora gdyż nie ma to sensu skoro 32 bitowe systemy się nie nadają do obliczeń.

Jakby ktoś chciał się pobawić z kompilacja tutaj wszystko ładnie opisane jak skompilować GMP pod VS 2008 http://fp.gladman.plus.com/computing/gmp4win.htm jeszcze więcej informacji w readme.txt w ściągniętym zipie.


Coś się nie chce kompilować GMP na x64 z 32 bitowego systemu :/ Zainstaluje XP x64 i zobaczymy może wtedy ruszy

[Jarek Wróblewski]

T5500@1660 aplikacja 64bity zakres 1-10000 - 91sekund
T5500@1660 aplikacja 32bity zakres 1-10000 - 90sekund
czasy zbliżone ale był mały zakres danych, więc trzeba by powtórzyć na większym obszarze

To w zupełności wystarczy, żeby stwierdzić, że na 32 i 64 bitach działa tak samo szybko. W zasadzie test kilkusekundowy już by wystarczył. Jak się zastanowiłem, to chyba wiem dlaczego tak może być. Otóż w tym programie zamiast dzielenia liczb 64-bitowych jest dzielenie 32-bitowe, a to chyba najbardziej żarłoczna operacja z tego programu.

To jednak sytuacja wyjątkowa, w większości tego typu programów nie da się uniknąć dzielenia 64-bitowego.

Inna sprawa, że T5500 jest procesorem nowszej generacji niż stare 32-bitówki i wcale nie jest powiedziane, że na nich też tak fajnie to pójdzie. Ale dramatycznej różnicy być nie powinno.

******

Po prostu tu nie ma mądrych na przewidywanie prędkości działania. Dopiero testy konkretnego programu pokazują jak jest naprawdę.

[Szopler]

Jak będą execki dla Win XP x64 to się przyłączam :P.

[Jarek Wróblewski]

Po dokładnym przejrzeniu kodu stwierdzam, że w obecnej wersji powinien działać poprawnie tylko do 1757658938, czyli troszkę mniej niż 2^31, ale poza tym, że nie należy przekraczać tej granicy, to nie ma istotnego znaczenia.

Myślę, że po ewentualnym znalezieniu rozwiązania AP19, należy kontynuować do powyższej wartości licząc na lepsze AP19 lub na AP20.

[sesef]

Co do APP-a x64 walczyłem kilka godzin przy okazji sypnąłem sobie 2 systemy (ale to już inna bajka + własna głupota) jak dotąd nie udało mi się skompilować GMP na x64 przez co nie mogę skompilować samego programu. Jak komuś się chce i potrafi może podłubać z Dev C++/Code Blocks obydwa środowiska używają GCC pod tym powinno w miarę ruszyć. Ja do tego środowiska nie mam zdrowia.


Myślałem również nad własna implementacja testu pierwszości, z tego co się doczytałem GMP korzysta z testu Millera-Rabina jadnak taka aplikacja będzie pewnie wolniejsza niż kompilowane z GMP.

[Jarek Wróblewski]

Myślałem również nad własna implementacja testu pierwszości, z tego co się doczytałem GMP korzysta z testu Millera-Rabina jadnak taka aplikacja będzie pewnie wolniejsza niż kompilowane z GMP.

Podejrzewam, że w tym konkretnym programie testowanie pierwszości jest wykonywane na tyle rzadko, że jego wydajność nie jest zbyt istotna. Myślę jednak, że nie ma sensu tracić energii na prowizoryczne rozwiązania, które w przyszłości nie wystarczą. Myślę, że na dłuższą metę bez GMP się nie obejdzie. W wielu programach, jakie mam w planie na przyszłość, trzeba operować na liczbach 128-bitowych i testować pierwszość liczb 128-bitowych. Trudno też każdy program pisać w 2 wersjach: z GMP i bez GMP.

Tak więc z punktu widzenia inwestycji w przyszłość dobrze byłoby, żeby ktoś kto ma nerwy do wepchnięcia GMP w Windowsowy kompilator, utorował drogę kolejnym programom.

[Jarek Wróblewski]

Kolejne dwa zadanka w katalogu
http://www.math.uni.wroc.pl/~jwr/BaP/
pliki Ap20.zip oraz Ap21.zip
Na razie starczy, zobaczymy, co jesteście w stanie z tego wydusić.

Programy niewiele różnią się od pierwszego, więc powinny sie podobnie zachowywać. W/g mojej oceny z tych trzech zadań największe szanse na rekord daje AP20. Jednak liczby pierwsze są tak nieprzewidywalne, że trudno coś prognozować.

[kempler]

Yyyy czy ten exex: AP19.x86.exe powinien działać na każdym win xp 32 ?

[Timaxi]

Yyyy czy ten exex: AP19.x86.exe powinien działać na każdym win xp 32 ?

No właśnie u mnie coś za bardzo nie działa :(
P.S. Mógłby ktoś zrobić instrukcje (dla laika  ;D) jak to uruchomić.

[AiDec]

Aplikacja na 32 bity pod windowsa http://www.speedyshare.com/212443438.html

Swietnie sesef, tylko ja dalej nie qmam ;). Sciagnalem i co mam z ty zrobic? Po odpaleniu mam komunikat: `Nie mozna uruchomic aplikacji, poniewaz jej konfiguracja jest niewlasciwa`. Odpalam to pod XP SP3 z juz zapietymi redistributami (jesli to ma znaczenie).


EDIT: Widze ze jestem trzeci w tym temacie. Sadzilem ze to ja jestem zawsze najwiekszym narzekaczem, ale skoro Kempler i Mchl tez nie qmaja, to znaczy cos jest na rzeczy ;).

[kempler]

Widzę na nasza trójka ma dokładnie taki sam problem... ;)

[lukaszde]

Start > Uruchom > wpisujecie CMD

1 W linii komend, poslugujac sie komenda cd przechodzicie do folderu gdzie jest zlokalizowany plik APexe.

2 W folderze z plikiem AP.exe powienien sie znalezc plik AP19-ini.txt postaci
x y
Np. 1 1000
i wtedy w wynikach - plik SOL-AP15.TXT powinno się znaleźć
15 65 598396207
15 140 229480759"

3 Z uruchamianiem nie bedzie problemu, wystarczy wpisac  nazwa.exe i dac enter  :P

Mam nadzieje, ze dzieki tym wskazowkom, poradzicie sobie z uruchamaniem programiku.

[emik]

a w linii komend jak uruchamiacie musicie chyba też podać argumenty czyli np:

Kod [Zaznacz] Rozwiń

AP19.x86.exe 1 1000

[AiDec]

Start > Uruchom > wpisujecie CMD

1 W linii komend, poslugujac sie komenda cd przechodzicie do folderu gdzie jest zlokalizowany plik APexe.

2 W folderze z plikiem AP.exe powienien sie znalezc plik AP19-ini.txt postaci
x y
(...)

Sugerujesz cofniecie sie 20 lat wstecz? Bo jakos majac pietnascie takie rzeczy robilem... Teraz juz za stary jestem.

[emik]

to stwórz w katalogu z programem plik AP19-ini.txt w którym będziesz wpisywał zakres i uruchamiaj program kliknięciem na niego a wyniki będziesz miał w plikach SOL-AP15.txt i SOL-AP19.txt :P

[mindc]

możecie u siebie sprawdzić jak działa i czy poprawnie?

http://zeus.mindc.net/~panther/files/ap19_windows_x64.exe

dzięki

[Szopler]

Zaciągam...