Algorytm Jarka Wróblewskiego

[emik]

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

[Szopler]

Windows XP x64 @ T9300

Kod [Zaznacz] Rozwiń

ap19.exe 1000 10000
TIME: 52999405 microseconds

Plik wynikowy:

Kod [Zaznacz] Rozwiń

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]

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.

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

[mindc]

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:

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

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

[mindc]

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

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

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

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

[Jarek Wróblewski]

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.

[mindc]

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]

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:

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:

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

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.

[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]

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

[mindc]

Sprawdzenie procedury PrimeQ (...)

x64:

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:

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]

@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

#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

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

[mindc]

Wyniki nowego testu...

x86

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

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

[mindc]

no i zadziałało ;D

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

[Szopler]

zaraz testnę...

[Szopler]

1 do 1000

Kod [Zaznacz] Rozwiń

15 65 598396207
15 140 229480759

1 do 10000

Kod [Zaznacz] Rozwiń

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]

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

[Jarek Wróblewski]

Jak dzielimy zakresy?

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

[Szopler]

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

[emik]

ok ja od 1 000 001 do 2 000 000

[Machloj]

to ja od 2000000 do 5000000

[Szopler]

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

Wyniki 1 do 1 000 000:

Kod [Zaznacz] Rozwiń

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]

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.

[Szopler]

Wynik
5 000 000 do 7 000 000

Kod [Zaznacz] Rozwiń

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

Kod [Zaznacz] Rozwiń


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