Guest User

PSE Pre-alpha calculator (parallel)

a guest
Apr 6th, 2017
79
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1.  
  2. #include <stdlib.h>
  3. #include <stdio.h>
  4. #include <stdint.h>
  5. #include <ctype.h>
  6.  
  7. #include <omp.h>
  8.  
  9. #define BITS (1u << 20)
  10. #define MAX (BITS * 8)
  11.  
  12. #define LEN 14
  13.  
  14.  
  15.  
  16. static int64_t eval(const char *str, int n)
  17. {
  18.     const char *end = str + n;
  19.     int64_t res = 0;
  20.     int op= '+';
  21.    
  22.     while (str < end) {
  23.         int64_t x = 0;
  24.        
  25.         while (str < end && isdigit(*str)) {
  26.             x = x * 10 + *str++ - '0';
  27.         }
  28.        
  29.         switch (op) {
  30.             case '+':   res += x; break;
  31.             case '-':   res -= x; break;
  32.             case '*':   res *= x; break;
  33.             case '/':   if (x == 0) return -1;
  34.                         if (res % x) return -1;
  35.                         res /= x; break;
  36.         }
  37.        
  38.         if (res == 0) return -1;
  39.        
  40.         op = *str++;
  41.     }
  42.    
  43.     if (res < 0 || res >= MAX) return -1;    
  44.     return res;
  45. }
  46.  
  47. static void swap(char *str, int i, int j)
  48. {
  49.     char s = str[i]; str[i] = str[j]; str[j] = s;
  50. }
  51.  
  52. static void permute(char *str, int n, uint8_t *set)
  53. {
  54.     int op = !isdigit(str[n - 1]);
  55.     int i;
  56.    
  57.     if (!op) {
  58.         int64_t e = eval(str, n);
  59.        
  60.         if (e >= 0) {
  61.             int m = e / 8;
  62.             int j = e % 8;
  63.  
  64.             if ((set[m] & (1u << j)) == 0) {
  65.                 if (0 && n < 5000000) printf("%ld == %.*s\n", e, n, str);
  66.                 set[m] |= (1u << j);
  67.             }
  68.         }
  69.     }
  70.  
  71.     for (i = n; i < LEN; i++) {
  72.         if (!op || isdigit(str[i])) {
  73.             if (op && str[i] == '0') continue;
  74.  
  75.             swap(str, i, n);
  76.             permute(str, n + 1, set);
  77.             swap(str, i, n);
  78.         }
  79.     }
  80. }
  81.  
  82. int main(void)
  83. {
  84.     int mthread = omp_get_max_threads();
  85.     uint8_t *set[mthread];
  86.     int m = 0;
  87.     int i;
  88.    
  89.     fprintf(stderr, "Maximum number of threads: %d\n", mthread);
  90.    
  91.     for (i = 0; i < mthread; i++) set[i] = NULL;
  92.  
  93.     #pragma omp parallel
  94.     {
  95.         int nthread = omp_get_num_threads();
  96.         int ithread = omp_get_thread_num();
  97.         int n;
  98.  
  99.         set[ithread] = calloc(1, BITS);
  100.         set[ithread][0] = 1;
  101.  
  102.         #pragma omp for
  103.         for (n = 0; n < 9 * 13; n++) {
  104.             char pool[] = "0123456789+-*/";
  105.  
  106.             swap(pool, 0, 1 + n / 13);
  107.             swap(pool, 1, 1 + n % 13);
  108.  
  109.             fprintf(stderr,
  110.                 "Exploring %c%c... on thread %d/%d.\n",
  111.                 pool[0], pool[1], ithread, nthread);
  112.  
  113.             permute(pool, 2, set[ithread]);
  114.         }
  115.     }
  116.    
  117.     {    
  118.         int nthread = 0;
  119.        
  120.         while (nthread < mthread && set[nthread]) nthread++;
  121.  
  122.         for (i = 0; i < BITS; i++) {
  123.             uint8_t mask = 0u;
  124.             int k;
  125.  
  126.             for (k = 0; k < nthread; k++) {
  127.                 mask |= set[k][i];
  128.             }
  129.  
  130.             for (k = 0; k < 8; k++) {
  131.                 if ((mask & (1u << k)) == 0) {
  132.                     printf("%d\n", m);
  133.                 }
  134.                 m++;
  135.             }
  136.  
  137.             if (m >= 5000000) break;
  138.         }
  139.  
  140.         for (i = 0; i < nthread; i++) free(set[i]);
  141.     }
  142.    
  143.    
  144.     return 0;
  145. }
RAW Paste Data