nth_prime

[Seth Troisi]

On Tue, May 21, 2019 at 11:49 AM Niels Möller <nisse at lysator.liu.se> wrote:

> Seth Troisi <braintwo at gmail.com> writes:
>
> > 3. Use Legendre's Formula (github
> > <https://github.com/sethtroisi/libgmp/pull/9>)
>
> Any reference for this method? I've never read anything about efficient
> computation of the nth prime. A web search turns up this sketch:
>
> https://programmingpraxis.com/2011/07/22/counting-primes-using-legendres-formula/
> ,
> but it's not clear to me for how large sizes it is practical.
>

https://github.com/kimwalisch/primecount has state-of-the-art
implementations of several prime counting algorithms/methods.
There are paralleled and highly optimized for just this calculation but it
suggests Legendre's method can calculate prime_pi(10^13) in <1 second.
I'm targeting nth_prime(10^9) in <10 second. Currently it takes ~40 seconds
on my high-end machine.

http://mathworld.wolfram.com/PrimeCountingFunction.html is a reasonable
starting place and includes some references on the various methods.
They also have a page about the method
http://mathworld.wolfram.com/LegendresFormula.html

This paper references some of the history
https://www.ams.org/journals/mcom/1985-44-170/S0025-5718-1985-0777285-5/S0025-5718-1985-0777285-5.pdf



> It seems clear that an efficient nth prime can be implemented on top of
> an efficient \pi(k) = (number of primes <= k): Given n, first find some
> k such that \pi(k) \approx n, e.g., based on asymptotics and/or binary
> search. Next, compute \pi(k) exactly. Then enumerate primes close to k
> (sieving + primality tests) to identify the nth prime.
>

Exactly!
Mathematica (and some references) refer to this as prime_pi(k) = (number of
primes <= k) which I'll use below

My implementation uses the approximation
<https://github.com/sethtroisi/libgmp/pull/9/files#diff-c211dcbd00b3dc25f09a1e077b11f4a2R272>*
nth_prime(n) = n * ( log(n) + (log(log(n)) - 1))
I then refine this guess twice by calculating error = n - prime_pi(guess),
guess += log(n) * error
then calling next_prime(guess) some small number of times (this could
easily be improved with a sieve but in practice takes less than 5% of total
time)

My plan is to get [1] and [2] checked in, do some optimization of phi(n, x)
and check in [3].
After that look at the trade-off in readability, memory, and performance
for implementing Meissel's method.

*GMP has next_prime but no prev_prime so I have to make sure to
underestimate

On Tue, May 21, 2019 at 9:50 AM Niels Möller <nisse at lysator.liu.se> wrote:

> Seth Troisi <braintwo at gmail.com> writes:
>
> > I think 1. and 2. are as clean as I know how to make them (I don't see a
> > style guide so apology for formatting / style differences),
>
> To answer the easy question: See
> https://www.gnu.org/prep/standards/standards.html
>
> Regards,
> /Niels
>
> --
> Niels Möller. PGP-encrypted email is preferred. Keyid 368C6677.
> Internet email is subject to wholesale government surveillance.
>