a-conjecture-of-mine

An exercise on polyglossy: the same problem solved on multiple languages

commit bc43e41ee0117bb99f2b34880215a6d926164829
parent d7ba71e901322111ef30b6a4c62766c2a9a39c3f
Author: Gark Garcia <37553739+GarkGarcia@users.noreply.github.com>
Date:   Thu, 20 Jun 2019 20:10:14 -0300

Merge pull request #5 from Androthi/master

Implemented multi-threading in C
Diffstat:
MC/main.c | 128++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++-------------
1 file changed, 107 insertions(+), 21 deletions(-)
diff --git a/C/main.c b/C/main.c
@@ -1,13 +1,65 @@
 #include <stdlib.h>
 #include <stdio.h>
 #include <time.h>
+#include <pthread.h>
+
+// shenanigans to get system information
+#ifdef _WIN32
+#include <windows.h>
+#elif MACOS
+#include <sys/param.h>
+#include <sys/sysctl.h>
+#else
+#include <unistd.h>
+#endif
 
 // This program is a simple test for the following conjecture:
 
 // Let S: N -> N be the sum of the digits of a positive integer.
 // For all A and B in N, S(A + B) = S(A) + S(B) - 9k, where k is an integer.
 
-int sum_digits(unsigned n)
+int err = 0;     // global error condition
+int *sums_cache; // shared memory between threads
+
+// we need a memory structure to pass arguments to threads using the pthreads library
+struct start_max
+{
+    int start;
+    int max;
+};
+
+// find the number of processors on host machine
+int getNumberOfCores()
+{
+#ifdef WIN32
+    SYSTEM_INFO sysinfo;
+    GetSystemInfo(&sysinfo);
+    return sysinfo.dwNumberOfProcessors;
+#elif MACOS
+    int nm[2];
+    size_t len = 4;
+    uint32_t count;
+
+    nm[0] = CTL_HW;
+    nm[1] = HW_AVAILCPU;
+    sysctl(nm, 2, &count, &len, NULL, 0);
+
+    if (count < 1)
+    {
+        nm[1] = HW_NCPU;
+        sysctl(nm, 2, &count, &len, NULL, 0);
+        if (count < 1)
+        {
+            count = 1;
+        }
+    }
+    return count;
+#else
+    return sysconf(_SC_NPROCESSORS_ONLN);
+#endif
+}
+
+int get_sums(unsigned n)
 {
     int parc = n;
     int sum = 0;
@@ -17,43 +69,78 @@ int sum_digits(unsigned n)
         sum += parc % 10;
         parc /= 10;
     }
-
     return sum;
 }
 
+int getCounterExample_runner(struct start_max *s_m)
+{
+    for (int a = s_m->start; a <= s_m->max; a++)
+        for (int b = a; b <= s_m->max; b++)
+        {
+            if ((sums_cache[a + b] - (sums_cache[a] + sums_cache[b])) % 9 != 0)
+            {
+                printf("\nThe conjecture is disproved! Here's a counterexample: (%u, %u)", a, b);
+                err = 1;
+                return 1;
+            }
+        }
+    return 0;
+}
+
 int main()
 {
+
+    int i;
+    int num_threads = getNumberOfCores();
+    pthread_t thread_ids[num_threads];
+    struct start_max startMax[num_threads];
+    unsigned int MAX = 0;
+
     printf("\nThis program is a simple test for the following conjecture:\n");
     printf("Let S: N -> N be the sum of the digits of a positive integer.\n");
     printf("For all A and B in N, S(A + B) = S(A) + S(B) - 9k, where k is an integer.\n");
-    printf("\nWhat value would you like to test the conjecture for?");
+    printf("\nWhat value would you like to test the conjecture for? >");
 
-    unsigned MAX = 0;
     scanf_s("%u", &MAX);
 
-    printf("\nLOADING. . .");
+    printf("\nLOADING. . ");
     clock_t start = clock(), end;
 
-    int sums_c = 2 * (MAX + 1), *sums;
-    sums = malloc(sizeof(int) * sums_c);
-    for (int i = 0; i <= sums_c; i++)
-        sums[i] = sum_digits(i);
+    // create the sums_cache
+    int sums_c = 2 * (MAX + 1);
+    sums_cache = malloc(sizeof(int) * sums_c * 2); //original (sizeof(int)* sums_c) causing seg faults in multi-threading
+    for (i = 0; i <= sums_c; i++)
+        sums_cache[i] = get_sums(i);
 
-    for (int a = 0; a <= MAX; a++)
-        for (int b = a; b <= MAX; b++)
-            if ((sums[a + b] - (sums[a] + sums[b])) % 9 != 0)
-            {
-                end = clock();
-                printf("\nLOADED. . . in %ums [1 Thread]\n", (unsigned)((end - start) * 1000 / CLOCKS_PER_SEC));
-                printf("\nThe conjecture is disproved! Here's a counterexample: (%u, %u)", a, b);
+    // create the threads, divide the task into number of threads equivalent to number
+    // of cores on the host machine
 
-                return 0;
-            }
+    for (i = 0; i < num_threads; i++)
+    {
+        startMax[i].start = i * (MAX / num_threads);
+        startMax[i].max = startMax[i].start + (MAX / num_threads) - 1;
+        err = pthread_create(&thread_ids[i], NULL, getCounterExample_runner, &startMax[i]);
+        if (err)
+        {
+            printf("unable to create thread : %d", err);
+        }
+    }
 
+    for (i = 0; i < num_threads; i++)
+    {
+        err = pthread_join(thread_ids[i], NULL);
+        if (err)
+        {
+            printf("unable to join threads :%d\n", err);
+        }
+    }
+
+    if (err)
+        return 1;
 
     end = clock();
-    printf("\nLOADED. . . in %ums\n", (unsigned)((end - start) * 1000 / CLOCKS_PER_SEC));
+    printf("\nLOADED. .%d Threads . in %ums\n", num_threads, (unsigned)((end - start) * 1000 / CLOCKS_PER_SEC));
     printf("\nThe conjecture is proved for all natural numbers smaller or equals to %u!", MAX);
 
     return 0;
-}-
\ No newline at end of file
+}