 |
|
| Science Forum Index » Mathematics Forum » Computing Pi(x) and p_n |
|
Page 1 of 1 |
|
| Author |
Message |
| Guest |
 Posted: Tue Nov 14, 2006 11:31 pm |
|
|
|
|
I am not an expert in this area but perhaps this posting can clear the
air somewhat on prime counting functions:
The following is apparently the state of the art according to Chapter 9
of Bach and Shallit's book "Algorithmic Number Theory, Vol. I", unless
new breakthroughs have happened in the last 10 years or so--I don't
mean "breakthroughs" by JSH!
Let Pi(x)=number of prime numbers less than or equal to x
Let p_n = the n^th prime
If you had an algorithm to compute one of these quantities, you can
compute the other by using the first as an oracle in polynomial time
effort, since for n equal to 6 or more p_n lies in a small interval of
length n*log log n
p_n \in (n log n, n(log n + log log n))
and, for example, binary search can be used in this interval using
O(lg_2(n log log n))=O(lg n) queries to the oracle for Pi(x) looking
for r such that Pi(r)=n and Pi(r-1)=n-1.
There is an algorithm to compute Pi(x), due to Lagarias and Odlyzko
(Vol. 1052 of LNCS:176-193, 1984). This algorithm yields a time/memory
tradeoff, which can be tailored to use
O(x^(3/5 + \epsilon)) bit operations and O(x^(\epsilon)) storage space
or
O(x^(1/2+\epsilon)) bit operations and O(x^(1/4+\epsilon)) storage
for \epsilon an arbitrarily small positive number. The algorithm is
apparently based on numerical integration of transforms of the Riemann
zeta function.
Related algorithms are also mentioned in the same book. |
|
|
| Back to top |
|
|
|
| Tim Peters |
| Posted: Tue Nov 14, 2006 11:54 pm |
|
|
|
Guest
|
[serdar.boztas@ems.rmit.edu.au]
[quote:cb510bf6d4]I am not an expert in this area but perhaps this posting can clear the
air somewhat on prime counting functions:
[/quote:cb510bf6d4]
I'd be happy to give it a shot, but I couldn't really identify "a question"
below  BTW, I don't work in the field, but have followed it with at
least casual interest for decades. Caveat emptor.
[quote:cb510bf6d4]The following is apparently the state of the art according to Chapter 9
of Bach and Shallit's book "Algorithmic Number Theory, Vol. I",
[/quote:cb510bf6d4]
That remains an excellent reference (and my understanding is that plans for
Volume II were dropped).
[quote:cb510bf6d4]unless new breakthroughs have happened in the last 10 years or so--I
don't mean "breakthroughs" by JSH!
[/quote:cb510bf6d4]
No real theoretical breakthroughs that I know about.
[quote:cb510bf6d4]Let Pi(x)=number of prime numbers less than or equal to x
Let p_n = the n^th prime
If you had an algorithm to compute one of these quantities, you can
compute the other by using the first as an oracle in polynomial time
effort, since for n equal to 6 or more p_n lies in a small interval of
length n*log log n
p_n \in (n log n, n(log n + log log n))
and, for example, binary search can be used in this interval using
O(lg_2(n log log n))=O(lg n) queries to the oracle for Pi(x) looking
for r such that Pi(r)=n and Pi(r-1)=n-1.
There is an algorithm to compute Pi(x), due to Lagarias and Odlyzko
(Vol. 1052 of LNCS:176-193, 1984). This algorithm yields a time/memory
tradeoff, which can be tailored to use
O(x^(3/5 + \epsilon)) bit operations and O(x^(\epsilon)) storage space
or
O(x^(1/2+\epsilon)) bit operations and O(x^(1/4+\epsilon)) storage
for \epsilon an arbitrarily small positive number. The algorithm is
apparently based on numerical integration of transforms of the Riemann
zeta function.
[/quote:cb510bf6d4]
Note that while those have the best-so-far known O() behavior, to the best
of my knowledge they've never been implemented. They're difficult to
implement, and the "hidden constant factors" are believed to be so high that
they aren't /expected/ to run faster than the second-best known algorithms
before inputs get significantly larger than are practical on current
hardware.
[quote:cb510bf6d4]Related algorithms are also mentioned in the same book.
[/quote:cb510bf6d4]
The current record-holding algorithm (in "real life") is described in a
paper available here, which will lead you back to earlier papers upon which
it builds:
http://numbers.computation.free.fr/Constants/Primes/Pix/pixtableproject.html
That's firmly in the chain started by Meissel, and by now it should be
probably be called the Legendre - Meissel - Lehmer - Lagarias - Miller -
Odlyzko - Deleglise - Rivat - Gourdon method. Or just LMLLMODRG for short
;-)
These have reached the point of making heroic efforts to save a factor of
log log n in sub-steps. Going back to one of the earlier papers in the
Lagarias-Miller line, there was already a strong heuristic argument for
believing no further truly major improvements were likely in this line of
attack, and subsequent refinements haven't refuted that.
Refinements /have/ pushed the largest exact values for pi(n) known upward,
but that stalled out about 5 years ago (AFAIK), at pi(4*10^22); the
computation for pi(10^23) took about a year of CPU time but is known to be
incorrect (failed a consistency check), and apparently the code has gotten
so complex nobody yet has been able to figure out the cause. |
|
|
| Back to top |
|
|
|
|
|
All times are GMT - 5 Hours
The time now is Mon Dec 07, 2009 11:24 am
|
|