mpz_prevprime

[Seth Troisi]

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 <bodrato at mail.dm.unipi.it>
wrote:

> Ciao,
>
> Il 2020-02-10 21:01 nisse at 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/
>