I worked your math and tested against some Constants I had, everything agrees.
This also matches much of my analysis in my prime gap search where I scale my sieve much more than linearly. On Tue, Feb 11, 2020, 2:13 PM Marco Bodrato <bodr...@mail.dm.unipi.it> wrote: > Ciao, > > Il 2020-02-10 21:01 ni...@lysator.liu.se ha scritto: > > On my laptop, it gives a speedup of about 25% for larger sizes. Not > > sure > > how to tune for small sizes, but clearly the old code clamping the size > > of the prime table based on the bit size is better than doing nothing. > > > > The computation of all the moduli could be speed up by using ptab, and > > by using precomputed reciprocals. Not clear to me how much the speed of > > that part matters. I haven't run any profiling. > > How often numbers pass the sieving if we use trial division up to > primelimit? > > Approximately 1/(ln(primelimit)*e^g), where g is the Eulero-Mascheroni > constant. Right? > > Assume, we had primelimit = e^n and we increase it to e^(n+1). > > The number of primes approximately was e^n/n, now it is e^(n+1)/(n+1). > > 1/(n*e^g) passed trial division, now only 1/((n+1)*e^g) pass it. > > For the numbers that did not pass trial division, nothing changes. > > For the numbers that did pass trial division, we add e^(n+1)/(n+1)-e^n/n > tests = e^n*(e-1-1/n)/(n+1). Can we assume a constant cost for each one > of this tests? > But for one every (n+1) of them, we can avoid any further test (they are > detected by the new trial divisions). Can we assume that the cost for > the additional test basically is the cost of Miller-Rabin? Let's call > this cost MR(x). > > So, increasing primelimit from e^n to e^(n+1), we pay > e^n*(e-1-1/n)/(n+1) and we gain MR(x)/(n+1). It is worth doing if > primelimit (e^n) is comparable with the cost MR(x). But the cost of > Miller-Rabin is more than quadratic on the bit-size of the number x, > right? > > 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 > numbers that are tested. > > > 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. > This observation gives again an almost linear relation between > primelimit and the bit-size of the number... and says that the speed of > the "update residues" loop is not so relevant, at least for large > numbers; but the speed of the initial moduli probably IS relevant. > > Ĝis, > m > > -- > http://bodrato.it/papers/ > _______________________________________________ gmp-devel mailing list gmp-devel@gmplib.org https://gmplib.org/mailman/listinfo/gmp-devel
