From a779dae5d38516943081d410d65ace286402dd4a Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Anton=20Luka=20=C5=A0ijanec?= Date: Sat, 7 May 2022 00:37:25 +0200 Subject: =?UTF-8?q?grem=20na=20drug=20ra=C4=8Dunalnik,=20da=20dobim=20open?= =?UTF-8?q?gl=203.3?= MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit --- "mat/program\304\215ki/ni\304\215le.c" | 128 ++++++++++++++++----------------- 1 file changed, 60 insertions(+), 68 deletions(-) (limited to 'mat/programčki/ničle.c') diff --git "a/mat/program\304\215ki/ni\304\215le.c" "b/mat/program\304\215ki/ni\304\215le.c" index cf453d8..68f4142 100644 --- "a/mat/program\304\215ki/ni\304\215le.c" +++ "b/mat/program\304\215ki/ni\304\215le.c" @@ -1,6 +1,6 @@ #include // navdih za to je tedx predstavitev andreja bauerja z naslovom ničle -#include // to je izris ničel littlewoodovih polinomov -#include // prevod: gcc -Wall -Wextra ničle.c -lgsl -lm -pthread +#include // to je izris ničel littlewoodovih polinomov v manj kot 105 vrsticah +#include // prevod: gcc (-Ofast) -Wall -Wextra -pedantic -lgsl -lm ničle.c #include // program na poti "ime" izdela kvadratno PGM datoteko podane višine #include // za nadaljno obdelavo je uporabno, če je širina liha; ni pa nujno #include // algoritem se da paralelizirati, ampak jaz imam samo en procesor @@ -8,98 +8,90 @@ #include #include #include -#include -struct nit { - int začetek; - int konec; // nit, pomni, da računaš DO konca in konca ne računaš; hvala -}; -void pripravi_koeficiente (double * izhod, int številka) { - while (številka) { +#include +void pripravi_koeficiente (double * izhod, int številka, int koeficientov) { + while (koeficientov--) { *izhod++ = številka & 1 ? 1 : -1; številka >>= 1; } } -pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER; -_Atomic int izvs = 0, nekonvergiranih = 0, stopnja, ši; -unsigned char * slika; -void * računaj (void * vhod) { - double koeficienti[stopnja+1]; // kako prikladno! polinom nte stopnje ima n+1 členov - double ničle[2*stopnja]; // ima pa n ničer, 2n+0 so realni deli, 2n+1 pa imaginarni - struct nit * nit = (struct nit *) vhod; - gsl_poly_complex_workspace * w = gsl_poly_complex_workspace_alloc(stopnja+1); - for (int i = nit->začetek; i < nit->konec; i++) { - pripravi_koeficiente(koeficienti, i); // noben člen ni 0, vsi so bodisi 1 bodisi -1 - if (gsl_poly_complex_solve(koeficienti, stopnja+1, w, ničle) != GSL_SUCCESS) - nekonvergiranih++; // uuu, lahko bi recimo narisali tiste, ki ne konver. - for (int j = 0; j < 2*stopnja; j += 2) { - int višs = ši/2 - ničle[j+1]*(ši/4); - int širs = ši/2 + ničle[j]*(ši/4); - if (višs > ši || širs > ši || višs < 0 || širs < 0) { - izvs++; - continue; - } - pthread_mutex_lock(&mutex); - slika[2*ši*višs+širs*2+1]++; - if (!slika[2*ši*višs+širs*2+1]) - if (slika[2*ši*višs+širs*2] != 255) - slika[2*ši*višs+širs*2]++; - pthread_mutex_unlock(&mutex); - } - } - gsl_poly_complex_workspace_free(w); - free(nit); return NULL; -} int main (int argc, char ** argv) { - if (argc != 1+4) { - fprintf(stderr, "takole: %s stopnja ime širina niti\n", argv[0] ? argv[0] : "ničle"); + int izven_slike = 0; + int nekonvergiranih = 0; + if (argc != 1+3 && argc != 1+4) { + fprintf(stderr, "uporaba: %s stopnja ime širina [razvij 1/4 krožnice]\n", + argv[0] ? argv[0] : "ničle"); return 1; } - int r = 0, kje_začeti = 0, fd, šn = atoi(argv[4]); - stopnja = atoi(argv[1]); - ši = atoi(argv[3]); - pthread_t niti[šn]; + long long int šir = atoi(argv[3]); + int fd; if ((fd = open(argv[2], O_CREAT | O_RDWR, 00664)) == -1) { perror("open"); return 2; } - if (ftruncate(fd, 128 + ši*ši*2) == -1) { + if (ftruncate(fd, 128 + šir*šir) == -1) { perror("ftruncate"); if (close(fd) == -1) perror("close"); return 3; } void * p; - if ((p = mmap(NULL, 128 + ši*ši*2, PROT_READ|PROT_WRITE, MAP_SHARED, fd, 0)) == MAP_FAILED) { + if ((p = mmap(NULL, 128+šir*šir, PROT_READ|PROT_WRITE, MAP_SHARED, fd, 0)) == MAP_FAILED) { perror("mmap"); if (close(fd) == -1) perror("close"); return 4; } - slika = (unsigned char *) p + 128; - memset(p, 0, 128 + ši*ši*2); - sprintf(p, "P5\n\n%58d\n%58d\n65535\n", ši, ši); // precisely calculated with dc(1) (: + unsigned char * slika = (unsigned char *) p + 128; + char * razvij = argv[4]; + memset(p, 0, 128 + šir*šir); + sprintf(p, "P5\n\n%57lld\n%57lld\n255\n", šir, šir); + long long int stopnja = atoi(argv[1]); + double koeficienti[stopnja+1]; // kako prikladno! polinom nte stopnje ima n+1 členov + double ničle[2*stopnja]; // ima pa n ničel, 2n so realni deli, 2n+1 pa imagin. gsl_set_error_handler_off(); - for (int i = 0; i < šn; i++) { - struct nit * nit = malloc(sizeof(struct nit)); - nit->začetek = kje_začeti; - nit->konec = (kje_začeti += ((1 << (stopnja+1))-1) / šn); - - if ((r = pthread_create(niti+i, NULL, računaj, nit))) { - fprintf(stderr, "pthread_create: %s (%d)\n", strerror(r), r); - r = 5; goto r; - } - } - for (int i = 0; i < šn; i++) { - if ((r = pthread_join(niti[i], NULL))) { - fprintf(stderr, "pthread_join: %s (%d)\n", strerror(r), r); - r = 6; goto r; + gsl_poly_complex_workspace * w = gsl_poly_complex_workspace_alloc(stopnja+1); + int prej_izpisano = 6969; + unsigned int over = 0; + for (long long int i = 0; i < 1LL << (stopnja+1); i++) { + if (prej_izpisano != i*1000/(1LL << (stopnja+1))) { + prej_izpisano = i*1000/(1LL << (stopnja+1)); + fprintf(stderr, "\rRačunam in rišem ničle: %d promilov", prej_izpisano); + } // noben člen ni 0, vsi so bodisi 1 bodisi -1 + pripravi_koeficiente(koeficienti, i, stopnja+1); + if (gsl_poly_complex_solve(koeficienti, stopnja+1, w, ničle) != GSL_SUCCESS) + nekonvergiranih++; // uuu, lahko bi recimo narisali tiste, ki ne konver. + for (int j = 0; j < 2*stopnja; j += 2) { + int širina_na_sliki, višina_na_sliki; + if (razvij) { + double razd = sqrt(ničle[j]*ničle[j]+ničle[j+1]*ničle[j+1]); + if (ničle[j] < 0 || ničle[j+1] < 0) + continue; // to ne šteje za izven_slike + širina_na_sliki = atan2(ničle[j], ničle[j+1])/M_PI*šir*2; + višina_na_sliki = razd*šir/2; + } else { + višina_na_sliki = šir/2 - ničle[j+1]*(šir/4); + širina_na_sliki = šir/2 + ničle[j]*(šir/4); + } + if (višina_na_sliki > šir || širina_na_sliki > šir + || višina_na_sliki < 0 || širina_na_sliki < 0) { + izven_slike++; + continue; + } + if (slika[šir*višina_na_sliki+širina_na_sliki] == 255) + over++; + else + slika[šir*višina_na_sliki+širina_na_sliki]++; } } -r: - if (munmap(p, 128 + ši*ši*2) == -1) + fprintf(stderr, "\r KONČANO \n"); + gsl_poly_complex_workspace_free(w); + if (munmap(p, 128 + šir*šir + ) == -1) perror("munmap"); // nima smisla ukinjat programa, sistem si je sam kriv >:) if (close(fd) == -1) perror("close"); - printf("%d ničel je izven 2+2i\n%d polinomov ni konvergiralo\n", izvs, nekonvergiranih); - return r; + printf("%u ničel je izven 2+2i (izven slike)\n%u polinomov ni konvergiralo\n" + "%d overflowov na sliki\n", izven_slike, nekonvergiranih, over); + return 0; } -- cgit v1.2.3