I made a few improvements.
tested with '--enable-assert' and verified no impact to timing with
`./tune/speed -f 1.02 -s 10-260 mpz_prevprime -p100000000 -P time_prevprime`
comparing with mpz_nextprime (before and after my change)
On Fri, Mar 27, 2020 at 2:29 AM Seth Troisi <brain...@gmail.com> wrote:
> Thanks for the quick review and probing comments.
>
> On Thu, Mar 26, 2020 at 2:00 PM Marco Bodrato <bodr...@mail.dm.unipi.it>
> wrote:
>
>> Ciao,
>>
>> Il 2020-03-25 02:25 Seth Troisi ha scritto:
>> > I'm back with a new mpz_prevprime patch
>>
>> diff -r 805304ca965a doc/gmp.texi
>> +@deftypefun int mpz_prevprime (mpz_t @var{rop}, const mpz_t @var{op})
>>
>> +If previous prime doesn't exist (e.g. @var{op} < 3), rop is unchanged
>> and
>> +0 is returned.
>>
>> I suggest "i.e." instead of "e.g.".
>>
> Replaced
>
>>
>> diff -r 805304ca965a mpz/nextprime.c
>> +findnext_small (unsigned t, short diff)
>> [...]
>> + ASSERT (t > 0 || (diff < 0 && t > 2));
>>
>> This is equivalent to (t > 0). Do you mean (t > 2 || (diff > 0 && t >
>> 0))?
>>
> Yes. changed now.
>
>>
>> + t = diff > 0 ? ((t + 1) | (t > 1)) :
>> + ((t == 3) ? 2 : ((t - 2) | 1));
>>
>> Maybe move this to the caller side? Or partially, leaving here just
>> ASSERT (t >= 2);
>> t |= (t != 2);
>>
> I moved this to the caller side (so that both findnext and findnext_small
> consider p) and added some comments
>
>>
>> -void
>> -mpz_nextprime (mpz_ptr p, mpz_srcptr n)
>> +int
>> +findnext (mpz_ptr p,
>>
>> If the function is not public any more, use static.
>>
> Done.
>
>>
>> - mpz_setbit (p, 0);
>>
>> This line can still be here, maybe converted to
>> * PTR (p) |= 1;
>>
> This has been moved to the outer functions.
> Maybe I should add a test that p is odd?
> Something like ASSERT (PTR(p) & 1 == 0);
>
>
>> + /* smaller numbers handled earlier*/
>> + ASSERT (nbits >= 15);
>>
>> Not needed. Maybe ASSERT (nbits > 3), because we don't want to handle
>> very small numbers with this code.
>>
> Changed back to nbits > 3 and added an ASSERT (SIZ(p) > 0);
>
>>
>> +int
>> +mpz_prevprime (mpz_ptr p, mpz_srcptr n)
>> +{
>> + /* First handle tiny numbers */
>> + if (mpz_cmp_ui (n, 2) <= 0)
>> + return 0;
>> +
>> + if (mpz_cmp_ui (n, NP_SMALL_LIMIT) < 0)
>> + {
>> + ASSERT (NP_SMALL_LIMIT < UINT_MAX);
>> + mpz_set_ui (p, findnext_small (SIZ (n) > 0 ? mpz_get_ui (n) : 1,
>> -2));
>> + return 2;
>> + }
>>
>> The line "if (mpz_cmp_ui (n, 2) <= 0)" already handle the case (SIZ (n)
>> <= 0), checking if (SIZ (n) > 0) is a nonsense
>> Anyway... assume that code is used: what happens if findnext_small(1,-2)
>> is called?
>>
> This has been reworked but should never have been included.
>
>>
>> diff -r 805304ca965a tests/mpz/t-nextprime.c
>> [...]
>> +refmpz_prevprime (mpz_ptr p, mpz_srcptr t)
>> [...]
>> + if (mpz_cmp_ui(t, 3) <= 0)
>>
>> The loop after that branch handles also that case, don't it?
>>
> Yes, I was counting by two but I reverted that at some point.
>
>>
>>
>> test_largegaps ()
>> {
>> [...]
>> + mpz_set_ui (n, 3842610773);
>> [...]
>> + mpz_set_ui (n, 18361375334787046697UL);
>>
>> Those lines can fail at compile time... if 3842610773 does not fit in an
>> int and 18361375334787046697 not in an unsigned long. E.g. when
>> sizeof(int)==4.
>> Use _set_str.
>>
>> + mpz_mul_ui (n, n, 4280516017);
>> [...]
>> + mpz_mul_ui (n, n, 3483347771);
>>
>> ...
>>
>> > I also added large negative tests for mpz_nextprime
>>
>> To be honest... I do not like this (undocumented) detail of the current
>> behaviour of _nextprime. I personally do not like the idea to enforce it
>> with a test...
>>
>> > and we can enable test_largegaps now that the default gap is smaller
>>
>> Yes, we should.
>> I would also check many gaps around 2^{16n}, to check if everything
>> works correctly when the search crosses the limb boundaries.
>> Maybe structuring the test with a table {"number(base16?)", gap}, i.e.
>> with (also) something like:
>> {"65521", 16},
>> {"4294967291", 20},
>> {"281474976710597", 80},
>> {"18446744073709551557", 72},
>> {"1208925819614629174706111", 78},
>> {"79228162514264337593543950319", 78},
>> {"5192296858534827628530496329220021", 100},
>> {"340282366920938463463374607431768211297", 210},
>>
> I did this (using hex form) I threw in some 16*n-1 also
>
>>
>>
>> +void
>> +test_prevprime (gmp_randstate_ptr rands, int reps)
>> [...]
>> + /* Test mpz_prevprime(3 <= n < 2^45) returns 2. */
>> [...]
>> + /* Test mpz_prevprime(n > 2^70) returns 1. */
>> [...]
>> + if ( retval != 1 )
>> [...]
>>
>> I do not understand. A test-function should fail if a function behaviour
>> does not agree with the documented interface, or it can fail for some
>> other kind of regression that we want to avoid...
>> Your test will warn us against possible improvements! What if the future
>> primality testing functions will return 2 on some large primes?
>>
>
> I modified the tests so that it makes it more clean that it's testing that
> it verifies the retval matches
> the return of mpz_prob_prime.
>
>
>> Ok, I'm sleepy now. I hope I did not write wrong things. Good night!
>>
> Given the number of times you are pointing our real issues, I wouldn't be
> worried about writing one or two wrong comments :)
>
>>
>> Ĝis,
>> m
>
>
diff -r c5d0fcb06969 doc/gmp.texi
--- a/doc/gmp.texi Sat Jul 04 23:15:41 2020 +0200
+++ b/doc/gmp.texi Fri Aug 28 03:44:14 2020 -0700
@@ -3563,8 +3563,19 @@
@deftypefun void mpz_nextprime (mpz_t @var{rop}, const mpz_t @var{op})
@cindex Next prime function
Set @var{rop} to the next prime greater than @var{op}.
-
-This function uses a probabilistic algorithm to identify primes. For
+@end deftypefun
+
+@deftypefun int mpz_prevprime (mpz_t @var{rop}, const mpz_t @var{op})
+@cindex Previous prime function
+Set @var{rop} to the greatest prime less than @var{op}.
+
+If previous prime doesn't exist (i.e. @var{op} < 3), rop is unchanged and
+0 is returned.
+
+Return 1 if @var{rop} is a probably prime, and 2 if @var{rop} is definitely
+prime.
+
+These functions use a probabilistic algorithm to identify primes. For
practical purposes it's adequate, the chance of a composite passing will be
extremely small.
@end deftypefun
diff -r c5d0fcb06969 gmp-h.in
--- a/gmp-h.in Sat Jul 04 23:15:41 2020 +0200
+++ b/gmp-h.in Fri Aug 28 03:44:14 2020 -0700
@@ -947,6 +947,9 @@
#define mpz_nextprime __gmpz_nextprime
__GMP_DECLSPEC void mpz_nextprime (mpz_ptr, mpz_srcptr);
+#define mpz_prevprime __gmpz_prevprime
+__GMP_DECLSPEC int mpz_prevprime (mpz_ptr, mpz_srcptr);
+
#define mpz_out_raw __gmpz_out_raw
#ifdef _GMP_H_HAVE_FILE
__GMP_DECLSPEC size_t mpz_out_raw (FILE *, mpz_srcptr);
diff -r c5d0fcb06969 mpz/nextprime.c
--- a/mpz/nextprime.c Sat Jul 04 23:15:41 2020 +0200
+++ b/mpz/nextprime.c Fri Aug 28 03:44:14 2020 -0700
@@ -124,14 +124,19 @@
}
static unsigned
-mpz_nextprime_small (unsigned t)
+findnext_small (unsigned t, short diff)
{
- ASSERT (t > 0); /* Expect t=1 if the operand was smaller.*/
+ /* For diff= 2, expect t = 1 if operand was negative.
+ * For diff=-2, expect t >= 3
+ */
+
+ /* Start from next candidate (2 or odd) */
+ t = diff > 0 ? (t + 1) | (t > 1)
+ : ((t - 2) | 1) + (t == 3);
+ ASSERT (t >= 2);
ASSERT (t < NP_SMALL_LIMIT);
- /* Start from next candidate (2 or odd) */
- t = (t + 1) | (t > 1);
- for (; ; t += 2)
+ for (; ; t += diff)
{
unsigned prime = 3;
for (int i = 0; ; prime += primegap_small[i++])
@@ -148,8 +153,10 @@
}
}
-void
-mpz_nextprime (mpz_ptr p, mpz_srcptr n)
+static int
+findnext (mpz_ptr p,
+ unsigned long(*nextmod_func)(const mpz_t, unsigned long),
+ void(*nextseq_func)(mpz_t, const mpz_t, unsigned long))
{
char *composite;
const unsigned char *primegap;
@@ -160,19 +167,14 @@
unsigned odds_in_composite_sieve;
TMP_DECL;
- /* First handle small numbers */
- if (mpz_cmp_ui (n, NP_SMALL_LIMIT) < 0)
- {
- 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);
-
TMP_MARK;
pn = SIZ(p);
MPN_SIZEINBASE_2EXP(nbits, PTR(p), pn, 1);
+ /* Smaller numbers handled earlier */
+ ASSERT (nbits >= 3);
+ /* p is odd */
+ ASSERT ((PTR(p)[0] & 1) == 1);
+
if (nbits / 2 <= NUMBER_OF_PRIMES)
{
primegap = primegap_small;
@@ -229,12 +231,13 @@
{
unsigned long difference;
unsigned long incr, prime;
+ int primetest;
memset (composite, 0, odds_in_composite_sieve);
prime = 3;
for (i = 0; i < prime_limit; i++)
{
- m = mpz_cdiv_ui(p, prime);
+ m = nextmod_func(p, prime);
/* Only care about odd multiplies of prime. */
if (m & 1)
m += prime;
@@ -252,20 +255,60 @@
if (composite[incr])
continue;
- mpz_add_ui (p, p, difference);
+ nextseq_func(p, p, difference);
difference = 0;
/* Miller-Rabin test */
- if (mpz_millerrabin (p, 25))
+ primetest = mpz_millerrabin (p, 25);
+ if (primetest)
{
TMP_FREE;
- return;
+ return primetest;
}
}
/* Sieve next segment, very rare */
- mpz_add_ui (p, p, difference);
+ nextseq_func(p, p, difference);
+ }
+}
+
+void
+mpz_nextprime (mpz_ptr p, mpz_srcptr n)
+{
+ /* First handle small numbers */
+ if (mpz_cmp_ui (n, NP_SMALL_LIMIT) < 0)
+ {
+ ASSERT (NP_SMALL_LIMIT < UINT_MAX);
+ mpz_set_ui (p, findnext_small (SIZ (n) > 0 ? mpz_get_ui (n) : 1, +2));
+ return;
}
+
+ /* First odd greater than n */
+ mpz_add_ui (p, n, 1);
+ mpz_setbit (p, 0);
+
+ findnext(p, mpz_cdiv_ui, mpz_add_ui);
+}
+
+int
+mpz_prevprime (mpz_ptr p, mpz_srcptr n)
+{
+ /* First handle tiny numbers */
+ if (mpz_cmp_ui (n, 2) <= 0)
+ return 0;
+
+ if (mpz_cmp_ui (n, NP_SMALL_LIMIT) < 0)
+ {
+ ASSERT (NP_SMALL_LIMIT < UINT_MAX);
+ mpz_set_ui (p, findnext_small (mpz_get_ui (n), -2));
+ return 2;
+ }
+
+ /* First odd less than n */
+ mpz_sub_ui (p, n, 2);
+ mpz_setbit (p, 0);
+
+ return findnext(p, mpz_fdiv_ui, mpz_sub_ui);
}
#undef LOOP_ON_SIEVE_END
diff -r c5d0fcb06969 tests/mpz/Makefile.am
--- a/tests/mpz/Makefile.am Sat Jul 04 23:15:41 2020 +0200
+++ b/tests/mpz/Makefile.am Fri Aug 28 03:44:14 2020 -0700
@@ -30,7 +30,8 @@
t-fac_ui t-mfac_uiui t-primorial_ui t-fib_ui t-lucnum_ui t-scan t-fits \
t-divis t-divis_2exp t-cong t-cong_2exp t-sizeinbase t-set_str \
t-aorsmul t-cmp_d t-cmp_si t-hamdist t-oddeven t-popcount t-set_f \
- t-io_raw t-import t-export t-pprime_p t-nextprime t-remove t-limbs
+ t-io_raw t-import t-export t-pprime_p t-nextprime t-remove t-limbs \
+ t-nextprime-tune
TESTS = $(check_PROGRAMS)
diff -r c5d0fcb06969 tests/mpz/t-nextprime.c
--- a/tests/mpz/t-nextprime.c Sat Jul 04 23:15:41 2020 +0200
+++ b/tests/mpz/t-nextprime.c Fri Aug 28 03:44:14 2020 -0700
@@ -33,10 +33,20 @@
}
void
+refmpz_prevprime (mpz_ptr p, mpz_srcptr t)
+{
+ if (mpz_cmp_ui(t, 2) <= 0)
+ return;
+
+ mpz_sub_ui (p, t, 1L);
+ while (! mpz_probab_prime_p (p, 10))
+ mpz_sub_ui (p, p, 1L);
+}
+
+void
test_largegap (mpz_t low, const int gap)
{
mpz_t t, nxt;
-
mpz_init (t);
mpz_init (nxt);
@@ -45,45 +55,55 @@
if (mpz_cmp_ui(t, gap) != 0)
{
- gmp_printf ("prime gap %Zd != %d\n", t, gap);
+ gmp_printf ("nextprime gap %Zd => %Zd != %d\n", low, nxt, gap);
abort ();
}
+ mpz_prevprime(t, nxt);
+ if (mpz_cmp(t, low) != 0)
+ {
+ gmp_printf ("prevprime gap %Zd => %Zd != %d\n", nxt, t, gap);
+ abort ();
+ }
+
+ mpz_clear (nxt);
mpz_clear (t);
- mpz_clear (nxt);
}
void
test_largegaps ()
{
- mpz_t x;
+ mpz_t n;
+
+ mpz_init (n);
- mpz_init (x);
+ // largest gap with start < 2^32.
+ mpz_set_str (n, "3842610773", 10);
+ test_largegap (n, 336);
- // This takes ~3 seconds on a fast computer.
- // Gap 33008 from P454 = 55261931 * 1063#/210 - 13116
- mpz_primorial_ui (x, 1063);
- mpz_mul_ui (x, x, 55261931);
- mpz_divexact_ui (x, x, 210);
- mpz_sub_ui (x, x, 13116);
+ // largest gap with start < 2^64.
+ mpz_set_str (n, "18361375334787046697", 10);
+ test_largegap (n, 1550);
- test_largegap(x, 33008);
+ // test high merit primegap in the P30 digit range.
+ mpz_set_str (n, "3001549619028223830552751967", 10);
+ test_largegap (n, 2184);
- mpz_clear (x);
-
+ // test high merit primegap in the P100 range.
+ mpz_primorial_ui (n, 257);
+ mpz_mul_ui (n, n, 4280516017UL);
+ mpz_divexact_ui (n, n, 5610);
+ mpz_sub_ui (n, n, 2560);
+ test_largegap (n, 9006);
- /*
- // This takes ~30 seconds, it test the deep science magic constant in
- // nextprime.c but takes too long to be always enabled.
- // Gap 66520 from P816 = 1931 * 1933# / 7230 - 30244
- mpz_primorial_ui (x, 1933);
- mpz_mul_ui (x, x, 1931);
- mpz_divexact_ui (x, x, 7230);
- mpz_sub_ui (x, x, 30244);
+ // test high merit primegap in the P200 range.
+ mpz_primorial_ui (n, 409);
+ mpz_mul_ui (n, n, 3483347771UL);
+ mpz_divexact_ui (n, n, 30);
+ mpz_sub_ui (n, n, 7016);
+ test_largegap (n, 15900);
- test_largegap(x, 66520);
- */
-
+ mpz_clear (n);
}
void
@@ -112,8 +132,8 @@
if (mpz_cmp (x, y) != 0)
{
- gmp_printf ("got %Zx\n", x);
- gmp_printf ("want %Zx\n", y);
+ gmp_printf ("got %Zd\n", x);
+ gmp_printf ("want %Zd\n", y);
abort ();
}
@@ -121,6 +141,45 @@
mpz_clear (x);
}
+void
+run_p (const char *start, int reps, const char *end, short diffs[])
+{
+ mpz_t x, y;
+ int i;
+
+ mpz_init_set_str (x, end, 0);
+ mpz_init (y);
+
+ // Last rep doesn't share same data with nextprime
+ for (i = 0; i < reps - 1; i++)
+ {
+ mpz_prevprime (y, x);
+ mpz_sub (x, x, y);
+ if (diffs != NULL &&
+ (! mpz_fits_sshort_p (x) || diffs[reps - i - 1] != (short) mpz_get_ui (x)))
+ {
+ gmp_printf ("diff list discrepancy %Zd, %d vs %d\n",
+ y, diffs[i], mpz_get_ui (x));
+ abort ();
+ }
+ mpz_swap (x, y);
+ }
+
+ // starts aren't always prime, so check that result is less than or equal
+ mpz_prevprime(x, x);
+
+ mpz_set_str(y, start, 0);
+ if (mpz_cmp (x, y) > 0)
+ {
+ gmp_printf ("got %Zd\n", x);
+ gmp_printf ("want %Zd\n", y);
+ }
+
+ mpz_clear (y);
+ mpz_clear (x);
+}
+
+
extern short diff1[];
extern short diff3[];
extern short diff4[];
@@ -128,15 +187,18 @@
extern short diff6[];
void
-test_ref(gmp_randstate_ptr rands, int reps) {
+test_ref (gmp_randstate_ptr rands, int reps,
+ void (*func)(mpz_t, const mpz_t),
+ void(*ref_func)(mpz_t, const mpz_t))
+{
int i;
- mpz_t bs, x, next_p, ref_next_p;
+ mpz_t bs, x, test_p, ref_p;
unsigned long size_range;
mpz_init (bs);
mpz_init (x);
- mpz_init (next_p);
- mpz_init (ref_next_p);
+ mpz_init (test_p);
+ mpz_init (ref_p);
for (i = 0; i < reps; i++)
{
@@ -146,35 +208,59 @@
mpz_urandomb (bs, rands, size_range);
mpz_rrandomb (x, rands, mpz_get_ui (bs));
-/* gmp_printf ("%ld: %Zd\n", mpz_sizeinbase (x, 2), x); */
-
- mpz_nextprime (next_p, x);
- refmpz_nextprime (ref_next_p, x);
- if (mpz_cmp (next_p, ref_next_p) != 0)
+ func (test_p, x);
+ ref_func (ref_p, x);
+ if (mpz_cmp (test_p, ref_p) != 0)
{
- gmp_printf ("Ref mismatch %Zd => %Zd vs %Zd\n", x, ref_next_p, next_p);
+ gmp_printf ("start %Zd\n", x);
+ gmp_printf ("got %Zd\n", test_p);
+ gmp_printf ("want %Zd\n", ref_p);
abort ();
}
}
mpz_clear (bs);
mpz_clear (x);
- mpz_clear (next_p);
- mpz_clear (ref_next_p);
+ mpz_clear (test_p);
+ mpz_clear (ref_p);
}
-int
-main (int argc, char **argv)
+void
+test_nextprime(gmp_randstate_ptr rands, int reps)
{
- gmp_randstate_ptr rands;
- int reps = 20;
+ /* Test mpz_nextprime(n <= 1) returns 2. */
+ {
+ long i;
+ mpz_t n, nxtp;
+ mpz_init (n);
+ mpz_init (nxtp);
- tests_start();
+ for (i = -10; i <= 1; i++)
+ {
+ mpz_set_si(n, i);
+ mpz_nextprime (nxtp, n);
+ if ( mpz_cmp_ui (nxtp, 2) != 0 )
+ {
+ gmp_printf ("mpz_nxtprime(%Zd) return %Zd\n", n, nxtp);
+ abort ();
+ }
+ }
- rands = RANDS;
- TESTS_REPS (reps, argv, argc);
+ for (i = 0; i <= 1000; i++)
+ {
+ mpz_ui_pow_ui(n, 2, i);
+ mpz_neg(n, n);
+ mpz_nextprime (nxtp, n);
+ if ( mpz_cmp_ui (nxtp, 2) != 0 )
+ {
+ gmp_printf ("mpz_prevprime(%Zd) return %Zd\n", n, nxtp);
+ abort ();
+ }
+ }
- test_ref(rands, reps);
+ mpz_clear (n);
+ mpz_clear (nxtp);
+ }
run ("2", 1000, "0x1ef7", diff1);
@@ -192,8 +278,114 @@
run ("0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF80", 50, /* 2^128 - 128 */
"0x10000000000000000000000000000155B", diff6);
- // Too slow to include in normal testing.
- //test_largegaps ();
+ test_ref(
+ rands, reps,
+ (void (*)(mpz_t, const mpz_t)) mpz_nextprime,
+ refmpz_nextprime);
+}
+
+void
+test_prevprime (gmp_randstate_ptr rands, int reps)
+{
+ long i;
+ int retval;
+ mpz_t n, prvp;
+
+ mpz_init (n);
+ mpz_init (prvp);
+
+ /* Test mpz_prevprime(n <= 2) returns 0, leaves rop unchanged. */
+ {
+ int temp = -5;
+ mpz_set_si (prvp, temp);
+ for (i = -10; i <= 2; i++)
+ {
+ mpz_set_si(n, i);
+ retval = mpz_prevprime (prvp, n);
+ if ( retval != 0 || mpz_cmp_si (prvp, temp) != 0 )
+ {
+ gmp_printf ("mpz_prevprime(%Zd) return (%d) rop (%Zd)\n", n, retval, prvp);
+ abort ();
+ }
+ }
+ }
+
+ mpz_set_ui(n, 3);
+ if ( mpz_prevprime (prvp, n) != 2 || mpz_cmp_ui(prvp, 2) != 0 )
+ {
+ gmp_printf ("mpz_prevprime(%Zd) return (%d) rop (%Zd)\n", n, retval, prvp);
+ abort ();
+ }
+
+ /* Test mpz_prevprime(10 <= n < 2^20) expect definitely prime (return 2). */
+ {
+ for (i = 10; i < 0x100000L; i += i/10)
+ {
+ mpz_set_ui(n, i);
+ retval = mpz_prevprime (prvp, n);
+ if ( retval != 2 || mpz_cmp(prvp, n) >= 0 )
+ {
+ gmp_printf ("mpz_prevprime(%Zd) return (%d) rop (%Zd)\n", n, retval, prvp);
+ abort ();
+ }
+ }
+ }
+
+ /* Test mpz_prevprime(2^70 <= n <= 2^100). */
+ {
+ for (i = 70; i < 100; i++)
+ {
+ mpz_ui_pow_ui(n, 2, i);
+ retval = mpz_prevprime (prvp, n);
+ if ( retval == 0 || mpz_cmp(prvp, n) >= 0 )
+ {
+ gmp_printf ("mpz_prevprime(%Zd) return (%d) rop (%Zd)\n", n, retval, prvp);
+ abort ();
+ }
+ }
+ }
+
+ mpz_clear (n);
+ mpz_clear (prvp);
+
+ run_p ("2", 1000, "0x1ef7", diff1);
+
+ run_p ("3", 1000 - 1, "0x1ef7", NULL);
+
+ run_p ("0x8a43866f5776ccd5b02186e90d28946aeb0ed914", 50,
+ "0x8a43866f5776ccd5b02186e90d28946aeb0eeec5", diff3);
+
+ run_p ("0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF6C", 50, /* 2^148 - 148 */
+ "0x100000000000000000000000000000000010ab", diff4);
+
+ run_p ("0x1c2c26be55317530311facb648ea06b359b969715db83292ab8cf898d8b1b", 50,
+ "0x1c2c26be55317530311facb648ea06b359b969715db83292ab8cf898da957", diff5);
+
+ run_p ("0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF80", 50, /* 2^128 - 128 */
+ "0x10000000000000000000000000000155B", diff6);
+
+ // Cast away int return from mpz_prevprime for test ref.
+ test_ref(
+ rands, reps,
+ (void (*)(mpz_t, const mpz_t)) mpz_prevprime,
+ refmpz_prevprime);
+}
+
+int
+main (int argc, char **argv)
+{
+ gmp_randstate_ptr rands;
+ int reps = 20;
+
+ tests_start();
+
+ rands = RANDS;
+ TESTS_REPS (reps, argv, argc);
+
+ test_nextprime(rands, reps);
+ test_prevprime(rands, reps);
+
+ test_largegaps ();
tests_end ();
return 0;
diff -r c5d0fcb06969 tune/common.c
--- a/tune/common.c Sat Jul 04 23:15:41 2020 +0200
+++ b/tune/common.c Fri Aug 28 03:44:14 2020 -0700
@@ -1776,6 +1776,18 @@
}
double
+speed_mpz_prevprime (struct speed_params *s)
+{
+ SPEED_ROUTINE_MPZ_NEXTPRIME (mpz_prevprime);
+}
+
+double
+speed_mpz_prevprime_1 (struct speed_params *s)
+{
+ SPEED_ROUTINE_MPZ_UNARY_1 (mpz_prevprime);
+}
+
+double
speed_mpz_jacobi (struct speed_params *s)
{
SPEED_ROUTINE_MPZ_JACOBI (mpz_jacobi);
diff -r c5d0fcb06969 tune/speed.c
--- a/tune/speed.c Sat Jul 04 23:15:41 2020 +0200
+++ b/tune/speed.c Fri Aug 28 03:44:14 2020 -0700
@@ -318,6 +318,8 @@
{ "mpz_nextprime", speed_mpz_nextprime },
{ "mpz_nextprime_1", speed_mpz_nextprime_1, FLAG_R_OPTIONAL },
+ { "mpz_prevprime", speed_mpz_prevprime },
+ { "mpz_prevprime_1", speed_mpz_prevprime_1, FLAG_R_OPTIONAL },
{ "mpz_jacobi", speed_mpz_jacobi },
{ "mpn_jacobi_base", speed_mpn_jacobi_base },
diff -r c5d0fcb06969 tune/speed.h
--- a/tune/speed.h Sat Jul 04 23:15:41 2020 +0200
+++ b/tune/speed.h Fri Aug 28 03:44:14 2020 -0700
@@ -409,6 +409,8 @@
double speed_mpz_init_realloc_clear (struct speed_params *);
double speed_mpz_nextprime (struct speed_params *);
double speed_mpz_nextprime_1 (struct speed_params *);
+double speed_mpz_prevprime (struct speed_params *);
+double speed_mpz_prevprime_1 (struct speed_params *);
double speed_mpz_jacobi (struct speed_params *);
double speed_mpz_lucnum_ui (struct speed_params *);
double speed_mpz_lucnum2_ui (struct speed_params *);
_______________________________________________
gmp-devel mailing list
gmp-devel@gmplib.org
https://gmplib.org/mailman/listinfo/gmp-devel
