mpz_prevprime

[Niels Möller]

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).

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.

Regards,
/Niels

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