From: xavier.gourdon@online.fr (Xavier Gourdon)
Subject: New record computation for pi(x), x=10^21
Date: 27 Oct 00 16:13:17 GMT
Newsgroups: sci.math.numberthy
Summary: [missing]

I am pleased to send you the value of a new record computation
of pi(x) = #{p<=x, p prime) :

pi(10^21) = 21 127 269 486 018 731 928

As always, this is close to the corresponding values of
Li(x) = int_2^m dt/log(t) and
R(x) = \sum_{n>0} mu(n)/n Li(x^{1/n}) :

Li(10^21) - Pi(10^21) = 597 394 254
  R(10^21) - Pi(10^21) = -86 432 204

CHECK :

This value has been checked by computing pi(10^21+10^8) with
a different parameter y used in the algorithm, and by counting
the number of primes in the inverval (10^21, 10^21+10^8].

The implementation was also checked on preceeding known values of pi(x)

computed by Marc Deleglise,  (see
http://www.utm.edu/research/primes/notes/md.html)
including Pi(10^20), Pi(2.10^19), Pi(10^19) and Pi(10^18).

TIME AND MEMORY :

The computation was distributed on two machines
and took 20 days (equivalent total time on Pentium II 350).
The verification took approximately the same time.
The memory needed was approximately 115 Mo.

ALGORITHM :

The algorithm used is a technical improvement of the algorithm in

Math Of Comp 1996 by Deleglise & Rivat : Computing Pi(x), the
Meissel, Lehmer, Lagarias, Miller, Odlyzko method.

The asymptotic time complexity remains unchanged O(x^{2/3}/log(x)^2),
but some constant factors have been saved.
The asymptotic space complexity has been decreased a bit, by a factor
log(x) at least
(I did not make precise asymptotic study for this).

A new feature has been introduced in the algorithm, permitting to
distribute the computation on several machines with NO MEMORY
EXCHANGE (expect the final result of each computation,
which has O(log(n)) bits), provided a precomputation taking
time O(x^{1/2}/log^{9/2}(x)) is done on each machine.
The problem of distributing the pi(x) computation by this algorithm
have already been considered in Computing pi(x): An analytic method,
J. C. Lagarias and A. M. Odlyzko, J. Algorithms, 8 (1987), pp. 173-191,

but memory exchange was needed.


More information will be soon available on my web site :

http://xavier.gourdon.free.fr/Constants/constants.html

I am also planning to start a project for a
distributed computation on the web to compute values of pi(x)
for values of x between 10^21 and 10^24.

Best regards,

Xavier Gourdon