Re: Fast primecounting implementation

From: flip (flip_alpha_at_safebunch.com)
Date: 09/29/03 

Date: Sun, 28 Sep 2003 16:23:52 -0700

"Christian Bau" <christian.bau@cbau.freeserve.co.uk> wrote in message
news:christian.bau-DB75D9.23513728092003@slb-newsm1.svr.pol.co.uk...
> A new version of my implementation of the Extended Meissel-Lehmer
> Algorithm for counting all prime numbers <= N is available from my
> webpage at
>
> www.cbau.freeserve.co.uk
>
> The new version has been tested intensively. Among other tests, it has
> calculated the values of pi (k * 10^18) for 1 <= k <= 18 correctly.
> Execution times on a Macintosh with 733 MHz and a PC with 1700 MHz are
> quite similar: pi (10^15) is calculated in about 50 seconds, pi (10^19)
> took a bit less than eight hours. pi (N) can be calculated for N <= 1.8
> * 10^19 using about 22 MB of memory.
>
> This version implements the algorithm relatively close to the
> description in the article by Lagarias, Miller and Odlyzko. I have added
> one of two major improvements due to Deleglise and Rivat; the second
> improvement will be added soon; thanks to Laurent Desnogues for the link
> to their article at
>
> http://www.ams.org/journal-getitem?pii=S0025-5718-96-00674-6
>
> I have replaced their method for counting the number of bits in a sieve
> with a brute force method that is much simpler and seems to run faster.
> Furthermore, most divisions can be replaced by multiplications which
> improves execution time significantly on the Macintosh version.
>
> Planned additions for the near future are:
>
> 1. Removing more unnecessary calculations as described by Deleglise and
> Rivat.
>
> 2. Cleaning up the code to produce a version that can be freely
> distributed.
>
> 3. Extending the code to calculate pi (x) for x >= 2^64
>
> 4. Add code to calculate the N-th prime for large N (thanks to Robert
> Israel for his info about the logarithmic integral which helps a lot
> with this calculation).
>
> 5. Add code that allows calculation of pi (x) for multiple values x
> simultaneously; this can be done significantly faster than calculating
> the results individually.

Thought some of you here might be interested in this ...