mpz_prevprime
Seth Troisi
braintwo at gmail.com
Tue Sep 3 06:41:47 UTC 2019
I've attached an updated diff, thanks for the comments Marco.
There doesn't seem to be a way to set s->reps without setting a high
precision so
I reused SPEED_BLOCK_SIZE from speed_gcd and ran the inner loop that many
times
Would folks rather I time
1. s->reps next_primes chained (next_prime(p, p); next_prime(p, p);)
2. s->reps of next_prime on random s->size bit numbers?
1. will be slightly slower (as it will have to search the full gap each
time) and more likely
for intermediate results to overflow s->size bits (which is seems fine)
than 2.
Currently it takes about 20 seconds to test -s 16-128, and 15 minutes to
test -s 16-1028
with -t 1.04 the resulting graph is much smoother than the old graph.
On Sat, Aug 24, 2019 at 8:33 AM Marco Bodrato <bodrato at mail.dm.unipi.it>
wrote:
> Ciao,
>
> Il Gio, 22 Agosto 2019 8:48 am, Marco Bodrato ha scritto:
> > Il Gio, 22 Agosto 2019 7:24 am, Niels Möller ha scritto:
> >> Maybe it would make sense to generalize a bit further, and write a
> >> function to find the first prime (if any) in an arithmetic sequence.
> >> I.e., find the smallest k >= such that A + kB is prime (if any). A
>
> ... here too we should decide what to do with negative numbers.
> which prime should we return if:
> 1) A = -123; B= 42; (I'd suggest A+3*B = +3)
> 2) A = -123; B= 30; (I'd suggest A+4*B = -3)
> 3) A = -123; B= 26; (I'd suggest A+1*B = -97)
>
> > I know that my proposal is an incompatible change for the interface...
> but
> > I'd suggest to extend the range for mpz_nextprime. Can we consider both
> > positive and negative primes?
>
> By the way... our documentation does not mention "positive" primes :-) and
> I'm quite sure that there aren't programs using the fact that the current
> implementation of nextprime returns 2 for negative numbers...
>
> Il Gio, 22 Agosto 2019 10:32 am, Niels Möller ha scritto:
> > I think that's a bit unusual. We can compare with the corresponding
> > functions in pari/gp. These differ from gmp by nextprime(p) == p if p is
> > prime. And they don't consider negative numbers to be primes.
>
> Il Mer, 21 Agosto 2019 10:02 am, Seth Troisi ha scritto:
> > Finally for mpz_prevprime(rop, op <= 2) it's not clear what rop should be
> > set to, so I use the smallest prime (2).
>
> Well, in pari/gp there is a function
> precprime(x): largest pseudoprime <= x, 0 if x<=1.
>
> I'm not sure I like that interface...
>
> My proposal to extend the range of nextprime to negative numbers:
>
> diff -r 643c931da9bd mpz/nextprime.c
> --- a/mpz/nextprime.c Thu Aug 22 15:14:09 2019 +0200
> +++ b/mpz/nextprime.c Sat Aug 24 16:52:21 2019 +0200
> @@ -56,21 +56,24 @@
> mp_size_t pn;
> mp_bitcnt_t nbits;
> unsigned incr;
> + mpz_t tp;
> TMP_SDECL;
>
> /* First handle tiny numbers */
> - if (mpz_cmp_ui (n, 2) < 0)
> + if (mpz_cmp_ui (n, 2) < 0 && mpz_cmpabs_ui (n, 4) < 0)
> {
> mpz_set_ui (p, 2);
> + if (mpz_cmpabs_ui (n, 3) == 0)
> + mpz_neg (p, p);
> return;
> }
> mpz_add_ui (p, n, 1);
> mpz_setbit (p, 0);
>
> - if (mpz_cmp_ui (p, 7) <= 0)
> + if (mpz_cmpabs_ui (p, 7) <= 0)
> return;
>
> - pn = SIZ(p);
> + pn = ABSIZ(p);
> MPN_SIZEINBASE_2EXP(nbits, PTR(p), pn, 1);
> if (nbits / 2 >= NUMBER_OF_PRIMES)
> prime_limit = NUMBER_OF_PRIMES - 1;
> @@ -88,7 +91,7 @@
> prime = 3;
> for (i = 0; i < prime_limit; i++)
> {
> - moduli[i] = mpz_tdiv_ui (p, prime);
> + moduli[i] = mpz_fdiv_ui (p, prime);
> prime += primegap[i];
> }
>
> @@ -115,7 +118,7 @@
> difference = 0;
>
> /* Miller-Rabin test */
> - if (mpz_millerrabin (p, 25))
> + if (mpz_millerrabin (mpz_roinit_n (tp, PTR (p), ABSIZ (p)), 25))
> goto done;
> next:;
> incr += 2;
>
>
> After those changes, the _precprime function can be implemented with:
>
> void
> mpz_precprime (mpz_ptr p, mpz_srcptr n)
> {
> mpz_t tn;
>
> mpz_nextprime (p, mpz_roinit_n (tn, PTR (n), -SIZ (n)));
> mpz_neg (p, p);
> }
>
>
> Ĝis,
> m
>
> --
> http://bodrato.it/papers/
>
>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: speed_nextprime.diff
Type: text/x-patch
Size: 2955 bytes
Desc: not available
URL: <https://gmplib.org/list-archives/gmp-devel/attachments/20190902/6e97ab01/attachment-0001.bin>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: speed_nextprime.png
Type: image/png
Size: 16175 bytes
Desc: not available
URL: <https://gmplib.org/list-archives/gmp-devel/attachments/20190902/6e97ab01/attachment-0001.png>
More information about the gmp-devel
mailing list