From 7fc3a441430d1a9a2faa4360a6f45ad5ad2b66eb Mon Sep 17 00:00:00 2001 From: Hector Colon Date: Wed, 6 Oct 2021 17:58:21 -0400 Subject: [PATCH] made it multi-thread --- proth.c | 149 ++++++++++++++++++++++++++++++++++++++------------------ 1 file changed, 101 insertions(+), 48 deletions(-) diff --git a/proth.c b/proth.c index 65867c8..5bc895a 100755 --- a/proth.c +++ b/proth.c @@ -2,6 +2,7 @@ #include #include +#include #include #include @@ -11,113 +12,166 @@ //#define N_CONST 44200000 /* recent find (k=46157, n=698207)*/ -//#define K_CONST 46157 -//#define N_CONST 698206 +#define K_CONST 46157 +#define N_CONST 698203 /* searching for k=301, n=7360 */ -#define K_CONST 301 -#define N_CONST 6500 +//#define K_CONST 301 +//#define N_CONST 6500 -mpz_t t_exp; -mpz_t t_p1; -mpz_t t_p2; -mpz_t t_p3; -mpz_t t; +#define NUM_CORES 6 -time_t start; -time_t end; +static void * proth_thread(void *arg); + +//mutex protected, thread safe n +unsigned long int n_val = N_CONST; +pthread_mutex_t n_lock; +pthread_mutex_t found_lock; int main(void) { + time_t start; + time_t end; time(&start); - mpz_t exp; - mpz_t p; - mpz_t k; - mpz_t base; + //array to keep track of the thread id's + pthread_t thread_ids[NUM_CORES]; - mpz_init(p); + //create the mutexes + pthread_mutex_init(&n_lock, NULL); + pthread_mutex_init(&found_lock, NULL); - mpz_init(k); - mpz_init(exp); - mpz_init(base); + //create the threads + for(int i = 0; i < NUM_CORES; i++) + { + pthread_create(&thread_ids[i], NULL, &proth_thread, NULL); + } + + //lock main thread until prime is found + pthread_mutex_lock(&found_lock); + pthread_mutex_lock(&found_lock); + + //destroy the threads + for(int i = 0; i < NUM_CORES; i++) + { + pthread_cancel(thread_ids[i]); + } + + //destroy the mutexes + pthread_mutex_destroy(&n_lock); + pthread_mutex_destroy(&found_lock); + + time(&end); + printf("total time: %f seconds\n", difftime(end, start)); +} + +unsigned long get_n() +{ + pthread_mutex_lock(&n_lock); + unsigned long n = n_val; + n_val++; + pthread_mutex_unlock(&n_lock); + return n; +} + +static void * proth_thread(void *arg) +{ + // variables to test the primality + mpz_t t; + mpz_t t_exp; + mpz_t t_p1; + mpz_t t_p2; + mpz_t t_p3; + mpz_init(t); mpz_init(t_exp); mpz_init(t_p1); mpz_init(t_p2); mpz_init(t_p3); - mpz_init(t); + + // variables to calculate the proth number p=k*2^n+1 + mpz_t proth; //the proth number + mpz_t p_minus1; // proth number minus 1 + mpz_t k; // k + mpz_t two; // 2 + mpz_t two_n; //2^n + + mpz_init(proth); + mpz_init(p_minus1); + mpz_init(k); + mpz_init(two); + mpz_init(two_n); //first 3 primes mpz_set_ui(t_p1, 2); mpz_set_ui(t_p2, 3); mpz_set_ui(t_p3, 5); - //proth number is k*2^n+1 + //proth number is p=k*2^n+1 mpz_set_ui(k, K_CONST); - //two is our base - mpz_set_ui(base, 2); + //two=2 + mpz_set_ui(two, 2); + + unsigned long int n; - unsigned long int n = N_CONST; while (1) { + //get the thread-safe n + n = get_n(); printf("(n=%llu)\n", n); - //calc 2^n - mpz_pow_ui(exp, base, n); + //calc exp=2^n + mpz_pow_ui(two_n, two, n); + //calc p=k*2^n + mpz_mul(p_minus1, k, two_n); + //calc p=k*2^n+1 (this is our proth number) + mpz_add_ui(proth, p_minus1, 1); - //p=k*2^n - mpz_mul(p, k, exp); - //p+=1 - mpz_add_ui(p, p, 1); - - //prime check exponent is (p-1)/2 - mpz_sub_ui(t_exp, p, 1); - mpz_divexact_ui(t_exp, t_exp, 2); + //the prime check exponent is (p-1)/2 + //mpz_sub_ui(t_exp, p, 1); + mpz_divexact_ui(t_exp, p_minus1, 2); //printf("prime check a=2\n"); - mpz_powm(t, t_p1, t_exp, p); + mpz_powm(t, t_p1, t_exp, proth); mpz_add_ui(t, t, 1); //printf("cmp1\n"); - if(mpz_cmp(t, p) == 0) + if(mpz_cmp(t, proth) == 0) { printf("prime with a=2!\n"); break; } //printf("prime check a=3\n"); - mpz_powm(t, t_p2, t_exp, p); + mpz_powm(t, t_p2, t_exp, proth); mpz_add_ui(t, t, 1); //printf("cmp2\n"); - if(mpz_cmp(t, p) == 0) + if(mpz_cmp(t, proth) == 0) { printf("prime with a=3!\n"); break; } //printf("prime check a=5\n"); - mpz_powm(t, t_p3, t_exp, p); + mpz_powm(t, t_p3, t_exp, proth); mpz_add_ui(t, t, 1); //printf("cmp3\n"); - if(mpz_cmp(t, p) == 0) + if(mpz_cmp(t, proth) == 0) { printf("prime with a=5!\n"); break; } - - n++; } //proth number is k*2^n+1 gmp_printf("%Zd*2^%llu+1 is prime!\n", k, n); //free - mpz_clear(p); - + mpz_clear(proth); + mpz_init(p_minus1); mpz_clear(k); - mpz_clear(exp); - mpz_clear(base); + mpz_clear(two); + mpz_clear(two_n); mpz_clear(t_exp); mpz_clear(t_p1); @@ -125,6 +179,5 @@ int main(void) mpz_clear(t_p3); mpz_clear(t); - time(&end); - printf("total time: %f seconds\n", difftime(end, start)); + pthread_mutex_unlock(&found_lock); } -- 2.17.1