20211113, 20:46  #23 
Mar 2016
567_{8} Posts 

20211113, 21:50  #24 
Sep 2002
Database er0rr
2×3^{2}×13×17 Posts 
Here is my solution written in C
Code:
#include <gmp.h> #include <stdio.h> #include <stdlib.h> void mpz_mod_mp (mpz_t r, mpz_t a, mp_bitcnt_t p) { // assumed that r is initialized and a is expendable do { mpz_fdiv_r_2exp(r, a, p); mpz_fdiv_q_2exp(a, a, p); mpz_add(r, r, a); } while (mpz_sizeinbase(r, 2) > p); } int main() { mpz_t r, a, f; mp_bitcnt_t p; mpz_init(r); mpz_init(a); mpz_init(f); p=137; printf("%d is exponent.\n",p); mpz_set_ui(f, 1); mpz_mul_2exp(f, f, p); mpz_sub_ui(f, f, 1); printf("Mp is "); mpz_out_str(stdout, 10, f); printf(".\n"); mpz_set_str(a,"10584739298444444444444444444409185657387898722659423897260",10); printf("a is "); mpz_out_str(stdout, 10, a); printf(".\n"); mpz_mod(r, a, f); printf("Result inbuilt is "); mpz_out_str(stdout, 10, r); printf(".\n"); mpz_mod_mp(r, a, p); // a was changed by mpz_mod_mp!! printf("Result written is "); mpz_out_str(stdout, 10, r); printf(".\n"); } Last fiddled with by paulunderwood on 20211113 at 22:17 
20211113, 22:24  #25 
Mar 2016
3×5^{3} Posts 
In gmp I could use the same mpz_t variable A like mpz_mod (A, A, f);
I tried to write a function like this mpz_mod_mp (A, A, Mp), therefore I initialized a help variable. Thanks for your patience. 
20211113, 22:47  #26  
Sep 2002
Database er0rr
2×3^{2}×13×17 Posts 
Quote:
Code:
void mpz_mod_mp (mpz_t r, mpz_t A, mp_bitcnt_t p) { mpz_t a; mpz_init_set(a, A); do { mpz_fdiv_r_2exp(r, a, p); mpz_fdiv_q_2exp(a, a, p); mpz_add(r, r, a); } while (mpz_sizeinbase(r, 2) > p); mpz_clear(a); } Last fiddled with by paulunderwood on 20211113 at 23:08 

20211115, 17:33  #27 
Mar 2016
101110111_{2} Posts 
Something is boogie:
I used my variable a and put it in your solution: Result is wrong: 137 is exponent. Mp is 174224571863520493293247799005065324265471. a is 15580960185386716076816921462913615019618152413172348145118933359820136234923109492. Result inbuilt is 10584739298409185657387898722659423897260. Result written is 89430325577680987480245132687307139815991. 
20211115, 21:28  #28  
"Robert Gerbicz"
Oct 2005
Hungary
2×3^{2}×5×17 Posts 
Quote:
Code:
void mpz_mod_mp (mpz_ptr r, mpz_ptr a, mp_bitcnt_t p) {// the result is r=a%(2^p1) mpz_t tmp; mpz_init(tmp); mpz_set(r,a); do { mpz_fdiv_r_2exp(tmp, r, p); mpz_fdiv_q_2exp(r, r, p); mpz_add(r, r, tmp); } while (mpz_sizeinbase(r, 2) > p); mpz_clear(tmp); } Last fiddled with by R. Gerbicz on 20211115 at 21:37 Reason: corrected the code. 

20211126, 04:03  #29 
"Alexander"
Nov 2008
The Alamo City
308_{16} Posts 
mpz_t is formally defined in gmp.h as a typedef for an array of exactly one __mpz_struct internal struct, so it's implicitly a pointer.
By the way, note to mods, this is a programming thread in the Math forum. 
20211126, 05:05  #30  
Sep 2002
Database er0rr
2·3^{2}·13·17 Posts 
Quoting the excellent GMP website documentation:
Quote:
Bernhard should think of these artifacts as a "feature". For example, if he is taking GCDs then there is no problem. For extra speed, I would shift Mp left to the word boundary and calculate at the word level, before any necessary dropdowns to the bit level. A sample program using the "word level" logic is attached. The "adjustment" might need some tweaking to account for the sign bit. Last fiddled with by paulunderwood on 20211126 at 19:43 

20211126, 19:47  #31  
Sep 2002
Database er0rr
2×3^{2}×13×17 Posts 
Quote:
Here is the updated code. Last fiddled with by paulunderwood on 20211126 at 19:55 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Factorial modulo a prime  axn  Computer Science & Computational Number Theory  66  20110901 21:55 
modulo operation for polynomials?  smslca  Math  3  20110418 17:18 
Order of 3 modulo a Mersenne prime  T.Rex  Math  7  20090313 10:46 
N! modulo for large N  Cyclamen Persicum  Math  2  20031210 10:52 
The modulo operation, how is it computed?  eepiccolo  Math  7  20030108 03:07 