braintwo at gmail.com
Thu Oct 15 23:47:56 UTC 2020
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
>From previous example looking at p=401
(1000000 * modular_inverse(-1 * delta, 401)) % 401 = (1000000 * -1) %
401 = 94
and validated (1000000 + 1 * 94) % 401 = 0
(1000000 * modular_inverse(-1 * delta, 401)) % 401 = (1000000) % 401 =
and validated 1000000 + -1 * 307) % 401 = 0
(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)) %
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);
> Niels Möller. PGP-encrypted email is preferred. Keyid 368C6677.
> Internet email is subject to wholesale government surveillance.
More information about the gmp-devel