From 7f8d80fc2f1eeb9b3c741592ba0062c60642110e Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Anton=20Luka=20=C5=A0ijanec?= Date: Sun, 1 May 2022 02:29:54 +0200 Subject: =?UTF-8?q?ni=C3=A7le?= MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit --- "mat/program\304\215ki/.gitignore" | 2 + "mat/program\304\215ki/ni\304\215le.c" | 105 +++++++++++++++++++++ "mat/program\304\215ki/ni\304\215le.mutex.c" | 105 +++++++++++++++++++++ .../ni\304\215le.singlethreaded.c" | 74 +++++++++++++++ .../ni\304\215le.singlethreaded16bit.c" | 82 ++++++++++++++++ .../ni\304\215le.wannabe-multithreaded.c" | 92 ++++++++++++++++++ 6 files changed, 460 insertions(+) create mode 100644 "mat/program\304\215ki/.gitignore" create mode 100644 "mat/program\304\215ki/ni\304\215le.c" create mode 100644 "mat/program\304\215ki/ni\304\215le.mutex.c" create mode 100644 "mat/program\304\215ki/ni\304\215le.singlethreaded.c" create mode 100644 "mat/program\304\215ki/ni\304\215le.singlethreaded16bit.c" create mode 100644 "mat/program\304\215ki/ni\304\215le.wannabe-multithreaded.c" (limited to 'mat/programčki') diff --git "a/mat/program\304\215ki/.gitignore" "b/mat/program\304\215ki/.gitignore" new file mode 100644 index 0000000..1442e15 --- /dev/null +++ "b/mat/program\304\215ki/.gitignore" @@ -0,0 +1,2 @@ +*.pgm +*.png diff --git "a/mat/program\304\215ki/ni\304\215le.c" "b/mat/program\304\215ki/ni\304\215le.c" new file mode 100644 index 0000000..cf453d8 --- /dev/null +++ "b/mat/program\304\215ki/ni\304\215le.c" @@ -0,0 +1,105 @@ +#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 // 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 +#include // enotska krožnica je na četrtini podane širine +#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) { + *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\304\215ki/ni\304\215le.mutex.c" "b/mat/program\304\215ki/ni\304\215le.mutex.c" new file mode 100644 index 0000000..cf453d8 --- /dev/null +++ "b/mat/program\304\215ki/ni\304\215le.mutex.c" @@ -0,0 +1,105 @@ +#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 // 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 +#include // enotska krožnica je na četrtini podane širine +#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) { + *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\304\215ki/ni\304\215le.singlethreaded.c" "b/mat/program\304\215ki/ni\304\215le.singlethreaded.c" new file mode 100644 index 0000000..d2d1e0c --- /dev/null +++ "b/mat/program\304\215ki/ni\304\215le.singlethreaded.c" @@ -0,0 +1,74 @@ +#include // navdih za to je tedx predstavitev andreja bauerja z naslovom ničle +#include // to je izris ničel littlewoodovih polinomov v manj kot 105 vrsticah +#include // prevod: gcc -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 +#include // enotska krožnica je na četrtini podane širine +#include +#include +#include +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\304\215ki/ni\304\215le.singlethreaded16bit.c" "b/mat/program\304\215ki/ni\304\215le.singlethreaded16bit.c" new file mode 100644 index 0000000..2412a1a --- /dev/null +++ "b/mat/program\304\215ki/ni\304\215le.singlethreaded16bit.c" @@ -0,0 +1,82 @@ +#include // navdih za to je tedx predstavitev andreja bauerja z naslovom ničle +#include // to je izris ničel littlewoodovih polinomov v manj kot 105 vrsticah +#include // prevod: gcc -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 +#include // enotska krožnica je na četrtini podane širine +#include +#include +#include +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*2) == -1) { + perror("ftruncate"); + if (close(fd) == -1) + perror("close"); + return 3; + } + void * p; + if ((p = mmap(NULL, 128+šir*šir*2, 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*2); + sprintf(p, "P5\n\n%58d\n%58d\n65535\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); + int prej_izpisano = 6969; + for (int i = 0; i < 1 << (stopnja+1); i++) { + if (prej_izpisano != i*1000/(1 << (stopnja+1))) { + prej_izpisano = i*1000/(1 << (stopnja+1)); + fprintf(stderr, "\rRačunam in rišem ničle: %d promilov", prej_izpisano); + } + 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[2*šir*višina_na_sliki+širina_na_sliki*2+1]++; + if (!slika[1*šir*višina_na_sliki+širina_na_sliki*2+1]) + slika[2*šir*višina_na_sliki+širina_na_sliki*2]++; + } + } + 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 (izven slike)\n%d polinomov ni konvergiralo\n", + izven_slike, nekonvergiranih); + return 0; +} diff --git "a/mat/program\304\215ki/ni\304\215le.wannabe-multithreaded.c" "b/mat/program\304\215ki/ni\304\215le.wannabe-multithreaded.c" new file mode 100644 index 0000000..66954be --- /dev/null +++ "b/mat/program\304\215ki/ni\304\215le.wannabe-multithreaded.c" @@ -0,0 +1,92 @@ +#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 // 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 +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; +} -- cgit v1.2.3