Path: newsspool2.news.pas.earthlink.net!stamper.news.pas.earthlink.net!newsread4.news.pas.earthlink.net.POSTED!not-for-mail
Message-ID: <3F5810B9.7A4A9791@ix.netcom.com>
From: "C. Bond" <cbond@ix.netcom.com>
Newsgroups: sci.physics,sci.math
Subject: Re: Prime counting C++ program, speed-up
Date: Fri, 05 Sep 2003 04:27:24 GMT
References: <3c65f87.0309040851.7bc10fca@posting.google.com> <9c9l21-var.ln1@lexi2.athghost7038suus.net>
Lines: 46
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.2.230
X-Complaints-To: abuse@earthlink.net
X-Trace: newsread4.news.pas.earthlink.net 1062736044 209.86.2.230 (Thu, 04 Sep 2003 21:27:24 PDT)
NNTP-Posting-Date: Thu, 04 Sep 2003 21:27:24 PDT
Organization: EarthLink Inc. -- http://www.EarthLink.net
X-Received-Date: Thu, 04 Sep 2003 21:27:24 PDT (newsspool2.news.pas.earthlink.net)
Xref: lexi2.athghost7038suus.net sci.physics:77776 sci.math:35842

The Ghost In The Machine wrote:

[snip new benchmark data]Again, thanks for taking the time to perform this
service. I have included another variation of Christian Bau's algorithm.
Perhaps you can run it when you have time. Also (and again), I cannot take
any credit for the algorithm as it is simply an enhancement of the code
originally posted by Christian. I probably won't submit another variation,
as I must now decide whether to port my own algorithm to this platform.

------------------------------------
//
// Modification of Christian Bau's
// prime counting algorithm
//
unsigned int cbpi2(unsigned int x){
    unsigned int i,j,k,idx,jdx,sum;
    static unsigned int skip[] = {4,2,4,2,4,6,2,6};

    if (x < 7) return(8*x+2)/13;

    idx = 0;
    for (i=7,sum=3;i <= x;i+=skip[idx++],sum += k) {
        idx &= 7;
        jdx = 0;
        for (j=7,k=1;j*j <= i;j += skip[jdx++]) {
            jdx &= 7;
            if (i % j) continue;
            else {
                k = 0;
                break;
            }
        }
    }
    return sum;
}
------------------------------------

--
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