Path: newsspool2.news.pas.earthlink.net!stamper.news.pas.earthlink.net!stamper.news.atl.earthlink.net!elnk-atl-nf1!newsfeed.earthlink.net!in.100proofnews.com!in.100proofnews.com!newsfeed.cs.utexas.edu!news.cs.utexas.edu!not-for-mail
Message-ID: <bjlapt$nj4$1@zorkmid.cs.utexas.edu>
From: djimenez@cs.utexas.edu (Daniel A. Jimenez)
Newsgroups: sci.math
Subject: Re: Second Call For Primecounter Contest Entries
Date: 9 Sep 2003 14:48:13 -0500
References: <bgbs21-kr1.ln1@lexi2.athghost7038suus.net> <Mun7b.4876$ej1.2156@nwrdny01.gnilink.net> <bjl2dp$l9d$1@zorkmid.cs.utexas.edu> <H7p7b.5190$ej1.4189@nwrdny01.gnilink.net>
Lines: 112
Organization: CS Dept, University of Texas at Austin
Sender: djimenez@zorkmid.cs.utexas.edu
NNTP-Posting-Host: zorkmid.cs.utexas.edu
X-Trace: news.cs.utexas.edu 1063136894 20045 128.83.120.248 (9 Sep 2003 19:48:14 GMT)
X-Complaints-To: usenet@cs.utexas.edu
NNTP-Posting-Date: Tue, 9 Sep 2003 19:48:14 +0000 (UTC)
X-Received-Date: Tue, 09 Sep 2003 12:48:17 PDT (newsspool2.news.pas.earthlink.net)
Xref: lexi2.athghost7038suus.net sci.math:36798

In article <H7p7b.5190$ej1.4189@nwrdny01.gnilink.net>,
Stan Gula <sgula@bellatlantic.net.remove.invalid> wrote:
>"Daniel A. Jimenez" <djimenez@cs.utexas.edu> wrote in message
>news:bjl2dp$l9d$1@zorkmid.cs.utexas.edu...
>
>The JSH program variants produce the same answers through 4*10^9.  So your
>answer for 10^10 is way off. 

Hmm.
>
>Thanks for the info.  I think we've won the contest<g>.  This was a lot of
>fun.

Yes, I've been having fun, too.  I've got one more modification (sorry,
I won't promise to stop, but I'll try :-)  Notice that the loop in S2 only
needs to iterate over the primes.  I peeled off the first iteration of
the loop for i=2, then propagated a bunch of constants to simplfy things.
I moved the code inside the loop to a function called "compute_sum," then
had the inner loop iterate over values of i of the form 6*k+1 and 6*k+5
where k is an integer; all primes except for 2 and 3 take this form.
The result is 30% faster for large values on a Pentium 4 and about 7%
(there's a lot of noise in the measurement) on an Athlon.  Here's the code:

#include <iostream.h>
#include <time.h>
#include <stdlib.h>

static unsigned S2(unsigned x, unsigned yin);

#define cache_size 65536

int f_cache[cache_size];

static unsigned JSHpi1(unsigned xin) {

	// cache most common answers

	if (xin<cache_size) {
		if (f_cache[xin - 1] == -1)
			f_cache[xin - 1] = xin - S2 (xin, xin) - 1;
		return f_cache[xin - 1];
	}
	return xin - S2 (xin, xin) - 1;
}

static unsigned compute_sum (unsigned i, unsigned x) {
	unsigned a1, a2, a3, sum1, sum2, j;
   	a1 = JSHpi1 (i);
   	a2 = JSHpi1 (i - 1);
	sum2 = a1 - a2;
	j = (i-1)*(i-1);
	if (sum2 != 0) {
		unsigned tmp2 = x / i;
		if (j < tmp2)
			a3 = tmp2 - S2 (tmp2, j) - 1;
		else
			a3 = JSHpi1 (tmp2);
		sum1 = a3 - a2;
		return sum1 * sum2;
	} else return 0;
}

static unsigned S2 (unsigned x, unsigned yin) {
	unsigned sum = 0, i, j, a3;

	if (4 > yin) return sum;
	int tmp2 = x / 2;
	if (2 < tmp2)
		a3 = tmp2 - S2 (tmp2, 2) - 1;
	else
		a3 = JSHpi1 (tmp2);
	sum += a3;
	if (9 <= yin) sum += compute_sum (3, x);
	if (25 <= yin) sum += compute_sum (5, x);
	for (i=6; ; i+=6) {
		j = i + 1;
		if (j*j > yin) return sum;
		sum += compute_sum (j, x);
		j = i + 5;
		if (j*j > yin) return sum;
		sum += compute_sum (j, x);
	}
}

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

	// cache elements are marked as uninitialized

	for (int i=0; i<cache_size; i++) f_cache[i] = -1;
	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 = JSHpi1(input);
	end = clock();
	cout << "Prime count (JSH/SG): " << p << endl;
	//cout << "      Time (sec) : " << (end-start)/CLK_TCK << endl << endl;
	return 0;
}
-- 
Daniel A. Jiménez                 djimenez@cs.utexas.edu
Assistant Professor               djimenez@cs.rutgers.edu
Department of Computer Science
Rutgers University