mpz_prevprime

Seth Troisi braintwo at gmail.com
Fri Oct 16 07:51:33 UTC 2020


I included a patch with the rename but not including Marco's tdiv

I measured tune/speed and it seems very stable (this requires setting
cpupower -g powersave to avoid weird turbo behavior)
[image: time_nextprime.png]


Il Ven, 16 Ottobre 2020 7:13 am, Marco Bodrato ha scritto:
>    m = mpz_tdiv_ui(p, prime);
>    m = (diff > 0) ? prime - m : m;

I remember that, in this context, if p = 0 (mod prime), the result m =
prime is as good as the result m = 0. Because the next two lines are:
     if (m & 1)
       m += prime;

won't this cause m = 2*prime, instead of the original result, m = 0?
I used m = (diff > 0 && m) ? prime - m : m;
to make sure that p can be marked as composite.



On Fri, Oct 16, 2020 at 12:13 AM Niels Möller <nisse at lysator.liu.se> wrote:

> Seth Troisi <braintwo at gmail.com> writes:
>
> > I just figured out how to make it generic (but please let's do this in a
> > 2nd change).
>
> Cool! But I agree that should be a followup change. If nothing else, it
> has a new failure mode, since it must fail if gcd(start, diff) > 1.
>
> > I'd suggest "negative_mod_ui" or "distance_ui" to replace "nextmod_func"
> > and  "increment_ui" to replace "nextseq_fun"
> > Also potentially adding the comment
> >
> > -       m = nextmod_fuct(p, prime)
> > +      /* Distance to next multiple of prime */
> > +      m = negative_mod_ui(p, prime);
>
> Sounds good to me.
>
> Regards,
> /Niels
>
> --
> Niels Möller. PGP-encrypted email is preferred. Keyid 368C6677.
> Internet email is subject to wholesale government surveillance.
>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: time_nextprime.png
Type: image/png
Size: 22446 bytes
Desc: not available
URL: <https://gmplib.org/list-archives/gmp-devel/attachments/20201016/1c305533/attachment-0001.png>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: prevprime_20201016.patch
Type: text/x-patch
Size: 16738 bytes
Desc: not available
URL: <https://gmplib.org/list-archives/gmp-devel/attachments/20201016/1c305533/attachment-0001.bin>


More information about the gmp-devel mailing list