Path: newsspool2.news.pas.earthlink.net!stamper.news.pas.earthlink.net!stamper.news.atl.earthlink.net!elnk-atl-nf1!newsfeed.earthlink.net!newshosting.com!news-xfer1.atl.newshosting.com!newsfeed.icl.net!newsfeed.fjserv.net!diablo.theplanet.net!news.theplanet.net!christian.bau
Message-ID: <christian.bau-7F4291.23461901092003@slb-newsm1.svr.pol.co.uk>
From: Christian Bau <christian.bau@cbau.freeserve.co.uk>
Newsgroups: sci.math
Subject: Harris, eat this: Vastly superior prime counting function
Date: Mon, 01 Sep 2003 23:46:19 +0100
Lines: 50
NNTP-Posting-Host: 81.77.2.1
X-Trace: news8.svr.pol.co.uk 1062456380 23374 81.77.2.1 (1 Sep 2003 22:46:20 GMT)
NNTP-Posting-Date: 1 Sep 2003 22:46:20 GMT
X-Complaints-To: abuse@theplanet.net
User-Agent: MT-NewsWatcher/3.2 (PPC Mac OS X)
X-Received-Date: Mon, 01 Sep 2003 15:46:20 PDT (newsspool2.news.pas.earthlink.net)
Xref: lexi2.athghost7038suus.net sci.math:35120

As everybody knows by now, James' Harris claim to fame is that he has 
supposedly found a prime counting function that can calculate pi (N), 
that is the number of primes <= N, with space complexity 0. And as the 
more observant readers have noticed, he is (as usual) wrong or lying. 
His prime counting function has space complexity O (log log N). 

To demonstrate what true mathematical genius can achieve, I would like 
you to take a look at the following prime counting function, with a 
vastly superior space complexity of O (1), implemented as a C function:

unsigned long long pi (unsigned long long x) {

   unsigned long long i, j, k, sum; 

   for (i = 2, sum = 0; i <= x; ++i, sum += k) {
      for (j = 2, k = 1; j < i; ++j) {
         if (i % j == 0) k = 0; 
      }
   }

   return sum;
}

Not only is the space complexity of this function vastly superior to 
that of Harris' program. What is more important is that this function 
will give the correct answer for any x in the range 0 <= x <= 2^64 - 2, 
which is an improvement by several orders of magnitude over Harris' 
function. And all this with an algorithm that is not only much simpler 
than Harris', but also much faster. 

To make matters worse for Harris, two very slight modifications improve 
the time complexity of my algorithm from O (N^2) to O (N^1.5 / log N), 
without increasing space complexity: 

unsigned long long pi (unsigned long long x) {

   unsigned long long i, j, k, sum; 

   for (i = 2, sum = 0; i * i <= x; ++i, sum += k) {
      for (j = 2, k = 1; j < i; ++j) {
         if (i % j == 0) { k = 0; break; }
      }
   }

   return sum;
}

Unfortunately, this function will only give the correct result for 
values of x in the much smaller range 0 <= x <= 2^64 - 2^33. Still 
better than Harris' formula on every account.