I see this was pushed, with a few more polishing tweaks.
Thanks for the collaboration to improve my rough code into something much
cleaner.
I see you also added more testing in tests/devel/primes.c which is a great
triple check.
It looks like the usage on line 21-28 / 399 wasn't updated.
Now that this is in I have a much smaller patch to add mpz_prevprime()
My patch includes t-nextprime-tune.c and Makefile.am which should not be
committed but I used
for internal testing and might be useful.
On Tue, Mar 17, 2020 at 10:53 PM Seth Troisi <brain...@gmail.com> wrote:
>
>
> On Tue, Mar 17, 2020 at 3:04 PM Marco Bodrato <bodr...@mail.dm.unipi.it>
> wrote:
>
>> Ciao,
>>
>> Il 2020-03-16 02:23 Seth Troisi ha scritto:
>> > On Sun, Mar 15, 2020 at 4:38 PM Marco Bodrato
>> > <bodr...@mail.dm.unipi.it> wrote:
>> >> May I write a few more comments?
>>
>> > Always, my opinion about being ready is just that it's passed
>> > the bar of being good enough not that it's perfect.
>>
>> I'm tempted to simply commit your proposal and then change it :-)
>> But if we keep on discussing here, we can improving the code with the
>> opinions of two persons...
>>
>> >> I see now:
>> >> + if (nbits <= 32)
>> >> + incr_limit = 336;
>>
>> >> Probably, we should change the name of the variable to
>> >> odd_candidates_in_sieve, then you would probably have written:
>> >> if (nbits <= 32)
>> >> odd_numbers_in_sieve = 168;
>>
>> > Renamed to odds_in_composite_sieve
>>
>> Of course the name is not essential, the values are :-)
>> And they seem correct to me, now.
>>
> I only discovered on experimental verification but the +1 is not needed,
> it took me a while to
> understand why but p is incremented to the first odd after the start of
> the gap by so the gap is -2
>
>>
>> >> Then I wonder if the cost of the /* Sieve next segment */ step
>> [...]
>> >> need to allocate the possibly huge next_mult array?
>> >
>> > You're correct, this reduces the memory use 80%
>>
>> Moreover the code has now the following structure:
>>
>> SIEVE;
>> for (;;) {
>> CHECK_AND_POSSIBLY_BREAK;
>> SIEVE;
>> }
>>
>> There is an unneeded code duplication, it should be:
>>
>> for (;;) {
>> SIEVE;
>> CHECK_AND_POSSIBLY_BREAK;
>> }
>>
> This is a great improvement :) thanks for the additional pair of eyes :)
>
>
>> >> If you need to store larger gaps, you can also save in
>> >> the array gap>>1, because they all are even. The prime
>> >> limit will be able to go beyond 2^37...
>> >
>> > Updated comment for how this could be done in the future.
>>
>> The first gap larger than 500, if I'm not wrong, is
>> 304599508537+514=304599509051
>>
> I added "far" so the comment now reads "allow this to go far beyond 436M"
>
>>
>> >> I'd expect a condition like
>> >>
>> >> + if (nbits <= numberof (primegap_small) * 2 + 1)
>> >> + {
>> >> + primegap = primegap_small;
>> >> + prime_limit = nbits / 2;
>> >> + }
>>
>> > Done
>>
>> I read:
>> + if (2 * nbits <= NUMBER_OF_PRIMES)
>> + {
>> + primegap = primegap_small;
>> + prime_limit = nbits / 2;
>> + }
>>
>> But ... this means that at most one fourth of the constants in
>> primegap_small are used, am I wrong?
>>
> I was experimenting with using 3 * nbits / 5 and other ratios and
> miscommitted this.
> Thanks again for the 2nd pair of eyes.
>
>>
>> Ĝis,
>> m
>>
>
diff -r a7836288d2c0 doc/gmp.texi
--- a/doc/gmp.texi Fri Mar 20 16:19:07 2020 +0100
+++ b/doc/gmp.texi Sat Mar 21 03:40:28 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 (e.g. @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 a7836288d2c0 gmp-h.in
--- a/gmp-h.in Fri Mar 20 16:19:07 2020 +0100
+++ b/gmp-h.in Sat Mar 21 03:40:28 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 a7836288d2c0 mpz/nextprime.c
--- a/mpz/nextprime.c Fri Mar 20 16:19:07 2020 +0100
+++ b/mpz/nextprime.c Sat Mar 21 03:40:28 2020 -0700
@@ -120,8 +120,10 @@
return sieve_limit;
}
-void
-mpz_nextprime (mpz_ptr p, mpz_srcptr n)
+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;
@@ -132,21 +134,13 @@
unsigned odds_in_composite_sieve;
TMP_DECL;
- /* First handle tiny numbers */
- if (mpz_cmp_ui (n, 2) < 0)
- {
- mpz_set_ui (p, 2);
- return;
- }
- mpz_add_ui (p, n, 1);
- mpz_setbit (p, 0);
+ TMP_MARK;
- if (mpz_cmp_ui (p, 7) <= 0)
- return;
-
- TMP_MARK;
pn = SIZ(p);
MPN_SIZEINBASE_2EXP(nbits, PTR(p), pn, 1);
+ /* p >= 8, smaller numbers handled */
+ ASSERT (nbits <= 3);
+
if (nbits / 2 <= NUMBER_OF_PRIMES)
{
primegap = primegap_small;
@@ -165,8 +159,8 @@
prime_limit = gmp_primesieve(sieve, sieve_limit);
/* TODO: Storing (prime - last_prime)/2 would allow this to go
- up to the gap 304599508537+514=304599509051 .
- With the current code our limit is 436273009+282=436273291 */
+ up to the gap 304599508537+514=304599509051 .
+ With the current code our limit is 436273009+282=436273291 */
ASSERT (sieve_limit < 436273291);
/* Needed to avoid assignment of read-only location */
@@ -199,13 +193,14 @@
{
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);
- /* Only care about odd multiplies of prime. */
+ m = nextmod_func(p, prime);
+ /* Only care about odd multiplies */
if (m & 1)
m += prime;
m >>= 1;
@@ -222,20 +217,62 @@
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))
- {
- TMP_FREE;
- return;
- }
+ primetest = mpz_millerrabin (p, 25);
+ if (primetest)
+ {
+ TMP_FREE;
+ 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 tiny numbers */
+ if (mpz_cmp_ui (n, 2) < 0)
+ {
+ mpz_set_ui (p, 2);
+ return;
}
+ mpz_add_ui (p, n, 1);
+ mpz_setbit (p, 0);
+
+ if (mpz_cmp_ui (p, 7) <= 0)
+ return;
+
+ 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, 3) == 0)
+ {
+ mpz_set_ui(p, 2);
+ return 2;
+ }
+
+ /* First odd less than n */
+ mpz_sub_ui (p, n, 2);
+ mpz_setbit (p, 0);
+
+ if (mpz_cmp_ui (n, 9) <= 0)
+ return 2;
+
+ return findnext(p, mpz_fdiv_ui, mpz_sub_ui);
}
#undef LOOP_ON_SIEVE_END
diff -r a7836288d2c0 tests/mpz/Makefile.am
--- a/tests/mpz/Makefile.am Fri Mar 20 16:19:07 2020 +0100
+++ b/tests/mpz/Makefile.am Sat Mar 21 03:40:28 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 a7836288d2c0 tests/mpz/t-nextprime-tune.c
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/tests/mpz/t-nextprime-tune.c Sat Mar 21 03:40:28 2020 -0700
@@ -0,0 +1,107 @@
+/* Test mpz_nextprime.
+
+Copyright 2009, 2015, 2018, 2020 Free Software Foundation, Inc.
+
+This file is part of the GNU MP Library test suite.
+
+The GNU MP Library test suite is free software; you can redistribute it
+and/or modify it under the terms of the GNU General Public License as
+published by the Free Software Foundation; either version 3 of the License,
+or (at your option) any later version.
+
+The GNU MP Library test suite is distributed in the hope that it will be
+useful, but WITHOUT ANY WARRANTY; without even the implied warranty of
+MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General
+Public License for more details.
+
+You should have received a copy of the GNU General Public License along with
+the GNU MP Library test suite. If not, see https://www.gnu.org/licenses/. */
+
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <sys/time.h>
+
+#include "gmp-impl.h"
+#include "tests.h"
+
+int
+main (int argc, char **argv)
+{
+ gmp_randstate_ptr rands;
+ int reps = 20;
+
+ tests_start();
+
+ struct timeval tval_b, tval_a, tval_result;
+
+ mpz_t n, m;
+ mpz_init(n);
+ mpz_init(m);
+
+ //int sizes[] = {100, 200, 300, 500, 1000, 2000, 5000};
+ //int sizes[] = {300, 500, 1000, 2000};
+ //int sizes[] = {3000, 5000};
+ int sizes[] = {32, 64, 128, 256,
+// 180, 200, 220,
+// 400, 500, 600, 700, 800, 900,
+ 1000, 1250, 1500, 1750, 2000, 2500, 3000, 4000,
+ 5000, 7500,
+ 10000, 12500, 15000
+ };
+
+ for (int i = 0; i < sizeof(sizes)/sizeof(sizes[0]); i++) {
+ int size = sizes[i];
+ int sumgap_next, sumgap_prev;
+ float seconds_next, seconds_prev;
+
+ mpz_ui_pow_ui(n, 2, size-1);
+ mpz_set(m, n);
+
+ gettimeofday(&tval_a, NULL);
+
+// int counts = 5;
+// int counts = 50;
+ int counts = 30 * 15000 / size;
+ for (int t = 0; t < counts; t++) {
+ mpz_nextprime(n, n);
+ }
+
+ gettimeofday(&tval_b, NULL);
+ timersub(&tval_b, &tval_a, &tval_result);
+ seconds_next = tval_result.tv_sec;
+ seconds_next += tval_result.tv_usec / 1e6;
+
+ mpz_sub(m, n, m);
+ sumgap_next = mpz_get_ui(m);
+ mpz_set(m, n);
+
+ for (int t = 0; t < counts; t++) {
+ mpz_prevprime(n, n);
+ }
+
+ gettimeofday(&tval_a, NULL);
+ timersub(&tval_a, &tval_b, &tval_result);
+ seconds_prev = tval_result.tv_sec;
+ seconds_prev += tval_result.tv_usec / 1e6;
+
+ mpz_sub(m, m, n);
+ sumgap_prev = mpz_get_ui(m);
+
+ if (sumgap_prev <= sumgap_next)
+ // should have returned to <= the first value
+ gmp_printf("Error!\n");
+
+ gmp_printf("%d, count: %d, gap: %d %d, %.4f, %.4f seconds = avg %.5f, %.5f\n\n\n",
+ size, counts,
+ sumgap_next, sumgap_prev,
+ seconds_next, seconds_prev,
+ seconds_next / counts, seconds_prev / counts);
+ }
+
+ mpz_clear(n);
+ mpz_clear(m);
+
+ tests_end ();
+ return 0;
+}
diff -r a7836288d2c0 tests/mpz/t-nextprime.c
--- a/tests/mpz/t-nextprime.c Fri Mar 20 16:19:07 2020 +0100
+++ b/tests/mpz/t-nextprime.c Sat Mar 21 03:40:28 2020 -0700
@@ -33,6 +33,23 @@
}
void
+refmpz_prevprime (mpz_ptr p, mpz_srcptr t)
+{
+ if (mpz_cmp_ui(t, 2) <= 0)
+ return;
+
+ if (mpz_cmp_ui(t, 3) <= 0)
+ {
+ mpz_set_ui (p, 2);
+ 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;
@@ -60,30 +77,33 @@
mpz_init (x);
- // 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^32.
+ mpz_set_ui (x, 3842610773);
+ test_largegap (x, 336);
+
+ // largest gap with start < 2^64.
+ mpz_set_ui (x, 18361375334787046697UL);
+ test_largegap (x, 1550);
+
+ // test high merit primegap in the P30 digit range.
+ mpz_set_str (x, "3001549619028223830552751967", 10);
+ test_largegap (x, 2184);
- test_largegap(x, 33008);
+ // test high merit primegap in the P100 range.
+ mpz_primorial_ui (x, 257);
+ mpz_mul_ui (x, x, 4280516017);
+ mpz_divexact_ui (x, x, 5610);
+ mpz_sub_ui (x, x, 2560);
+ test_largegap (x, 9006);
+
+ // test high merit primegap in the P200 range.
+ mpz_primorial_ui (x, 409);
+ mpz_mul_ui (x, x, 3483347771);
+ mpz_divexact_ui (x, x, 30);
+ mpz_sub_ui (x, x, 7016);
+ test_largegap (x, 15900);
mpz_clear (x);
-
-
- /*
- // 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_largegap(x, 66520);
- */
-
}
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,33 +208,26 @@
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)
- abort ();
+ func (test_p, x);
+ ref_func (ref_p, x);
+ if (mpz_cmp (test_p, ref_p) != 0)
+ {
+ 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;
-
- tests_start();
-
- rands = RANDS;
- TESTS_REPS (reps, argv, argc);
-
- test_ref(rands, reps);
-
run ("2", 1000, "0x1ef7", diff1);
run ("3", 1000 - 1, "0x1ef7", NULL);
@@ -189,8 +244,106 @@
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)
+{
+ unsigned long i;
+ int retval;
+ mpz_t x, prvp;
+
+ mpz_init (x);
+ mpz_init (prvp);
+
+ /* Test mpz_prevprime(x <= 2) returns 0, leaves rop unchanged. */
+ {
+ mpz_set_ui (prvp, 123);
+ for (i = -10; i <= 2; i++)
+ {
+ mpz_set_si(x, i);
+ retval = mpz_prevprime (prvp, x);
+ if ( retval != 0 || mpz_get_si (prvp) != 123 )
+ {
+ gmp_printf ("mpz_prevprime(%d) return (%d) rop (%Zd)\n", i, retval, prvp);
+ abort ();
+ }
+ }
+ }
+
+ /* Test mpz_prevprime(3 <= x < 2^45) returns 2. */
+ {
+ for (i = 10; i < 0x200000000000L; i += i/10)
+ {
+ mpz_set_si(x, i);
+ retval = mpz_prevprime (prvp, x);
+ if ( retval != 2 )
+ {
+ gmp_printf ("mpz_prevprime(%d) return (%d) rop (%Zd)\n", i, retval, prvp);
+ abort ();
+ }
+ }
+ }
+
+ /* Test mpz_prevprime(x > 2^70) returns 1. */
+ {
+ for (i = 70; i < 100; i++)
+ {
+ mpz_ui_pow_ui(x, 2, i);
+ retval = mpz_prevprime (prvp, x);
+ if ( retval != 1 )
+ {
+ gmp_printf ("mpz_prevprime(%Zd) return (%d) rop (%Zd)\n", x, retval, prvp);
+ abort ();
+ }
+ }
+ }
+
+ mpz_clear (x);
+ 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 a7836288d2c0 tune/speed.h
--- a/tune/speed.h Fri Mar 20 16:19:07 2020 +0100
+++ b/tune/speed.h Sat Mar 21 03:40:28 2020 -0700
@@ -3214,7 +3214,7 @@
/* Calculate nextprime(n) for random n of s->size bits (not limbs). */
#define SPEED_ROUTINE_MPZ_NEXTPRIME(function) \
{ \
- unsigned i, j; \
+ unsigned i, j, k; \
mpz_t wp, n; \
double t; \
\
@@ -3230,17 +3230,19 @@
\
speed_starttime (); \
i = s->reps; \
+ /* Increase time_divisor significantly for small numbers */ \
+ j = 200000 / s->size; \
do \
{ \
/* nextprime timing is variable, so average over many calls */ \
- j = SPEED_BLOCK_SIZE - 1; \
+ k = j-1; \
/* starts on random, after measures prime to next prime */ \
function (wp, n); \
do \
{ \
function (wp, wp); \
} \
- while (--j != 0); \
+ while (--k != 0); \
} \
while (--i != 0); \
t = speed_endtime (); \
@@ -3248,7 +3250,7 @@
mpz_clear (wp); \
mpz_clear (n); \
\
- s->time_divisor = SPEED_BLOCK_SIZE; \
+ s->time_divisor = j; \
return t; \
}
_______________________________________________
gmp-devel mailing list
gmp-devel@gmplib.org
https://gmplib.org/mailman/listinfo/gmp-devel
