mpz_prevprime

[Marco Bodrato]

Ciao,

Il Ven, 16 Ottobre 2020 1:47 am, Seth Troisi ha scritto:
> On Thu, Oct 15, 2020 at 10:44 AM Niels Möller <nisse at lysator.liu.se>
>> Seth Troisi <braintwo at gmail.com> writes:
>> > Technically I can restructure the code to make both use with
>> mpz_fdiv_ui

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

Well, both mpz_fdiv and mpz_cdiv have if statements in their code, to
differently handle positive and negative numbers.
We can avoid those branches using tdiv, and add one here (the compiler may
use a cmov). I mean:

/* we have 0 < prime <= 150000001 < 2^28, because of calculate_sievelimit */
#if GMP_NUMB_BITS >= 28
   m = mpn_mod_1 (PTR (p), SIZ (p), (mp_limb_t) prime);
#else
   m = mpz_tdiv_ui(p, prime);
#endif
   m = (diff > 0) ? prime - m : m;

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

We don't have such a function :-) But adding a static function like that
here, assuming that p is always positive and greater than |si|, with a
single branch... can be a good idea.

Ĝis,
m