Path: newsspool2.news.pas.earthlink.net!stamper.news.pas.earthlink.net!elnk-pas-nf1!newsfeed.earthlink.net!small1.nntp.aus1.giganews.com!nntp.giganews.com!cyclone1.gnilink.net!spamkiller2.gnilink.net!nwrdny01.gnilink.net.POSTED!53ab2750!not-for-mail
Message-ID: <weN6b.2652$ej1.664@nwrdny01.gnilink.net>
From: "Stan Gula" <sgula@bellatlantic.net.remove.invalid>
Newsgroups: sci.math
Subject: Re: Second Call For Primecounter Contest Entries
Date: Sun, 07 Sep 2003 21:16:12 GMT
References: <bgbs21-kr1.ln1@lexi2.athghost7038suus.net>
Lines: 53
X-Priority: 3
X-MSMail-Priority: Normal
X-Newsreader: Microsoft Outlook Express 6.00.2800.1158
X-MimeOLE: Produced By Microsoft MimeOLE V6.00.2800.1165
NNTP-Posting-Host: 151.203.149.60
X-Complaints-To: abuse@verizon.net
X-Trace: nwrdny01.gnilink.net 1062969372 151.203.149.60 (Sun, 07 Sep 2003 17:16:12 EDT)
NNTP-Posting-Date: Sun, 07 Sep 2003 17:16:12 EDT
X-Received-Date: Sun, 07 Sep 2003 14:16:13 PDT (newsspool2.news.pas.earthlink.net)
Xref: lexi2.athghost7038suus.net sci.math:36355


"The Ghost In The Machine" <ewill@sirius.athghost7038suus.net> wrote in
message news:bgbs21-kr1.ln1@lexi2.athghost7038suus.net...
> This highly informal contest is still open until
> midnight PDT 2003-09-15.  So far it's been an interesting
> contest with some surprising results.  (Sorry, no prizes
> except for name recognition on my webpage.  :-) )

Oh, Ghostly one:

Although JSH is no longer interested in prime counting, I would be
interested in how my minor change to his integer version stacks up.  I
posted this on 9/5.  It removes all his calls to sqrt() which in my tests
produced better than 70% improvement in run speed.  Sorry, my compiler
doesn't have 'unsigned long long' so I didn't implement it as the project
specified because I have no means to test that (well I have cygwin and gcc,
but only use other cygwin tools).

//--- Improved JSH C++ prime counter with removal of all sqrt() calls
unsigned S2(unsigned x, unsigned yin);

unsigned JSHpi2(unsigned xin, unsigned yin)
{
  return (xin-S2(xin,yin)-1);
}

//Optionally, use a define instead of the above function to reduce function
calls and stack
//overhead
//#define JSHpi2 (xin,yin) (xin-S2(xin,yin)-1)
//use at the risk of losing type safety

unsigned S2(unsigned x, unsigned yin)
{
  unsigned sum=0, i, sum1, sum2;
  const unsigned dx=1;

  for(unsigned i=2; i*i<=yin; i++)
  {

    sum2 = ( pi2(i,i) - pi2(i-dx,i-dx));

    if (sum2!=0){
      int tmp = (i-dx)*(i-dx),
        tmp2=x/i;
      sum1 = ( pi2(x/i,min(tmp,tmp2)) -
          pi2(i-dx,i-dx)) ;
      sum+=(sum1 * sum2);
    }
  } return sum;
}