Algorytm Jarka Wróblewskiego

Zaczęty przez Jarek Wróblewski, 03 Styczeń 2009, 11:59

emik

jak aplikacje będą działać poprawnie to trzeba zacząć rozdzielać zakresy i bierzemy się za obliczenia


Szopler

Windows XP x64 @ T9300

ap19.exe 1000 10000
TIME: 52999405 microseconds


Plik wynikowy:
10001 10000

emik

plik wynikowy masz o nazwie SOL-AP15.txt a ty dałeś dane z pliku zakresowego

dla tego zakresu powinno być:

15 65 598396207
15 140 229480759
15 1156 337523821
17 6682 110101249


Szopler

U mnie plik SOL w ogóle nie powstał!

emik

to może spróbuj utworzyć pusty plik tekstowy o tej nazwie w katalogu z programem i dopiero go uruchom


Szopler

#45
SOL-AP19.txt - pusty
SOL-AP15.txt - pusty

Próbowałem różnych kombinacji i jedyne co widzę to to, że zmienia mi plik ini.
wpiszę 333 (do) 3333 to po wykonaniu programu mam 3334 3333, dla 1 (do) 1000 zmienia na 1001 1000.

emik

plik.ini służy do tego, że jak przerwiesz program to zaczyna on później dalsze przeliczania od miejsca określonego w pierwszej pozycja, a jeśli ta liczba jest większa od drugiej to znaczy, że zakres został zakończony


Jarek Wróblewski

Teoretycznie mogło się coś skopać z obliczeniami przy kompilacji. Mam nadzieję, że Prime32.h/Prime64.h jest dobrane odpowiednio do wersji, bo kompilator się nie poskarży, a program będzie liczył głupoty.

Gdyby skompilować wersję testową zmieniając w AP19.h linia 134

if(k>=10)
na
if(k>=7)

