Il 2020-03-23 22:38 Marco Bodrato ha scritto:
Using unsigned long to compute the modulus is obviously faster than
many calls to mpz_cdiv_ui. I tried a patch that surely is not as fast
as yours, but should speed-up all numbers that fits in a single
unsigned long. The speed-up seems small, I'm not sure it's worth.
... it is not very interesting, but I attach the patch I wrote.
Ĝis,
m
diff -r a7836288d2c0 mpz/nextprime.c
--- a/mpz/nextprime.c Fri Mar 20 16:19:07 2020 +0100
+++ b/mpz/nextprime.c Mon Mar 23 22:39:43 2020 +0100
@@ -202,6 +202,29 @@
memset (composite, 0, odds_in_composite_sieve);
prime = 3;
+ if (mpz_fits_ulong_p (p))
+ {
+ unsigned long p0 = mpz_get_ui (p);
+
+ for (i = 0; i < prime_limit; i++)
+ {
+ m = p0 % prime;
+ /* Only care about odd multiplies of prime. */
+ if (m & 1)
+ m = (prime - m) >> 1;
+ else
+ {
+ composite[0] |= m == 0;
+ m = prime - (m >> 1);
+ }
+
+ /* Mark off any composites in sieve */
+ for (; m < odds_in_composite_sieve; m += prime)
+ composite[m] = 1;
+ prime += primegap[i];
+ }
+ }
+ else
for (i = 0; i < prime_limit; i++)
{
m = mpz_cdiv_ui(p, prime);
_______________________________________________
gmp-devel mailing list
gmp-devel@gmplib.org
https://gmplib.org/mailman/listinfo/gmp-devel
