Ciao, Il Mer, 12 Febbraio 2020 7:26 am, Niels Möller ha scritto: > Marco Bodrato <bodr...@mail.dm.unipi.it> writes:
>> Maybe my estimates are wrong. If they are not, the limit for trial >> division should be increased more than linearly on the size of the > And current code uses > prime_limit = nbits / 2; > Why the constant "/ 2"? No idea, this code seems to be written by > Torbjörn's and me a decade ago. Before the rewrite, the code was void mpz_nextprime (mpz_ptr p, mpz_srcptr t) { mpz_add_ui (p, t, 1L); while (! mpz_probab_prime_p (p, 5)) mpz_add_ui (p, p, 1L); } Which had the only benefit (from my personal point of view) of returning the next (possibly negative) probab_prime when a negative value was given as an input :-) The "/2" is one of the many constant that should be interesting to tune, but it's not easy to understand exactly how to, because we do not even really know if we need a multiplicative constant or some other curve. >> A possible error in my analysis: I assumed a "constant cost" for each >> new prime. That's true when updating the residues, but each new number >> in the initial loop on _tdiv_ui imply a cost that is linear on the >> bit-size of the number x. > And for a small prime gap (common case), this cost should be the main > part of the sieving. So it would make sense to optimize it. If we also > use the ptab, we could compute modulo single-limb prime products using > precomputed constants. Yes, of course. And the next question will be: should we generate on the fly an even larger table of primes when the required size grows beyond the precomputed table? Ĝis, m _______________________________________________ gmp-devel mailing list gmp-devel@gmplib.org https://gmplib.org/mailman/listinfo/gmp-devel