From bee4ee51702eb0fe54531ae8ab43faf05d624082 Mon Sep 17 00:00:00 2001 From: Hector Colon Date: Fri, 6 Aug 2021 23:18:00 -0400 Subject: [PATCH] init --- mper_gmp.c | 122 ++++++++++++++++++++++++++++++++++++++++++++ proth.c | 141 +++++++++++++++++++++++++++++++++++++++++++++++++++ proth_test.c | 35 +++++++++++++ 3 files changed, 298 insertions(+) create mode 100755 mper_gmp.c create mode 100755 proth.c create mode 100755 proth_test.c diff --git a/mper_gmp.c b/mper_gmp.c new file mode 100755 index 0000000..042fccc --- /dev/null +++ b/mper_gmp.c @@ -0,0 +1,122 @@ +#include +#include +#include +#include +#include + +#include + +#define NUM_DIGITS 1024 + +void mpz_mper(mpz_t num); + +bool inc_mper(char *num); + +char tmp_buf[NUM_DIGITS] = ""; + +uint64_t count = 0; +uint64_t best_count = 0; + +uint64_t digit_best_count = 0; //what the best is +mpz_t digit_count; //how many times we've hit the best + +clock_t start; + +int main(void) +{ + char guess[NUM_DIGITS] = "01"; + mpz_t ans; + mpz_init(ans); + mpz_init(digit_count); + + start = clock(); + + do + { + count = 0; + mpz_set_str(ans, guess, 10); + + while(mpz_cmp_ui(ans, 9) > 0) + { + mpz_mper(ans); + ++count; + } + + if(count > best_count) + { + clock_t found = clock(); + double time_spent = (double)(found - start) / CLOCKS_PER_SEC; + best_count = count; + printf("(%f)\t%lu steps: %s <------\n", time_spent, count, guess); + } + + if (count > digit_best_count) + { + digit_best_count = count; + mpz_set_ui(digit_count, 1); + } + else if(count == digit_best_count) + { + mpz_add_ui(digit_count, digit_count, 1); + } + }while(inc_mper(guess)); +} + +void mpz_mper(mpz_t num) +{ + int sz = gmp_snprintf(tmp_buf, NUM_DIGITS, "%Zd", num); + + if(sz >= NUM_DIGITS) + { + printf("\n=== can't fit num in tmp_buf! ===\n\n"); + return; + } + + mpz_set_ui(num, 1); + + uint_fast16_t i = 0; + while(tmp_buf[i] != '\0') + { + mpz_mul_ui(num, num, tmp_buf[i] - 0x30); + ++i; + } +} + + +bool inc_mper(char *num) +{ + uint_fast16_t i = 0; + + while(num[i] == '9') + { + ++i; + + if(i >= NUM_DIGITS) + { + printf("\n=== ran out of digits ===\n\n"); + return false; + } + } + + if(num[i] == '\0') + { + clock_t found = clock(); + double time_spent = (double)(found - start) / CLOCKS_PER_SEC; + //printf("(%f)\t%lu digits best: %u\n", time_spent, i+1, best_count); + + gmp_printf("(%f) finished %lu digits. %Zd nums with count: %lu\n", time_spent, i, digit_count, digit_best_count); + mpz_set_ui(digit_count, 0); + digit_best_count = 0; + + num[i] = '1'; + } + + char new_num = ++num[i]; + while(i) + { + --i; + num[i] = new_num; + } + + return true; +} diff --git a/proth.c b/proth.c new file mode 100755 index 0000000..54e2059 --- /dev/null +++ b/proth.c @@ -0,0 +1,141 @@ +#include +#include +#include +#include +#include + +#include + + +bool is_prime(mpz_t p); +bool is_prime2(mpz_t p); + +clock_t start; + + +//ints for is_prime test +mpz_t t_exp; +mpz_t t_p1; +mpz_t t_p2; +mpz_t t_p3; +mpz_t t; + + +int main(void) +{ + mpz_t exp; + mpz_t p; + mpz_t k; + mpz_t base; + + mpz_init(p); + + mpz_init(k); + mpz_init(exp); + mpz_init(base); + + mpz_init(t_exp); + mpz_init(t_p1); + mpz_init(t_p2); + mpz_init(t_p3); + mpz_init(t); + + //first 3 primes + mpz_set_ui(t_p1, 2); + mpz_set_ui(t_p2, 3); + mpz_set_ui(t_p3, 5); + + //start = clock(); + + + //proth number is k*2^n+1 + //check where k is 19 + mpz_set_ui(k, 46157); + + //calc 2^n + mpz_set_ui(base, 2); + + for(unsigned long int n = 698200; ; n++) + { + mpz_pow_ui(exp, base, n); + + //p=k*2^n + mpz_mul(p, k, exp); + //p+=1 + mpz_add_ui(p, p, 1); + + gmp_printf("(n=%d)\n%Zd\n\n", n, p); + if(is_prime2(p) == true) + { + printf(" <--- prime\n"); + return 1; + } + printf("\n"); + } + + //free p + mpz_clear(p); +} + +bool is_prime(mpz_t p) +{ + //exponent is (p-1)/2 + //printf("exp\n"); + mpz_sub_ui(t_exp, p, 1); + mpz_divexact_ui(t_exp, t_exp, 2); + unsigned long int ui_exp = mpz_get_ui(t_exp); + + //printf("pow1\n"); + mpz_pow_ui(t, t_p1, ui_exp); + mpz_add_ui(t, t, 1); + //printf("div1\n"); + if(mpz_divisible_p(t, p) != 0) + return true; + + //printf("pow2\n"); + mpz_pow_ui(t, t_p2, ui_exp); + mpz_add_ui(t, t, 1); + //printf("div2\n"); + if(mpz_divisible_p(t, p) != 0) + return true; + + //printf("pow3\n"); + mpz_pow_ui(t, t_p3, ui_exp); + mpz_add_ui(t, t, 1); + //printf("div3\n"); + if(mpz_divisible_p(t, p) != 0) + return true; + + return false; +} + +bool is_prime2(mpz_t p) +{ + //exponent is (p-1)/2 + printf("exp\n"); + mpz_sub_ui(t_exp, p, 1); + mpz_divexact_ui(t_exp, t_exp, 2); + + printf("pow1\n"); + mpz_powm(t, t_p1, t_exp, p); + mpz_add_ui(t, t, 1); + printf("cmp1\n"); + if(mpz_cmp(t, p) == 0) + return true; + + printf("pow2\n"); + mpz_powm(t, t_p2, t_exp, p); + mpz_add_ui(t, t, 1); + printf("cmp2\n"); + if(mpz_cmp(t, p) == 0) + return true; + + printf("pow3\n"); + mpz_powm(t, t_p3, t_exp, p); + mpz_add_ui(t, t, 1); + printf("cmp3\n"); + if(mpz_cmp(t, p) == 0) + return true; + + return false; +} diff --git a/proth_test.c b/proth_test.c new file mode 100755 index 0000000..d4f36ca --- /dev/null +++ b/proth_test.c @@ -0,0 +1,35 @@ +#include +#include +#include +#include +#include + +#include + + + +int main(void) +{ + mpz_t p; + mpz_t exp; + mpz_t base; + mpz_t rop; + + mpz_init(p); + mpz_init(exp); + mpz_init(base); + mpz_init(rop); + + mpz_set_ui(base, 5); + mpz_set_ui(exp, (13-1)/2); + mpz_set_ui(p, 13); + + mpz_powm(rop, base, exp, p); + + gmp_printf("%Zd\n", rop); + + mpz_clear(p); + mpz_clear(exp); + mpz_clear(base); + mpz_clear(rop); +} -- 2.17.1