mpz_prevprime

[Seth Troisi]

On Thu, Oct 15, 2020 at 10:44 AM Niels Möller <nisse at lysator.liu.se> wrote:

> Seth Troisi <braintwo at gmail.com> writes:
>
> > for nextprime sieving the interval 1,000,000 to 1,000,500
> > p is the start of the interval (1,000,000) in this case
> > let prime = 401
> > (-p) % prime = mpz_cdiv_ui(p, prime) = 94
> > the 94th number in the sieve (p + 94 = 100094) is the first number
> > divisible by 401 in the interval
> >
> > for previous prime we can reuse almost all of the logic but with fdiv_ui
> > sieving the interval 1,000,000 to 999,500
> > set p to the "start" of the interval (1,000,000) in this case
> > p % prime = mpz_fdiv_ui(p, prime) = 307
> > the 307th number in the sieve (p - 307 = 999693) is the first number
> > divisible by 401 in the interval.
>
> Thanks for the explanation.
>
> > Technically I can restructure the code to make both use with mpz_fdiv_ui
> > My quick and dirty attempt
> >
> > diff -r 1e638b839cbe mpz/nextprime.c
> > --- a/mpz/nextprime.c   Thu Oct 15 01:13:43 2020 -0700
> > +++ b/mpz/nextprime.c   Thu Oct 15 01:30:03 2020 -0700
> > @@ -156,7 +156,7 @@
> >
> >  static int
> >  findnext (mpz_ptr p,
> > -          unsigned long(*nextmod_func)(const mpz_t, unsigned long),
> > +          char direction,
> >            void(*nextseq_func)(mpz_t, const mpz_t, unsigned long))
>
> I see. I don't think it's worth taking out a function pointer if it's
> replaced with a flag and a couple of if statements. It would be neat if
> it could be done similarly to findnext_small
>
>   static int
>   findnext (mpz_ptr p, signed diff)
>
> with diff being +2 or -2 (and possibly generalized further), and no
> conditionals, e.g.,
>
>   mpz_add_si (p, p, diff * (odds_in_composite_sieve-1));
>
> But I imagine you've already considered that, and found it not so easy
> (if at all reasonably possible).
>
The vast majority of time is spent in mpz_millerrabin, and a small amount
doing mods or finding primes.
so a small amount of overhead handling special cases is fine.

I just figured out how to make it generic (but please let's do this in a
2nd change).

>From previous example looking at p=401
next_prime(start=1000000, delta=1)
    (1000000 * modular_inverse(-1 * delta, 401)) % 401 = (1000000 * -1) %
401 = 94
    and validated (1000000 + 1 * 94) % 401 = 0

next_prime(start=1000000, delta=-1)
    (1000000 * modular_inverse(-1 * delta, 401)) % 401 = (1000000) % 401 =
307
    and validated 1000000 + -1 * 307) % 401 = 0

next_prime(start=1000000, delta=5)
    (1000000 * modular_inverse(-1 * delta, 401)) % 401 = (1000000 * 80) %
401 = 99
   and validated (1000000 + 5 * 99) % 401 = 0

This works for both signs because modular_inverse(-X) % p = (-modular(X)) %
p
I'm haven't checked if this works for primes which share a factor with delta

>
> So I think the logic with function pointers is fine. I'd prefer
> different names though, mod_ui instead of nextmod_func, and something
> similar for the other one. Or at least drop the _func suffix, which
> might be descriptive of a typedef name, but not as the name of a
> argument or a local variable.
>
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);




> Regards,
> /Niels
>
> --
> Niels Möller. PGP-encrypted email is preferred. Keyid 368C6677.
> Internet email is subject to wholesale government surveillance.
>