Path: newsspool2.news.pas.earthlink.net!stamper.news.pas.earthlink.net!newsread3.news.pas.earthlink.net.POSTED!not-for-mail
Message-ID: <3F563F94.79F0D7C8@ix.netcom.com>
From: "C. Bond" <cbond@ix.netcom.com>
Newsgroups: sci.math
Subject: Prime counting benchmark
Date: Wed, 03 Sep 2003 19:22:47 GMT
Lines: 128
X-Mailer: Mozilla 4.02 [en]C-DIAL  (Win95; U)
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
NNTP-Posting-Host: 209.86.0.150
X-Complaints-To: abuse@earthlink.net
X-Trace: newsread3.news.pas.earthlink.net 1062616967 209.86.0.150 (Wed, 03 Sep 2003 12:22:47 PDT)
NNTP-Posting-Date: Wed, 03 Sep 2003 12:22:47 PDT
Organization: EarthLink Inc. -- http://www.EarthLink.net
X-Received-Date: Wed, 03 Sep 2003 12:22:47 PDT (newsspool2.news.pas.earthlink.net)
Xref: lexi2.athghost7038suus.net sci.math:35478

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.

-----------------------------
//
// 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.
//
unsigned cbpi(unsigned x) {
    unsigned 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;
}

//
// Christian Bau's method for counting primes.
// (modified for native integer size.)
//
unsigned xpi(unsigned x) {
    unsigned i,j,k,sum;

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

//
//  James Harris' method for counting primes.
//  (unmodified)
//
double S(double x, double yin);
double pi(double xin,double yin){
    return ((int)xin - S(xin,yin) - 1);

}
double min(double x, double y) {
    return x>y?y:x;
}

double S(double x,double yin){
    double sum=0,sum1,sum2,dx=1;

    for (int i=2;i<=yin;i++) {
        sum1 = (pi(x/i,min(i-dx,sqrt(x/i)))-pi(i-dx,sqrt(i-dx)));
        sum2 = (pi(i,sqrt(i)) - pi(i-dx,sqrt(i-dx)));
        sum += (sum1*sum2);
    }
    return sum;
}


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

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

    start = clock();
    p = pi(input,sqrt(input));
    end = clock();
    cout << "Prime count (JSH): " << p << endl;
    cout << "      Time (sec) : " << (end-start)/CLK_TCK << endl <<
endl;

    start = clock();
    p = xpi(input);
    end = clock();
    cout << "Prime count (BAU): " << p << endl;
    cout << "      Time (sec) : " << (end-start)/CLK_TCK << endl <<
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;
}
--------------------------------

--
There are two things you must never attempt to prove: the unprovable --
and the obvious.
--
Democracy: The triumph of popularity over principle.
--
http://www.crbond.com