mpz_prevprime
Marco Bodrato
bodrato at mail.dm.unipi.it
Thu Aug 22 06:48:18 UTC 2019
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/
More information about the gmp-devel
mailing list