mper_gmp.c

   1 #include <time.h>
   2 #include <stdio.h>
   3 #include <string.h>
   4 #include <stdint.h>
   5 #include <stdbool.h>
   6
   7 #include <gmp.h>
   8
   9 #define NUM_DIGITS 1024
  10
  11 void mpz_mper(mpz_t num);
  12
  13 bool inc_mper(char *num);
  14
  15 char tmp_buf[NUM_DIGITS] = "";
  16
  17 uint64_t count = 0;
  18 uint64_t best_count = 0;
  19
  20 uint64_t digit_best_count = 0; //what the best is
  21 mpz_t digit_count; //how many times we've hit the best
  22
  23 clock_t start;
  24
  25 int main(void)
  26 {
  27     char guess[NUM_DIGITS] = "01";
  28     mpz_t ans;
  29     mpz_init(ans);
  30     mpz_init(digit_count);
  31
  32     start = clock();
  33
  34     do
  35     {
  36         count = 0;
  37         mpz_set_str(ans, guess, 10);
  38
  39         while(mpz_cmp_ui(ans, 9) > 0)
  40         {
  41             mpz_mper(ans);
  42             ++count;
  43         }
  44
  45         if(count > best_count)
  46         {
  47             clock_t found = clock();
  48             double time_spent = (double)(found - start) / CLOCKS_PER_SEC;
  49             best_count = count;
  50             printf("(%f)\t%lu steps: %s  <------\n", time_spent, count, guess);
  51         }
  52
  53         if (count > digit_best_count)
  54         {
  55             digit_best_count = count;
  56             mpz_set_ui(digit_count, 1);
  57         }
  58         else if(count == digit_best_count)
  59         {
  60             mpz_add_ui(digit_count, digit_count, 1);
  61         }
  62     }while(inc_mper(guess));
  63 }
  64
  65 void mpz_mper(mpz_t num)
  66 {
  67     int sz = gmp_snprintf(tmp_buf, NUM_DIGITS, "%Zd", num);
  68
  69     if(sz >= NUM_DIGITS)
  70     {
  71         printf("\n=== can't fit num in tmp_buf! ===\n\n");
  72         return;
  73     }
  74
  75     mpz_set_ui(num, 1);
  76
  77     uint_fast16_t i = 0;
  78     while(tmp_buf[i] != '\0')
  79     {
  80         mpz_mul_ui(num, num, tmp_buf[i] - 0x30);
  81         ++i;
  82     }
  83 }
  84
  85
  86 bool inc_mper(char *num)
  87 {
  88     uint_fast16_t i = 0;
  89
  90     while(num[i] == '9')
  91     {
  92         ++i;
  93
  94         if(i >= NUM_DIGITS)
  95         {
  96             printf("\n=== ran out of digits ===\n\n");
  97             return false;
  98         }
  99     }
 100
 101     if(num[i] == '\0')
 102     {
 103         clock_t found = clock();
 104         double time_spent = (double)(found - start) / CLOCKS_PER_SEC;
 105         //printf("(%f)\t%lu digits best: %u\n", time_spent, i+1, best_count);
 106
 107         gmp_printf("(%f) finished %lu digits. %Zd nums with count: %lu\n", time_spent, i, digit_count, digit_best_count);
 108         mpz_set_ui(digit_count, 0);
 109         digit_best_count = 0;
 110
 111         num[i] = '1';
 112     }
 113
 114     char new_num = ++num[i];
 115     while(i)
 116     {
 117         --i;
 118         num[i] = new_num;
 119     }
 120
 121     return true;
 122 }