Path: newsspool2.news.pas.earthlink.net!stamper.news.pas.earthlink.net!elnk-nf2-pas!newsfeed.earthlink.net!newshub.sdsu.edu!cyclone.bc.net!news-in.mts.net!nf1.bellglobal.com!nf2.bellglobal.com!news20.bellglobal.com.POSTED!not-for-mail
Message-ID: <F9T5b.11379$Sq5.367845@news20.bellglobal.com>
From: David Bernier <david250@sympatico.ca>
Newsgroups: sci.math
Subject: Re: Prime counting benchmark
Date: Thu, 04 Sep 2003 23:11:34 -0400
References: <3F563F94.79F0D7C8@ix.netcom.com>
Lines: 108
User-Agent: Mozilla/5.0 (Windows; U; Windows NT 5.0; en-US; rv:1.4) Gecko/20030624 Netscape/7.1 (ax)
X-Accept-Language: en-us, en
MIME-Version: 1.0
In-Reply-To: <3F563F94.79F0D7C8@ix.netcom.com>
Content-Type: text/plain; charset=us-ascii; format=flowed
Content-Transfer-Encoding: 7bit
NNTP-Posting-Host: 67.68.130.241
X-Complaints-To: abuse@sympatico.ca
X-Trace: news20.bellglobal.com 1062731493 67.68.130.241 (Thu, 04 Sep 2003 23:11:33 EDT)
NNTP-Posting-Date: Thu, 04 Sep 2003 23:11:33 EDT
Organization: Bell Sympatico
X-Received-Date: Thu, 04 Sep 2003 20:19:25 PDT (newsspool2.news.pas.earthlink.net)
Xref: lexi2.athghost7038suus.net sci.math:35835


C. Bond wrote:
> I have taken the liberty of including a simple C++ benchmarking program
> in this post. It displays the results and the elapsed time for counting
> primes by 3 methods. One method is the JSH method he previously post in
> this newsgroup. The 2nd method is one by Christian Bau, but which has
> been rescaled to use native integer types so the range of application
> matches that of James' method. (This eliminates the long long integer
> which slows the code down but increases the range.) The 3rd method is a
> minor modification of Bau's method which simple skips the even integers.
> 
> Feel free to add your own routines and collect benchmard data at will.
> You will find that the comparative results are not only algorithm
> dependent, but also compiler dependent and platform dependent.
[...]

Of the 3 method's JSH's is the slowest, second slowest is Christian Bau's
and fastest is your modification of Bau's. (The modification to
Bau's method seemed to run in half the time, which makes sense
if the even numbers are skipped).

I tried input = 10^9 and gave up after 20 minutes (I think JSH's code
runs first in the benchmark tests ...)
Then I decided to switch to 10^8.

So in the main(), I removed the JSH and Bau methods and only kept
the modified Bau method.  Also, I changed some integer types to "long".

Then, I compared the time to James's PrimeCountH.java .  His java
program is much faster.

Here's a summary:

========================================================
Input positive integer: 100000000

Prime count (CRB): 5761455
       Time (sec) : 880

========================================================

pi(100,000,000)   =   	5,761,455  	 /*** Chris Caldwell ***/

========================================================

PrimeCountH:

java PrimeCountH 100000000
Sieve Time: 10
m_max=10001
pi(100000000)=5761455

Total Time: 30  /*** milliseconds ***/
=========================================================


David Bernier

------------------- modified & edited C++ code below:  --------------------

//
// prmbnch.cpp -- simple benchmark platform for testing prime counting
//                methods.
//
#include <iostream.h>
#include <math.h>
#include <time.h>

//
// Slight modification of Bau's method.
//
long cbpi(long x) {
     long i,j,k,sum;

     if (x < 5) return 2*x/3;
     for (i = 5,sum = 2;i <= x;i += 2,sum += k) {
         for (j = 3,k = 1;j*j <= i; j+=2) {
             if (i % j) continue;
             else {
                 k = 0;
                 break;
             }
         }
     }
     return sum;
}

int main()
{
     clock_t start,end;
     long input,p;

     cout <<"\nInput positive integer: ";
     cin >> input;
     cout << endl;


     start = clock();
     p = cbpi(input);
     end = clock();
     cout << "Prime count (CRB): " << p << endl;
     cout << "      Time (sec) : " << (end-start)/CLK_TCK << endl << endl;

     return 0;
}

---------------------------------------------------------------------