mpz_prevprime

[Marco Bodrato]

Ciao,

Il Gio, 22 Agosto 2019 7:24 am, Niels Möller ha scritto:
> Seth Troisi <braintwo at gmail.com> writes:

>> In order to profile parts of this I also added tune/speed support for
>> mpz_nextprime

>> Note that I change the behavior of s->size to mean size bits instead
>> of limbs for for measuring mpz_nextprime, as the function is slow (in

It's not easy to discuss code if the code is elsewhere... can you post it
here?

I glanced at your proposed code, with mpz_tdiv_r_2exp you make sure that
the operand has "at most" s->size bits. I'd add mpz_setbit to make sure
that the operand has exactly the given bit-size.

> Good. I imagine mpz_nextprime performance has some room for improvement.
>
> For benchmarking, maybe one should use something other than arithmetic
> mean for averaging, since some numbers will be much slower than others?

Currently tune/speed usually use the mean of many calls with the same input.
Maybe for _nextprime we should use a chain? Give the previous result as
the new input.

>> For implementing mpz_prevprime, I tried to reuse as much code as

> Maybe it would make sense to generalize a bit further, and write a
> function to find the first prime (if any) in an arithmetic sequence.
> I.e., find the smallest k >= such that A + kB is prime (if any). A

Interesting idea.

>> Finally for mpz_prevprime(rop, op <= 2) it's not clear what rop should
>> be set to, so I use the smallest prime (2).
>
> I'd prefer using the function return value to indicate success/failure.

I know that my proposal is an incompatible change for the interface... but
I'd suggest to extend the range for mpz_nextprime. Can we consider both
positive and negative primes?

Curently, mpz_nextprime returns 2 for negative inputs. What if we extend
the function in such a way that _nextprime(-10) returns -7? Then the
implementation of
_prevprime(n)
will be
- _nextprime( - n)
and _prevprime(2) will coherently be -2 :-)


Ĝis,
m

-- 
http://bodrato.it/papers/