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

"C. Bond" wrote:

Just for the record, here are the timing results I get on my system for the
latest version of JSH's prime counting code (his recently posted integer
version) and several versions of Christian Bau's code. (My system is a Compaq
Laptop, 2GHz Pentium 4, Windows XP, running DOS.)

'Time' represents the elapsed time to compute the number of primes where the
argument is 1000000 (one million)

Code Time (sec)
JSH(new) 0.428
CBAU 1.412
CBAU1 0.711
CBAU2 0.324

On my system, the last variation of Bau's algorithm consistently outperforms
JSH's latest offering. This is rather unexpected, because the BAU codes are
simple, straightforward sieves.

The memory space requirements are (compiled with Borland C++):

JSH
----
324 bytes for code and local variables + about n*44 bytes for stack frame and
locals, where 'n' is the number of recursion levels (approx. 1 level per decade
of the argument). For an argument of 1000000 this is roughly: 760 bytes

CBAU2
--------
194 bytes for code and local variables. There is no recursion so this value is
independent of the argument.

I have been through this kind of benchmarking exercise before, and would like
to caution anyone interested that it isn't really possible to 'benchmark an
algorithm', but only to 'benchmark an implementation of an algorithm on a
specific platform'. Different platforms could produce results which not only
scale differently but change the order. Nevertheless, absent any metric except
unsupported claims, benchmarking has the benefit of at least providing an
objective metric.

Regarding Harris, "The Bell Curve" Herrnstein and Murray (softcover),
p. 279: Black and White IQ distributions proportional to ethnic
populations. One expects nothing of Harris on statistical grounds.
Given vast chronic bloated empirical exposition issuing from Harris,
we have received nothing. Harris is a credit to his race on the
average and in specific. (Note that sci.physics is inundated with
White Trash, too. The left end of the bell curve is a slum. Don't
live there.)

Harris is a child screaming at its presumed parent to look at him. It
makes no difference what he does, for the object of his exercise is
process not product, noise not content. "LOOK AT MEEEEE, MOMMY!"
Harris desperately, insanely (estranged from reality, hence his
refractory ignorance when charitably corrected) wants to be the
world's best at something. Harris is fundamentally broken. No form,
content, or volume of adult intervention will fix him because he
denies reality.

Harris is not well educated. He embraces this as carte blanche to
"discover" and demand credit for that which his betters have achieved
a century before. The very concept of education, of learning that
which has been rigorously validated by the rules of engagement, is
foreign to him. He therefore considers himself unconstrained by the
rules of a system ever conspiring to crush him because he has a
desperate appetite for the same boons enjoyed by those who have earned
them.

Harris is the logical product of Liberal social engineering. Whites
learn as juveniles and work as adults, then their income is stolen by
the govenrment and compassionately redistributed less user fees.
Blacks are not to be oppressed by historic White Protestant European
mores either in juvenile education or adult productivity. Blacks are
to be awarded what they "deserve."

http://www.apa.org/journals/psp/psp7761121.html

--
Uncle Al
http://www.mazepath.com/uncleal/
(Toxic URL! Unsafe for children and most mammals)
"Quis custodiet ipsos custodes?" The Net!

"C. Bond" wrote in message ...
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.

I posted something similar in basic about 6 nonths back. The sum of 7
added to the repeating series, [4,2,4,2,4,2,4,6,2,6] are the only sums
at any point that need to be factored which will eliminate all n== 0
(mod) 2, 0 (mod) 3 and 0 (mod) 5 throughout all summations. This makes
2,3,5 and 7 the first 4 primes.
How fast is this algorithm in c?
Basic is slow!

Thanks,

Dan

Dan wrote:

[snip variation of Christian Bau's algorithm]

I posted something similar in basic about 6 nonths back. The sum of 7
added to the repeating series, [4,2,4,2,4,2,4,6,2,6] are the only sums
at any point that need to be factored which will eliminate all n== 0
(mod) 2, 0 (mod) 3 and 0 (mod) 5 throughout all summations. This makes
2,3,5 and 7 the first 4 primes.
How fast is this algorithm in c?
Basic is slow!

Thanks,

Dan

On my platform (a Compaq Presario laptop, 2GHz Pentium 4, Windows XP), it consistently
outperforms JSH's most recent contribution. There may not be much difference in performance
between the C version and a compiled BASIC version, but I guess you just have to code 'em and
test 'em.

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

"C. Bond" wrote in message ...
Just for the record, here are the timing results I get on my system for the
latest version of JSH's prime counting code (his recently posted integer
version) and several versions of Christian Bau's code. (My system is a Compaq
Laptop, 2GHz Pentium 4, Windows XP, running DOS.)

'Time' represents the elapsed time to compute the number of primes where the
argument is 1000000 (one million)

Code Time (sec)
JSH(new) 0.428
CBAU 1.412
CBAU1 0.711
CBAU2 0.324

On my system, the last variation of Bau's algorithm consistently outperforms
JSH's latest offering. This is rather unexpected, because the BAU codes are
simple, straightforward sieves.

It's not unexpected given use of small numbers like 10^6 to test.

Now if you push away from the pure math with my C++ code the next way
to speed it up is to not check evens.

I'll leave that to interested readers to check but it should at least
double the speed.

Notice these are *algorithmic* improvements which steadily move you
away from the pure math into techniques for counting prime numbers.

I've already chased that trail to the extent that my PrimeCountH.java
blows away anything most of you can produce, forcing you to go to what
the professional mathematicians have managed, *if* you can find the
code, as I doubt many of you have the expertise to code it yourselves.

Though if you can I'd be interested in hearing about your exploits.

The memory space requirements are (compiled with Borland C++):

JSH
----
324 bytes for code and local variables + about n*44 bytes for stack frame and
locals, where 'n' is the number of recursion levels (approx. 1 level per decade
of the argument). For an argument of 1000000 this is roughly: 760 bytes

Now that's interesting.

CBAU2
--------
194 bytes for code and local variables. There is no recursion so this value is
independent of the argument.

I have been through this kind of benchmarking exercise before, and would like
to caution anyone interested that it isn't really possible to 'benchmark an
algorithm', but only to 'benchmark an implementation of an algorithm on a
specific platform'. Different platforms could produce results which not only
scale differently but change the order. Nevertheless, absent any metric except
unsupported claims, benchmarking has the benefit of at least providing an
objective metric.

I dare you to redo your benchmarking with 10^7 without even asking
that you make the further enhancements to my C++ program that I
mentioned as I'd like to confirm a suspicion.

Besides I'm curious to see if the recursion depth goes to 7.


James Harris

James Harris wrote:

[snip]

I dare you to redo your benchmarking with 10^7 without even asking
that you make the further enhancements to my C++ program that I
mentioned as I'd like to confirm a suspicion.

Besides I'm curious to see if the recursion depth goes to 7.

James Harris

I did. The recursion depth is already 8 at 10^6.

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