Path: newsspool2.news.pas.earthlink.net!stamper.news.pas.earthlink.net!elnk-nf2-pas!newsfeed.earthlink.net!wn14feed!wn13feed!wn11feed!worldnet.att.net!199.45.49.37!cyclone1.gnilink.net!spamkiller2.gnilink.net!nwrdny01.gnilink.net.POSTED!53ab2750!not-for-mail
Message-ID: <0j27b.3569$ej1.2908@nwrdny01.gnilink.net>
From: "Stan Gula" <sgula@bellatlantic.net.remove.invalid>
Newsgroups: sci.math
Subject: Re: Second Call For Primecounter Contest Entries
Date: Mon, 08 Sep 2003 16:41:32 GMT
References: <bgbs21-kr1.ln1@lexi2.athghost7038suus.net> <weN6b.2652$ej1.664@nwrdny01.gnilink.net> <aZN6b.6040$w41.2164@nwrdny02.gnilink.net> <jh1t21-n72.ln1@lexi2.athghost7038suus.net> <ejW6b.3223$ej1.195@nwrdny01.gnilink.net> <iubu21-0p2.ln1@lexi2.athghost7038suus.net>
Lines: 137
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.145.16
X-Complaints-To: abuse@verizon.net
X-Trace: nwrdny01.gnilink.net 1063039292 151.203.145.16 (Mon, 08 Sep 2003 12:41:32 EDT)
NNTP-Posting-Date: Mon, 08 Sep 2003 12:41:32 EDT
X-Received-Date: Mon, 08 Sep 2003 09:41:32 PDT (newsspool2.news.pas.earthlink.net)
Xref: lexi2.athghost7038suus.net sci.math:36514

"The Ghost In The Machine" <ewill@sirius.athghost7038suus.net> wrote in
message news:iubu21-0p2.ln1@lexi2.athghost7038suus.net...
> In sci.math, Stan Gula
> <sgula@bellatlantic.net.remove.invalid>
>  wrote
> on Mon, 08 Sep 2003 07:35:38 GMT
> <ejW6b.3223$ej1.195@nwrdny01.gnilink.net>:
> > "The Ghost In The Machine" <ewill@sirius.athghost7038suus.net> wrote in
> > message news:jh1t21-n72.ln1@lexi2.athghost7038suus.net...
> >>
> >> Sorry, I can't accept your submission at present as all of the values
> >> are way off, and I don't see an obvious way of fixing it.  Perhaps you
> >> can point out the flaw?
> > <snip>
> >>
> >> unsigned long long pi(unsigned long long x)
> >> {
> >> return (unsigned long long) JSHpi2(x, sqrt(x));
> >> }
> >>
> >
> > Problem is right there...  Documentation error!
> >
> > I removed all the usage of sqrt() so the call to JSHpi2 should have the
form
> > JSHpi2(x,x) - I should have provided a test harness to document that
usage.
> >
> > My harness included stdlib.h which has a template implementation of
min() -
> > the macro form is fine as stated.
> >
> > Thanks.
> > --Stan Gula
> >
>
> With that fix it works beautifully.  Thank you; I can now accept this
> submission.  :-)  Results will shortly be available at
> http://home.earthlink.net/~ewill3/math/primecounters/index.html .
>
> You're between legendrephi and jamesharris3 in the rankings, so far.
>

One more attempt and I have to retire.  I am now showing times as good as
Daniel A. Jimenez for tests up to 10^8 and I'm beating him at 10^9.  The key
was running some tests and watching how the recursion works and caching the
first 32 values of pi(x).  James' guess that skipping evaluations at even
values didn't help and in fact the time to do the test to see if I could
skip the evaluations took longer than the amount of time I could save...
Note that in his S2 function, the evaluation of sum1 is skipped when
sum2==0, and it is obvious that this is so for all even values (except 2).

//last submission, Stan Gula mods to the JSH prime counter---
//removed the sqrt calls, and cached the first 32 values of pi(x)
#include <iostream.h>
#include <time.h>
#include <stdlib.h>

unsigned S2(unsigned x, unsigned yin);

unsigned JSHpi(unsigned xin, unsigned yin)
{
//cache most common answers
#define cache_size 32
  static unsigned f[cache_size]=
    {0,1,2,2,3,3,4,4,4,4,5,5,6,6,6,6,7,7,8,8,8,8,9,9,9,9,9,9,10,10,11,11};
  if(xin==yin && (xin<cache_size))return f[xin-1];
  return (xin-S2(xin,yin)-1);
}

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 = ( JSHpi(i,i) - JSHpi(i-dx,i-dx));
    if (sum2!=0){
      int tmp = (i-dx)*(i-dx),
      tmp2=x/i;
      sum1 = ( JSHpi(x/i,min(tmp,tmp2)) -
          JSHpi(i-dx,i-dx));
      sum+=(sum1 * sum2);
    }
  } return sum;
}

int main(int argc,char *argv[])
{
  unsigned p;
  clock_t start,end;

  if(argc<2)
  {
    cout << "You need to provide an integer value on the command
line"<<endl;
    return 0;
  }

    int input = atol(argv[1]);
    if(input<=0)
    {
      cout << "You need to provide an integer value >0 on the command
line"<<endl;
    }

    start = clock();
    p = JSHpi(input,input);
    end = clock();
    cout << "Prime count (JSH/SG): " << p << endl;
    cout << "      Time (sec) : " << (end-start)/CLK_TCK << endl << endl;
    return 0;
}

Some test results compared to Daniel's code:
pmbench 100000000
 Prime count (JSH/SG): 5761455
      Time (sec) : 6.8
 Prime count (DJ): 5761455
      Time (sec) : 6.78

pmbench 1000000000
 Prime count (JSH/SG): 50847534
      Time (sec) : 67.346
 Prime count (DJ): 50847534
      Time (sec) : 98.913

You can play with the value of "cache_size" in JSHpi() to see the results of
various cache sizes.  It might be worth pushing this further, but my goal
was to see if I could push it close to Daniel's results, and I think it's
there.

Regards,
Stan Gula (not a mathematician any more, but maybe a decent programmer)