diff options
author | Anton Luka Šijanec <anton@sijanec.eu> | 2022-05-07 00:37:25 +0200 |
---|---|---|
committer | Anton Luka Šijanec <anton@sijanec.eu> | 2022-05-07 00:37:25 +0200 |
commit | a779dae5d38516943081d410d65ace286402dd4a (patch) | |
tree | d45e574d43d7c29213f3f8913b30b797625c705a /mat | |
parent | HELMHOLTZOVA TULJAVA (diff) | |
download | sola-gimb-3-a779dae5d38516943081d410d65ace286402dd4a.tar sola-gimb-3-a779dae5d38516943081d410d65ace286402dd4a.tar.gz sola-gimb-3-a779dae5d38516943081d410d65ace286402dd4a.tar.bz2 sola-gimb-3-a779dae5d38516943081d410d65ace286402dd4a.tar.lz sola-gimb-3-a779dae5d38516943081d410d65ace286402dd4a.tar.xz sola-gimb-3-a779dae5d38516943081d410d65ace286402dd4a.tar.zst sola-gimb-3-a779dae5d38516943081d410d65ace286402dd4a.zip |
Diffstat (limited to 'mat')
-rw-r--r-- | mat/programčki/ničle.c | 128 | ||||
-rw-r--r-- | mat/programčki/ničle.mutex.c | 105 | ||||
-rw-r--r-- | mat/programčki/ničle.singlethreaded.c | 74 | ||||
-rw-r--r-- | mat/programčki/ničle.singlethreaded16bit.c | 114 | ||||
-rw-r--r-- | mat/programčki/ničle.wannabe-multithreaded.c | 92 |
5 files changed, 60 insertions, 453 deletions
diff --git a/mat/programčki/ničle.c b/mat/programčki/ničle.c index cf453d8..68f4142 100644 --- a/mat/programčki/ničle.c +++ b/mat/programčki/ničle.c @@ -1,6 +1,6 @@ #include <stdlib.h> // navdih za to je tedx predstavitev andreja bauerja z naslovom ničle -#include <stdio.h> // to je izris ničel littlewoodovih polinomov -#include <gsl/gsl_poly.h> // prevod: gcc -Wall -Wextra ničle.c -lgsl -lm -pthread +#include <stdio.h> // to je izris ničel littlewoodovih polinomov v manj kot 105 vrsticah +#include <gsl/gsl_poly.h> // prevod: gcc (-Ofast) -Wall -Wextra -pedantic -lgsl -lm ničle.c #include <sys/types.h> // program na poti "ime" izdela kvadratno PGM datoteko podane višine #include <sys/stat.h> // za nadaljno obdelavo je uporabno, če je širina liha; ni pa nujno #include <fcntl.h> // algoritem se da paralelizirati, ampak jaz imam samo en procesor @@ -8,98 +8,90 @@ #include <string.h> #include <unistd.h> #include <gsl/gsl_errno.h> -#include <pthread.h> -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 <math.h> +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; } diff --git a/mat/programčki/ničle.mutex.c b/mat/programčki/ničle.mutex.c deleted file mode 100644 index cf453d8..0000000 --- a/mat/programčki/ničle.mutex.c +++ /dev/null @@ -1,105 +0,0 @@ -#include <stdlib.h> // navdih za to je tedx predstavitev andreja bauerja z naslovom ničle -#include <stdio.h> // to je izris ničel littlewoodovih polinomov -#include <gsl/gsl_poly.h> // prevod: gcc -Wall -Wextra ničle.c -lgsl -lm -pthread -#include <sys/types.h> // program na poti "ime" izdela kvadratno PGM datoteko podane višine -#include <sys/stat.h> // za nadaljno obdelavo je uporabno, če je širina liha; ni pa nujno -#include <fcntl.h> // algoritem se da paralelizirati, ampak jaz imam samo en procesor -#include <sys/mman.h> // enotska krožnica je na četrtini podane širine -#include <string.h> -#include <unistd.h> -#include <gsl/gsl_errno.h> -#include <pthread.h> -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) { - *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"); - 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]; - if ((fd = open(argv[2], O_CREAT | O_RDWR, 00664)) == -1) { - perror("open"); - return 2; - } - if (ftruncate(fd, 128 + ši*ši*2) == -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) { - 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) (: - 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; - } - } -r: - if (munmap(p, 128 + ši*ši*2) == -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; -} diff --git a/mat/programčki/ničle.singlethreaded.c b/mat/programčki/ničle.singlethreaded.c deleted file mode 100644 index d2d1e0c..0000000 --- a/mat/programčki/ničle.singlethreaded.c +++ /dev/null @@ -1,74 +0,0 @@ -#include <stdlib.h> // navdih za to je tedx predstavitev andreja bauerja z naslovom ničle -#include <stdio.h> // to je izris ničel littlewoodovih polinomov v manj kot 105 vrsticah -#include <gsl/gsl_poly.h> // prevod: gcc -Wall -Wextra -pedantic -lgsl -lm ničle.c -#include <sys/types.h> // program na poti "ime" izdela kvadratno PGM datoteko podane višine -#include <sys/stat.h> // za nadaljno obdelavo je uporabno, če je širina liha; ni pa nujno -#include <fcntl.h> // algoritem se da paralelizirati, ampak jaz imam samo en procesor -#include <sys/mman.h> // enotska krožnica je na četrtini podane širine -#include <string.h> -#include <unistd.h> -#include <gsl/gsl_errno.h> -void pripravi_koeficiente (double * izhod, int številka) { - while (številka) { - *izhod++ = številka & 1 ? 1 : -1; - številka >>= 1; - } -} -int main (int argc, char ** argv) { - int izven_slike = 0; - int nekonvergiranih = 0; - if (argc != 1+3) { - fprintf(stderr, "uporaba: %s stopnja ime širina\n", argv[0] ? argv[0] : "ničle"); - return 1; - } - 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 + šir*šir) == -1) { - perror("ftruncate"); - if (close(fd) == -1) - perror("close"); - return 3; - } - void * p; - 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; - } - unsigned char * slika = (unsigned char *) p + 128; - memset(p, 0, 128 + šir*šir); - sprintf(p, "P5\n\n%59d\n%59d\n255\n", šir, šir); // precisely calculated with dc(1) (: - 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čer, 2n+0 so realni deli, 2n+1 pa imaginarni - gsl_set_error_handler_off(); - gsl_poly_complex_workspace * w = gsl_poly_complex_workspace_alloc(stopnja+1); - for (int i = 0; i < 1 << (stopnja+1); 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šina_na_sliki = šir/2 - ničle[j+1]*(šir/4); - int š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; - } - slika[šir*višina_na_sliki+širina_na_sliki]++; - } - } - 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 (izven slike)\n%d polinomov ni konvergiralo\n", - izven_slike, nekonvergiranih); - return 0; -} diff --git a/mat/programčki/ničle.singlethreaded16bit.c b/mat/programčki/ničle.singlethreaded16bit.c deleted file mode 100644 index eb1f672..0000000 --- a/mat/programčki/ničle.singlethreaded16bit.c +++ /dev/null @@ -1,114 +0,0 @@ -#include <stdlib.h> // navdih za to je tedx predstavitev andreja bauerja z naslovom ničle -#include <stdio.h> // to je izris ničel littlewoodovih polinomov v manj kot 105 vrsticah -#include <gsl/gsl_poly.h> // prevod: gcc -Wall -Wextra -pedantic -lgsl -lm ničle.c -#include <sys/types.h> // program na poti "ime" izdela kvadratno PGM datoteko podane višine -#include <sys/stat.h> // za nadaljno obdelavo je uporabno, če je širina liha; ni pa nujno -#include <fcntl.h> // algoritem se da paralelizirati, ampak jaz imam samo en procesor -#include <sys/mman.h> // enotska krožnica je na četrtini podane širine -#include <string.h> -#include <unistd.h> -#include <gsl/gsl_errno.h> -void pripravi_koeficiente (double * izhod, int številka, int koeficientov) { - while (koeficientov--) { - *izhod++ = številka & 1 ? 1 : -1; - številka >>= 1; - } -} -int main (int argc, char ** argv) { - int izven_slike = 0; - int nekonvergiranih = 0; - if (argc != 1+3) { - fprintf(stderr, "uporaba: %s stopnja ime širina\n", argv[0] ? argv[0] : "ničle"); - return 1; - } - 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 + šir*šir -#ifdef SESTNAJST - *2 -#endif - ) == -1) { - perror("ftruncate"); - if (close(fd) == -1) - perror("close"); - return 3; - } - void * p; - if ((p = mmap(NULL, 128+šir*šir -#ifdef SESTNAJST - *2 -#endif - , PROT_READ|PROT_WRITE, MAP_SHARED, fd, 0)) == MAP_FAILED) { - perror("mmap"); - if (close(fd) == -1) - perror("close"); - return 4; - } - unsigned char * slika = (unsigned char *) p + 128; - memset(p, 0, 128 + šir*šir -#ifdef SESTNAJST - *2 -#endif - ); -#ifdef SESTNAJST - sprintf(p, "P5\n\n%58lld\n%58lld\n65535\n", šir, šir); // precisely calculated with dc(1) (: -#else - sprintf(p, "P5\n\n%57lld\n%57lld\n255\n", šir, šir); -#endif - 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(); - 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 višina_na_sliki = šir/2 - ničle[j+1]*(šir/4); - int š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; - } -#ifdef SESTNAJST - slika[2*šir*višina_na_sliki+širina_na_sliki*2+1]++; - if (!slika[2*šir*višina_na_sliki+širina_na_sliki*2+1]) { - if (slika[2*šir*višina_na_sliki+širina_na_sliki*2] != 255) - slika[2*šir*višina_na_sliki+širina_na_sliki*2]++; - else - over++; - } -#else - if (slika[šir*višina_na_sliki+širina_na_sliki] == 255) - over++; - else - slika[šir*višina_na_sliki+širina_na_sliki]++; -#endif - } - } - fprintf(stderr, "\r KONČANO \n"); - gsl_poly_complex_workspace_free(w); - if (munmap(p, 128 + šir*šir -#ifdef SESTNAJST - *2 -#endif - ) == -1) - perror("munmap"); // nima smisla ukinjat programa, sistem si je sam kriv >:) - if (close(fd) == -1) - perror("close"); - 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; -} diff --git a/mat/programčki/ničle.wannabe-multithreaded.c b/mat/programčki/ničle.wannabe-multithreaded.c deleted file mode 100644 index 66954be..0000000 --- a/mat/programčki/ničle.wannabe-multithreaded.c +++ /dev/null @@ -1,92 +0,0 @@ -#include <stdlib.h> // navdih za to je tedx predstavitev andreja bauerja z naslovom ničle -#include <stdio.h> // to je izris ničel littlewoodovih polinomov -#include <gsl/gsl_poly.h> // prevod: gcc -Wall -Wextra ničle.c -lgsl -lm -pthread -#include <pthread.h> // program na poti "ime" izdela kvadratno PGM datoteko podane višine -#include <gsl/gsl_errno.h> // za nadaljno obdelavo je uporabno, če je širina liha; ni pa nujno -#include <string.h> // algoritem se da paralelizirati, ampak jaz imam samo en procesor -struct nit { // enotska krožnica je na četrtini podane širine - int začetek; - int konec; // nit, pomni, da računaš DO konca in konca ne računaš; hvala - unsigned int * platno; - pthread_t nit; - int stopnja; - int širina; -}; -void pripravi_koeficiente (double * izhod, int številka) { - while (številka) { - *izhod++ = številka & 1 ? 1 : -1; - številka >>= 1; - } -} -_Atomic unsigned long long int izvs = 0, nekonv = 0; -void * računaj (void * vhod) { - struct nit * nit = (struct nit *) vhod; - double koeficienti[nit->stopnja+1]; // kako prikladno! polinom nte stopnje ima n+1 členov - double ničle[2*nit->stopnja]; // ima pa n ničel, 2n so realni deli, 2n+1 pa imagin. - gsl_poly_complex_workspace * w = gsl_poly_complex_workspace_alloc(nit->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, nit->stopnja+1, w, ničle) != GSL_SUCCESS) - nekonv++; // uuu, lahko bi recimo narisali tiste, ki ne konver. - for (int j = 0; j < 2*nit->stopnja; j += 2) { - int višs = nit->širina/2 - ničle[j+1]*(nit->širina/4); - int širs = nit->širina/2 + ničle[j]*(nit->širina/4); - if (višs > nit->širina || širs > nit->širina || višs < 0 || širs < 0) { - izvs++; - continue; - } - nit->platno[nit->širina*višs+širs]++; - } - } - gsl_poly_complex_workspace_free(w); - return NULL; -} -int main (int argc, char ** argv) { - if (argc != 1+3) { - fprintf(stderr, "takole: %s stopnja širina niti\n", argv[0] ? argv[0] : "ničle"); - return 1; - } - int r = 0, zač = 0, stopnja = atoi(argv[1]), širina = atoi(argv[2]), šn = atoi(argv[3]); - gsl_set_error_handler_off(); - struct nit niti[šn]; - for (int i = 0; i < šn; i++) { - niti[i].začetek = zač; - niti[i].konec = (zač += ((1 << (stopnja+1))-1) / šn); - niti[i].stopnja = stopnja; - niti[i].širina = širina; - if (!(niti[i].platno = malloc(sizeof(*niti[i].platno)*širina*širina))) { - fprintf(stderr, "premalo delovnega spomina\n"); - return 2; - } - if ((r = pthread_create(&niti[i].nit, NULL, računaj, &niti[i]))) { - fprintf(stderr, "pthread_create: %s (%d)\n", strerror(r), r); - return 3; - } - } - for (int i = 0; i < šn; i++) { - if ((r = pthread_join(niti[i].nit, NULL))) { - fprintf(stderr, "pthread_join: %s (%d)\n", strerror(r), r); - return 4; - } - } - printf("P5 %d %d 256\n", širina, širina); - unsigned long long int over = 0; - for (int i = 0; i < širina*širina; i++) { - unsigned long long int sešt = 0; - for (int j = 0; j < šn; j++) - sešt += niti[j].platno[i]; - if (sešt > 65535) { - fputc(0xFF, stdout); - over++; - continue; - } - fputc(sešt >> 8, stdout); - fputc(sešt % 256, stdout); - } - for (int i = 0; i < šn; i++) { - free(niti[i].platno); - } - fprintf(stderr, "%llu ničel je izven 2+2i (izven slike)\n%llu polinomov ni konvergiralo\n" - "%llu vrednosti na sliki je preseglo najv. vrednost\n", izvs, nekonv, over); - return 0; -} |