oraz w AP19-64.c linia 32

  if(AP_Length>=15){
na
  if(AP_Length>=7){

to nawet program, który liczy głupoty, powinien coś wpisać do pliku z wynikami, jeśli się go uruchomi w zakresie 1-1000. Z tego, co wpisze być może mógłbym spróbować zgadnąć, w czym problem.

Znaleziono AP26:

http://www.primegrid.com/forum_thread.php?id=1246#22466

emik

z tego co zrozumiałem to na windowsie plik wynikowy nie powstaje


Jarek Wróblewski

Jeszcze można w AP19-64.c po

    out = fopen("SOL-AP15.TXT", "a");
    fprintf(out,"%d %d %lld\n",AP_Length,difference,First_Term);

dodać

    printf("%d %d %d\n",AP_Length,difference,(int)First_Term);

i obserwować, co się pojawi na ekranie.
Znaleziono AP26:

http://www.primegrid.com/forum_thread.php?id=1246#22466

mindc

Cytat: Jarek Wróblewski w 04 Styczeń 2009, 13:56
Teoretycznie mogło się coś skopać z obliczeniami przy kompilacji. Mam nadzieję, że Prime32.h/Prime64.h jest dobrane odpowiednio do wersji, bo kompilator się nie poskarży, a program będzie liczył głupoty.

Gdyby skompilować wersję testową zmieniając w AP19.h linia 134

if(k>=10)
na
if(k>=7)

oraz w AP19-64.c linia 32

  if(AP_Length>=15){
na
  if(AP_Length>=7){

to nawet program, który liczy głupoty, powinien coś wpisać do pliku z wynikami, jeśli się go uruchomi w zakresie 1-1000. Z tego, co wpisze być może mógłbym spróbować zgadnąć, w czym problem.

po tych zmianach, zawartość pliku SOL-AP15.TXT, dla zakresu 1-1000:

Cytat
10 3 34885523
7 4 521456203
8 5 1059076987
7 5 618419947
7 5 400523197
7 5 692438231
7 5 833400947
7 6 1101329077
7 7 598994027
7 9 434687459
9 12 784730797
9 16 1457831491
12 19 1108058221
8 25 864274319
8 27 1160753959
8 30 1211370239
8 32 1282347991
7 32 961145401
7 34 947001613
7 36 869029297
7 39 1123725461
10 41 199427939
7 45 817682623
7 48 1223836447
8 49 55415093
7 49 530699903
9 49 574121099
8 49 1049405909
7 50 1318362337
7 50 1286319257
7 51 150117533
7 53 790333363
9 53 15338177
7 54 666476507
7 55 248658701
8 56 371285953
7 78 244228547



Jarek Wróblewski

Wszystko jest OK oprócz testowania pierwszości liczb powyżej 2^32.

Zapewne szwankuje konwersja long long value -> mpz_t n w procedurze PrimeQ z pliku PrimeQ64.h.

Zara pomyślimy jak to obejść...
Znaleziono AP26:

http://www.primegrid.com/forum_thread.php?id=1246#22466

Jarek Wróblewski

Takiego mam pomysła, a nawet trzy.

W pliku PrimeQ64.h zamiast 2 linijek

       PTR(n)[0] = value;
       SIZ(n) =1;

dać 1 linijkę

mpz_set_ui(n,value);

Jeżeli to nie zadziała, spróbować zamiast powyższych 2 linijek dać 4 linijki

mpz_set_ui(n,(unsigned int)(value>>32));
mpz_mul_ui(n,n,1<<16);
mpz_mul_ui(n,n,1<<16);
mpz_add_ui(n,n,(unsigned int)(value^((1LL<<32)-1));

To drugie rozwiązanie ma szansę działać także na 32 bitach, gdyby tam były problemy.

Można też spróbować na 64 bitach kompilować PrimeQ32.h. Jeżeli ten gmp nie jest w pełni dostosowany do 64 bitów i używa słów 32-bitowych, to to ma szansę pójść.

Jeśli coś zadziała, to ustawienia z 7-ką dadzą masę rozwiązań, a powrót do 15-tki da to, co ma być.


Znaleziono AP26:

http://www.primegrid.com/forum_thread.php?id=1246#22466

mindc

Cytat: Jarek Wróblewski w 04 Styczeń 2009, 15:29
Takiego mam pomysła, a nawet trzy.

W pliku PrimeQ64.h zamiast 2 linijek

       PTR(n)[0] = value;
       SIZ(n) =1;

dać 1 linijkę
mpz_set_ui(n,value);



zawartość pliku SOL-AP15.TXT dla zakresu 1-1000

Cytat
10 3 34885523
7 4 521456203
8 5 1059076987
7 5 618419947
7 5 400523197
7 5 692438231
7 5 833400947
7 6 1101329077
7 7 598994027
7 9 434687459
9 12 784730797
9 16 1457831491
12 19 1108058221
8 25 864274319
8 27 1160753959
8 30 1211370239
8 32 1282347991
7 32 961145401
7 34 947001613
7 36 869029297
7 39 1123725461
10 41 199427939
7 45 817682623
7 48 1223836447
8 49 55415093
7 49 530699903
9 49 574121099
8 49 1049405909
7 50 1318362337
7 50 1286319257
7 51 150117533
7 53 790333363
9 53 15338177
7 54 666476507
7 55 248658701
8 56 371285953
7 56 1251227567
7 117 388651139
7 123 696612359
7 128 744170807

Cytat
Jeżeli to nie zadziała, spróbować zamiast powyższych 2 linijek dać 4 linijki

mpz_set_ui(n,(unsigned int)(value>>32));
mpz_mul_ui(n,n,1<<16);
mpz_mul_ui(n,n,1<<16);
mpz_add_ui(n,n,(unsigned int)(value^((1LL<<32)-1)));


zawartość pliku SOL-AP15.TXT dla zakresu 1-1000: pusto


Jarek Wróblewski

Pusto, bo głupotę napisałem. Zamiast

mpz_add_ui(n,n,(unsigned int)(value^((1LL<<32)-1)));

powinno być

mpz_add_ui(n,n,(unsigned int)(value&((1LL<<32)-1)));
Znaleziono AP26:

http://www.primegrid.com/forum_thread.php?id=1246#22466

TJM

 |-? głowa mnie rozbolała od przeczytania tego tematu, matematyka to dla mnie w większości czarna magia %-)
Jeśli przewidywany czas obliczeń, żeby uzyskać jakiś rezultat jest dość długi, teoretycznie mógłbym skrobnąć na szybko jakiś prosty serwerek i skrypty po stronie klienta automatycznie przydzielające kolejne zakresy.
Projekt BOINC raczej nie ma sensu, bo byłaby to konkurencja dla PrimeGrida i to z początku dość słaba (zanim by się rozbudowało wszystko do takiego poziomu jak oni mają, minęłoby zapewne wiele miesięcy); nie wspominając już o tym, że aplikację trzeba obudować wrapperem lub wbudować BOINC_API oraz przygotować całe środowisko serwerowe, co też pewnie zajęłoby z miesiąc dla uzyskania pierwszej stabilnej wersji.
No chyba, że mamy jakąś pewność, że byłoby co liczyć przez co najmniej parę  miesięcy - wtedy można coś w tym temacie pomyśleć.

W razie jakiejś pilniejszej sprawy - jestem często dostępny na kanale IRC B@P, na forum czasami zapominam zajrzeć lub nie mam czasu.

Jarek Wróblewski

Cytat: TJM w 04 Styczeń 2009, 16:32
No chyba, że mamy jakąś pewność, że byłoby co liczyć przez co najmniej parę  miesięcy - wtedy można coś w tym temacie pomyśleć.

Zagadnień do liczenia na dowolnie długi czas mogę spokojnie dostarczyć. Na razie jest chyba trochę przedwcześnie, aby mówić o szczegółach BOINC-ów czy serwerków. Myślę, że najpierw parę w miarę krótkich zagadnień trzeba rozwiązać dzieląc zakresy ręcznie. To pokaże nam wszystkim, na czym polega ta zabawa i jakie się mogą pojawiać problemy. Na dłuższą metę rozdział zadań musi być automatyczny, więc jakiś serwerek to chyba absolutne minimum, jeśli mamy zamiar myśleć o czymś poważnym.
Znaleziono AP26:

http://www.primegrid.com/forum_thread.php?id=1246#22466

mindc

#57
Cytat: Jarek Wróblewski w 04 Styczeń 2009, 16:08
Pusto, bo głupotę napisałem. Zamiast

mpz_add_ui(n,n,(unsigned int)(value^((1LL<<32)-1)));

powinno być

mpz_add_ui(n,n,(unsigned int)(value&((1LL<<32)-1)));

niestety, dalej pusto
a może chodzi o to, że podczas kompilacji sypie mi warningami o
konwersji '__int64' na 'unisgned int',  po modyfikcjach pliku PrimeQ64.h
lub konwersji '__int64'  na 'int' w pliku AP19.h
może dlatego gubimy liczby powyżej 2^32 z powodu właśnie niezamierzonej konwersji typów

EDIT:
zaczyna mi się tu coś niepodobać, bo kompilacja czysto 32 bitowa, także wypluwa mi puste pliki (a raczej ich brak)



Jarek Wróblewski

#58
Cytat: mindc w 04 Styczeń 2009, 18:18
a może chodzi o to, że podczas kompilacji sypie mi warningami o
konwersji '__int64' na 'unisgned int',  po modyfikcjach pliku PrimeQ64.h
lub konwersji '__int64'  na 'int' w pliku AP19.h
może dlatego gubimy liczby powyżej 2^32 z powodu właśnie niezamierzonej konwersji typów

W AP19.h sobie może sypać warningami, bo nie mapowałem wyraźnie typów, to powinno być OK. Coś jest skopane w definicji PrimeQ i teraz już nie wiem co.

***********

Sprawdzenie procedury PrimeQ:

Robimy plik PrimeQ.h:

Cytat
int PrimeQ(long long value)
{
   int out;
   char c[64];//usunac jak bedzie OK
       mpz_t  n;
       mpz_init(n);

mpz_set_ui(n,(unsigned int)(value>>32));
mpz_mul_ui(n,n,1<<16);
mpz_mul_ui(n,n,1<<16);
mpz_add_ui(n,n,(unsigned int)(value&((1LL<<32)-1)));

       out=mpz_probab_prime_p (n,1);

mpz_get_str(c,10,n);//usunac jak bedzie OK
printf("%s %d\n",c,out);//usunac jak bedzie OK

       mpz_clear(n);
       
       return out;

}

oraz Test.c:

Cytat
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <gmp.h>

#include "PrimeQ.h"
int main(int argc, char *argv[])
{

int i;

long long n;

n=1000000019;

for(i=1;i<=13;i++)
{
n+=2000000000;
PrimeQ(n);
};

system("PAUSE");

  return 0;
}

Po skompilowaniu i odpaleniu Test.c powinien dać na 32 lub 64 bitach:

Cytat
3000000019 1
5000000019 0
7000000019 0
9000000019 0
11000000019 0
13000000019 0
15000000019 0
17000000019 0
19000000019 0
21000000019 1
23000000019 0
25000000019 0
27000000019 1

EDIT:

@mindc: Jak będę wiedział, jakie wyniki drukuje u Ciebie powyższy test, to dopiero wtedy możemy coś dalej kombinować. To się powinno zachowywać jak wyżej, niezależnie od liczby bitów.
Znaleziono AP26:

http://www.primegrid.com/forum_thread.php?id=1246#22466

bartsob5

Pracujesz na uniwersytecie?
bo w sumie, to ja slyszalem, ze w polsce to mocy obliczeniowej nie brakuje (w przeciwienstwie do ludzi i kasy)... nie zastanawiales sie nad zaprzegnieciem jakiegos superkomputera?

Juras23

#60
Cytat: bartsob5 w 05 Styczeń 2009, 18:42
Pracujesz na uniwersytecie?
bo w sumie, to ja slyszalem, ze w polsce to mocy obliczeniowej nie brakuje (w przeciwienstwie do ludzi i kasy)... nie zastanawiales sie nad zaprzegnieciem jakiegos superkomputera?

HEH - Bartsob5 - odnoszę wrażenie że to co piszesz jest dokładnie przeciwstawieniem tego do czego nawołujemy - czyli potrzebujemy więcej mocy obliczeniowej i chcemy rozpraszać duże obliczenia z superkomputerów na mniejsze maszyny - jakoś tak mi tu taki kontrast wchodzi na myśl.  :P

Mchl

Tyle, że jak dotąd wszelkie uczelnie, które staraliśmy się zainteresować BOINCem odpowiadały: "Ale my mamy gdzie liczyć"

W nagłych wypadkach wzywać przez: mail: mchlpl[at]gmail.com | PM|mchl[a]boincatpoland.org

mindc

Cytat: Jarek Wróblewski w 04 Styczeń 2009, 18:38
Sprawdzenie procedury PrimeQ (...)

x64:

Cytat
3000000019 1
5000000019 0
7000000019 0
9000000019 0
11000000019 0
13000000019 0
15000000019 0
17000000019 0
19000000019 0
21000000019 0
23000000019 0
25000000019 0
27000000019 1

x86:

Cytat
3000000019 1
5000000019 0
7000000019 0
9000000019 0
11000000019 0
13000000019 0
15000000019 0
17000000019 0
19000000019 0
21000000019 1
23000000019 0
25000000019 0
27000000019 0



Szopler

Walczcie Panowie! A jak już zwalczycie to dajcie znać - ściągnę sobie ten programik, rozdzielimy zakresy i jazdaaaa :attack:

Jarek Wróblewski

#64
@bartsob5: Tak, pracuję na Uniwersytecie Wrocławskim. O żadnych łatwo dostępnych superkomputerach mi nic nie wiadomo.

@mindc: No to chyba teraz wiadomo tyle, że to Twoje GMP jest jakieś lewe, przynajmniej test pierwszości daje wyniki do bani powyżej 2^32.

Zaraz pomyślę nad następnym testem, może da się to obejść...

EDIT

Spawa jest banalna. Robisz program
Cytat
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <gmp.h>
int main(int argc, char *argv[])
{
int i;
char c[64];
char d[64];
mpz_t n;
mpz_t m;
mpz_t dwa;
mpz_init(n);
mpz_init(m);
mpz_init(dwa);
mpz_set_str(n,"15000000019",10);
mpz_set_str(dwa,"2",10);
for(i=1;i<=12;i++){
mpz_add_ui(n,n,2000000000);
mpz_powm(m,dwa,n,n);
mpz_get_str(c,10,n);
mpz_get_str(d,10,m);
printf("%s %s\n",c,d);
};
mpz_clear(n);
system("PAUSE");
return 0;
}

Jeśli dostajesz dokładnie to
Cytat
17000000019 1855924640
19000000019 18764911666
21000000019 2
23000000019 8
25000000019 14662086300
27000000019 2
29000000019 25672840505
31000000019 3693428967
33000000019 8068775031
35000000019 134217728
37000000019 16095345138
39000000019 38213931463
to jestem w stanie prosto napisać procedurę testującą pierwszość.

Jeśli dostajesz cokolwiek innego, to przynajmniej wiadomo, co można zrobić z Twoim GMP - ale tego już nie napiszę na forum ;)
Znaleziono AP26:

http://www.primegrid.com/forum_thread.php?id=1246#22466

mindc

Wyniki nowego testu...

x86

Cytat
17000000019 1855924640
19000000019 18764911666
21000000019 2
23000000019 8
25000000019 14662086300
27000000019 2
29000000019 25672840505
31000000019 3693428967
33000000019 8068775031
35000000019 134217728
37000000019 16095345138
39000000019 38213931463

x64

Cytat
17000000019 1855924640
19000000019 18764911666
21000000019 2
23000000019 8
25000000019 14662086300
27000000019 2
29000000019 25672840505
31000000019 3693428967
33000000019 8068775031
35000000019 134217728
37000000019 16095345138
39000000019 38213931463

wygląda dobrze  ;D


Jarek Wróblewski

Może to w końcu zadziała
http://www.math.uni.wroc.pl/~jwr/BaP/
plik PrimeQ.zip
Znaleziono AP26:

http://www.primegrid.com/forum_thread.php?id=1246#22466

mindc



Szopler


Szopler

1 do 1000
15 65 598396207
15 140 229480759


1 do 10000
15 65 598396207
15 140 229480759
15 65 598396207
15 140 229480759
15 1156 337523821
17 6682 110101249


tylko jeszcze z nazwą pliku trzeba by coś zrobić bo ap19 tworzy wynik ap15 ;).
Jak dzielimy zakresy?

Jarek Wróblewski

Cytat: Szopler w 07 Styczeń 2009, 17:32
tylko jeszcze z nazwą pliku trzeba by coś zrobić bo ap19 tworzy wynik ap15 ;).

To jest celowe. W pliku SOL-AP15.TXT są zapisywane wszystkie AP15 i dłuższe. Z punktu widzenia poszukiwań są to śmieci, ale takie śmieci dobrze jest zapisywać, żeby wiedzieć co się dzieje - ile jakich rozwiązań znajduje program, np. ile 18-tek, 17-tek.

Jeśli będzie AP19, to będzie zapisane w SOL-AP15.TXT oraz w SOL-AP19.TXT (dwa razy).
Znaleziono AP26:

http://www.primegrid.com/forum_thread.php?id=1246#22466

Jarek Wróblewski

Cytat: Szopler w 07 Styczeń 2009, 17:32
Jak dzielimy zakresy?

Moja sugestia. Piszcie tu po kolei posty:
Biorę od ... do ...
Znaleziono AP26:

http://www.primegrid.com/forum_thread.php?id=1246#22466

Szopler

To ja...
pierwszy milion [1 do 1 000 000] :D

emik

ok ja od 1 000 001 do 2 000 000


Machloj


Szopler

#75
Uważajta to się nieco czasu liczy... ;)

