Il 2020-03-24 01:10 Seth Troisi ha scritto:
(I'm don't think your ulong patch is needed but I can measure at a
It's a small patch, but the speed-up it gives is probably too small to
be worth adding.
My code doesn't use a sieve (and instead checks each number for
divisors similar to the old code) because the average gap for small
numbers is small 300000 / primepi(300000) = 11
There is a small error in the code, it does not handle negative numbers
correctly.
For each divisor your code uses two operations, a product (prime*prime)
and a remainder (t % prime). On many architectures computing t/prime and
t%prime cost just one operation... that's why I'd use the ideas Torbjorn
used in isprime() in dumbmp.c,
https://gmplib.org/repo/gmp/rev/7524222ab7d4 currently in bootstrap.c .
I propose a variation of your patch, you find it attached, on my
computer it's faster.
Because the measured threshold for this was much larger (~80 million),
it might actually make sense to use a sieve after some threshold
If you think that's a 1.5-3x speedup for inputs 16-30bits is important
I can try to dynamically generate a longer list of primes
If writing the code is not too complex, it may be interesting to test if
it is worth.
On Mon, Mar 23, 2020 at 2:38 PM Marco Bodrato
<bodr...@mail.dm.unipi.it> wrote:
It might also be useful to commit tune_nextprime_small which
dynamically selects a higher reps count for
mpz_nextprime input and helps increase precision.
Uhm...
j = 200000 / s->size;
This is a great point, I modified the code so It only changes the
outer loop count.
I included a screenshot showing how much this reduces variance over
multiple runs.
Did you try tweaking with the -p parameter? It can be useful when a
measure is "noisy".
PS: a comment in the current code says
/* Larger threshold is faster but takes ~O(n/ln(n)) memory.
To be honest, the array sieve needs n/24 bytes, and the array
You are correct, let's change the comment by which I mean you :)
Done.
Ĝis,
m
--
http://bodrato.it/papers/
diff -r a7836288d2c0 mpz/nextprime.c
--- a/mpz/nextprime.c Fri Mar 20 16:19:07 2020 +0100
+++ b/mpz/nextprime.c Tue Mar 24 17:24:41 2020 +0100
@@ -85,6 +85,9 @@
};
#define NUMBER_OF_PRIMES 100
+#define LAST_PRIME 557
+/* NP_SMALL_LIMIT = prevprime (LAST_PRIME ^ 2) */
+#define NP_SMALL_LIMIT 310243
static unsigned long
calculate_sievelimit(mp_bitcnt_t nbits) {
@@ -120,6 +123,32 @@
return sieve_limit;
}
+static unsigned
+mpz_nextprime_small (unsigned t)
+{
+ ASSERT (t > 0); /* Expect t=1 if the operand was smaller.*/
+ /* Technically this should be prev_prime(LAST_PRIME ^ 2) */
+ ASSERT (t < NP_SMALL_LIMIT);
+
+ /* Start from next candidate (2 or odd) */
+ t = (t + 1) | (t > 1);
+ for (; ; t += 2)
+ {
+ unsigned prime = 3;
+ for (int i = 0; ; prime += primegap_small[i++])
+ {
+ unsigned q, r;
+ q = t / prime;
+ r = t - q * prime; /* r = t % prime; */
+ if (q < prime)
+ return t;
+ if (r == 0)
+ break;
+ ASSERT (i < NUMBER_OF_PRIMES);
+ }
+ }
+}
+
void
mpz_nextprime (mpz_ptr p, mpz_srcptr n)
{
@@ -132,18 +161,16 @@
unsigned odds_in_composite_sieve;
TMP_DECL;
- /* First handle tiny numbers */
- if (mpz_cmp_ui (n, 2) < 0)
+ /* First handle small numbers */
+ if (mpz_cmp_ui (n, NP_SMALL_LIMIT) < 0)
{
- mpz_set_ui (p, 2);
+ ASSERT (NP_SMALL_LIMIT < UINT_MAX);
+ mpz_set_ui (p, mpz_nextprime_small (SIZ (n) > 0 ? mpz_get_ui (n) : 1));
return;
}
mpz_add_ui (p, n, 1);
mpz_setbit (p, 0);
- if (mpz_cmp_ui (p, 7) <= 0)
- return;
-
TMP_MARK;
pn = SIZ(p);
MPN_SIZEINBASE_2EXP(nbits, PTR(p), pn, 1);
_______________________________________________
gmp-devel mailing list
gmp-devel@gmplib.org
https://gmplib.org/mailman/listinfo/gmp-devel
