Path: newsspool2.news.pas.earthlink.net!stamper.news.pas.earthlink.net!elnk-pas-nf1!newsfeed.earthlink.net!newshub.sdsu.edu!headwall.stanford.edu!newsfeed.stanford.edu!postnews1.google.com!not-for-mail
Message-ID: <3c65f87.0309040851.7bc10fca@posting.google.com>
From: jstevh@msn.com (James Harris)
Newsgroups: sci.physics,sci.math
Subject: Prime counting C++ program, speed-up
Date: 4 Sep 2003 09:51:36 -0700
Lines: 63
Organization: http://groups.google.com/
NNTP-Posting-Host: 67.192.35.50
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: 8bit
X-Trace: posting.google.com 1062694297 27043 127.0.0.1 (4 Sep 2003 16:51:37 GMT)
X-Complaints-To: groups-abuse@google.com
NNTP-Posting-Date: 4 Sep 2003 16:51:37 GMT
X-Received-Date: Thu, 04 Sep 2003 09:51:38 PDT (newsspool2.news.pas.earthlink.net)
Xref: lexi2.athghost7038suus.net sci.physics:77513 sci.math:35655

For some odd reason a few people seem especially fixated on the
slowness of the C++ program that I posted, which I kept saying is
configured for an easy switch to the continuous field so that you can
make a numerical calculation of the partial differential.

In any event rather than sit by while people kept ragging on the
program I thought I'd point out a couple of quick speed-ups, though
it's still a lot slower than algorithms I've developed, but it's a
good way to give you some sense of reality versus what posters often
think is reality.

The two changes are to use ints instead of doubles, and don't do the
second calculation if sum2==0.

Now that second one seemed to evade quite a few of you which I find
odd.

I didn't feel like compiling to check, so you might have to fix what
follows.


James Harris

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

#include <iostream.h>
#include <math.h>

int S(int x, int yin);
int pi(int xin, int yin)
{
  return (xin-S(xin,yin)-1);
}

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

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

  for(int i=2; i<=yin; i++)
  {

    sum2 = ( pi(i,(int)sqrt(i)) - pi(i-dx,(int)sqrt(i-dx)));

    if (sum2!=0){
      sum1 = ( pi(x/i,min(i-dx,(int)sqrt(x/i))) -
pi(i-dx,(int)sqrt(i-dx))) ;
      sum+=(sum1 * sum2);
    }
  } return sum;
}
int main()
{
  int input;
  cout <<"Input positive integer"<<endl;
  cin>>input;
  cout << pi(input,(int)sqrt(input)) << endl;
  return 0;
}