Wyniki 1 do 1 000 000:
15 65 598396207
15 140 229480759
15 1156 337523821
17 6682 110101249
16 10579 1121933177
15 40013 1218234179
15 88889 87380341
15 119269 805503269
15 123908 1190445023
15 137684 488283073
15 144577 399444719
15 226495 1433893103
16 266144 410043391
16 340496 908653751
15 343489 816836677
16 380386 1010600791
15 531180 121932113
15 584570 1068368759
16 620733 1053699379
15 627605 979138847
16 650092 1304938421
16 704608 1087724507
15 801484 242973079
16 858761 463282423
15 902455 1315101839
15 923597 956815309
15 999383 718679333


Teraz biorę od 5 000 000 do 7 000 000.

emik

dlatego ja biorę po milionie - w sam raz na raz

Panie Jarku - rozumiem, że możemy dopiero chwalić się w tym wątku jak utworzy nam plik SOL-AP19.TXT


Jarek Wróblewski

Cytat: emik w 07 Styczeń 2009, 19:49
Panie Jarku - rozumiem, że możemy dopiero chwalić się w tym wątku jak utworzy nam plik SOL-AP19.TXT

Tak. Jeśli ktoś dostanie plik SOL-AP19.TXT to niech się pochwali.

Jednak nie kasujcie pliku ze śmieciami SOL-AP15.TXT - jeśli nie znajdzie się rozwiązanie, to może będę chciał je kiedyś przeanalizować.

Myślę, że "Jarku" w zupełności wystarczy, nie ma potrzeby utrzymywać sztucznego dystansu, zwracanie się na "Ty" lub po imieniu jest w/g mnie odpowiedniejsze.
Znaleziono AP26:

http://www.primegrid.com/forum_thread.php?id=1246#22466

Szopler

Wynik
5 000 000 do 7 000 000
15 5013452 1368397853
15 5020312 486259331
16 5099835 305320991
15 5111767 104480839
16 5246635 103505323
15 5322984 511794671
17 5353247 605459201
16 5710040 922409141
15 5827337 1115111603
17 6048084 647252449
16 6340225 127734281
15 6435251 664966447
16 6627536 773502491
17 6750574 1228004317
17 6816384 1014615383
17 6840922 1248448199


Teraz porcja na nockę - 7 000 000 do 10 000 000 :).

emik

wynik
1 000 000 - 2 000 000

16 1076266 664325611
15 1101302 400424237
16 1828488 759373873
16 1852568 865245361
15 1876856 879681449
15 1908153 781761527
15 1922346 1011811651
15 1929050 1037784037


kolej na 10 000 000 do 15 000 000