### Thursday, March 17, 2005

## Timing tests, PrimeCountH.java program against the world

I like to talk about tests done a couple of years ago where I say my PrimeCountH.java, a dinky program I kind of threw together back when I was chasing the speed thing with my research, compared ok against Mathematica, though Mathematica did clearly kick its butt.

But how badly?

I'm going to include the program here, which I doubt could be done with the comparable program in Mathematica, or in any challenging program, so people who like to do these kinds of things can do a timing test.

Now upfront I expect my program to be beaten rather soundly, but I also expect it to do far better than you'd think some small Java program, based on my research, should do.

Ok, then I'm including the program in this post, so people can copy it out and run it!!!

Easy for you people who can do Java.

Though the wrapping is a problem, in a couple of places easily seen, so you will have to do just a little workd to get it to compile.

If it's too problematic for you I might start up a Yahoo! Group and stick it there, but it's really not that hard to just copy from here and get the program to compile.

James Harris

//Written by James S. Harris. Copyright 2002-2003. All rights reserved.

//My suggestion is to write your own version modifying this one.

//Commercial use is not permitted without my written permission.

//Proper attribution might get me some credit for having found the prime counting function

//So play with this and share, and *please* mention where you got it from.

import java.util.*;

public class PrimeCountH {

public static void main(String[] args) {

long N = Long.parseLong(args[0]);

long displayN = N;

//Internally the program only uses even N, so this handles

//if someone puts in an odd number

if (N!=1 && N%2!=0) N++;

PrimeCountH p = new PrimeCountH();

//I have two instances because that it made it easy for printing out

the prime

PrimeCountH.p1 = new PrimeCountH();

long t1 = System.currentTimeMillis();

m_t = t1;

int m_max = (int)Math.sqrt(N)+1;

//Note that I am building a bigger prime list than necessary

//It would all work with m_max, but a bigger prime list speeds things

up

if (N>120){

PrimeCountH.doSieve(8*m_max);

System.out.println("Sieve Time: "+(System.currentTimeMillis() -

t1));

}

//Put "true" in as your second argument to see more output

if (args.length>1 && args[1].equals("true")) p.printFlag=true;

System.out.println("m_max="+m_max);

System.out.println("pi("+displayN+")="+p.pi(N));

System.out.println("");

System.out.println("Total Time: "+(System.currentTimeMillis() - t1));

System.out.println("");

}

public static PrimeCountH p1;

public boolean printFlag;

public String primes="2, 3, 5, 7, ";

public static long t, dt, tot;

public static long y;

public static int x;

public static int[] primeList;

public static int primeCount;

public static int maxPrime;

public static long m_t;

public static void doSieve(int m_max){

//I separated this part so those of you who want to do your own sieve

//can easily put it in place.

//Just remember to put m_max at the end of your prime list array

//I don't claim that this is the fastest way to do it.

boolean[] temp = new boolean[m_max/2+1];

if (m_max>10000){

PrimeCountH sieveSize = new PrimeCountH();

doSieve((int)Math.sqrt(m_max)+1);

m_max+=m_max&1;

int size = sieveSize.pi(m_max);

primeList = new int[size+2];

int incr=1;

primeList[0]=2;

int i;

for (i=3; i<(int)Math.sqrt(m_max)+1; i+=2){

if (temp[(i-1)>>1]==false){

for (int j=i; j<m_max/i+1; j+=2){

temp[(i*j-1)>>1]=true;

}

primeList[incr]=i;

incr++;

}

}

for (; i<m_max; i+=2){

if (temp[(i-1)>>1]==false){

primeList[incr]=i;

incr++;

}

}

primeCount = incr;

primeList[incr]=m_max;

maxPrime = primeList[incr-1];

}

else {

for (int i=3; i<(int)Math.sqrt(m_max)+1; i+=2){

if (temp[(i-1)>>1]==false){

for (int j=i; j<m_max/i+1; j+=2){

temp[(i*j-1)>>1]=true;

}

}

}

int incr=2;

for (int i=2; i<m_max/2; i++){

if (temp[i]==false) incr++;

}

primeList = new int[incr+1];

incr=2;

primeList[0]=2;

primeList[1]=3;

for (int i=2; i<m_max/2; i++){

if (temp[i]==false){

primeList[incr]=(i<<1)+1;

incr++;

}

}

primeCount = incr;

primeList[incr]=m_max;

maxPrime = primeList[incr-1];

}

}

public int pi(int N){

if (N<121){

if (N<9) return N/2;

if (N<25) return N/2 - (N-4)/6;

if (N<49) return N/2 -(N-4)/6 - (N-16)/10 + (N-16)/30;

return N/2 -(N-4)/6 - (N-16)/10 + (N-16)/30 - (N-36)/14 + (N-22)/42;

}

//The code that follows is what makes a giant speed improvement

if (N<maxPrime){

int size= primeCount>>1;

if (N>>2 < size) size = (int)N>>2;

byte goForward;

int pos = size;

int prime;

while(size>0) {

prime = primeList[pos];

if (prime<N) goForward=1;

else if (prime>N) goForward=-1;

else break;

size=size>>1;

pos = pos + size*goForward;

}

if (pos<primeCount-1) {

prime = primeList[pos+1];

if (prime<N){

do{

pos++;

prime = primeList[pos+1];

} while (prime<N);

}

}

prime = primeList[pos];

if (prime>N){

do{

pos--;

prime = primeList[pos];

} while (prime>N);

}

// System.out.println("pi["+N+"]="+(pos+1));

// System.out.println("prime["+pos+"]="+primeList[pos]);

// System.out.println("");

return (pos+1);

}

int S=0;

int dS=0;

int p=11;

boolean preTransition=true;

int m_max = (int)Math.sqrt(N)+1;

for (int c=4; p<m_max; c++){

x = N/p;

x += x&1;

if (preTransition){

if (p<(int)Math.sqrt(x)+1){

dS = p1.pi(x, p) - c;

}

else {

if (printFlag){

System.out.println("Time to transion was

"+(System.currentTimeMillis() - m_t));

System.out.println("Transition prime equals "+p);

}

dS = p1.pi(x) - c;

preTransition=false;

}

}

else dS = p1.pi(x) - c;

S += dS;

if (false){//printFlag ){

System.out.println("prime="+p+", dS="+dS);

primes+=p +", ";

System.out.println("");

}

p=primeList[c+1];

}

if (false){//printFlag) {

System.out.println(primes);

System.out.println("");

System.out.println("S="+S);

System.out.println("");

}

return N/2 -(N-4)/6 - (N-16)/10 + (N-16)/30 - (N-8)/14 + (N-22)/42

+ (N-106)/70 - (N-106)/210 +2 - S;

}

public int pi(int N, int m_max){

int S=0;

int dS=0;

int p=11;

boolean preTransition=true;

for (int c=4; p<m_max; c++){

x = N/p;

x += x&1;

if (preTransition){

if (p<(int)Math.sqrt(x)+1){

dS = p1.pi(x, p) - c;

}

else {

dS = p1.pi(x) - c;

preTransition=false;

}

}

else dS = p1.pi(x) - c;

S += dS;

p=primeList[c+1];

}

return N/2 -(N-4)/6 - (N-16)/10 + (N-16)/30 - (N-8)/14 + (N-22)/42

+ (N-106)/70 - (N-106)/210 +2 - S;

}

public long pi(long N){

if (N<2147483647) return pi((int)N);

long S=0;

long dS=0;

int p=11;

boolean preTransition=true;

int m_max = (int)Math.sqrt(N)+1;

for (int c=4; p<m_max; c++){

y = ((N+p-1)/(2*p))<<1;

if (preTransition){

if (p<(int)Math.sqrt(y)+1){

dS = p1.pi(y, p) - c;

}

else {

if (printFlag){

System.out.println("Time to transion was

"+(System.currentTimeMillis() - m_t));

System.out.println("Transition prime equals "+p);

}

dS = p1.pi(y) - c;

preTransition=false;

}

}

else dS = p1.pi(y) - c;

S += dS;

p=primeList[c+1];

}

return N/2 -(N-4)/6 - (N-16)/10 + (N-16)/30 - (N-8)/14 + (N-22)/42

+ (N-106)/70 - (N-106)/210 +2 - S;

}

public long pi(long N, int m_max){

if (N<2147483647) return pi((int)N, m_max);

long S=0;

long dS=0;

int p=11;

boolean preTransition=true;

for (int c=4; p<m_max; c++){

y = ((N+p-1)/(2*p))<<1;

if (preTransition){

if (p<(int)Math.sqrt(y)+1){

dS = p1.pi(y, p) - c;

}

else {

dS = p1.pi(y) - c;

preTransition=false;

}

}

else dS = p1.pi(y) - c;

S += dS;

p=primeList[c+1];

}

return N/2 -(N-4)/6 - (N-16)/10 + (N-16)/30 - (N-8)/14 + (N-22)/42

+ (N-106)/70 - (N-106)/210 +2 - S;

}

}

But how badly?

I'm going to include the program here, which I doubt could be done with the comparable program in Mathematica, or in any challenging program, so people who like to do these kinds of things can do a timing test.

Now upfront I expect my program to be beaten rather soundly, but I also expect it to do far better than you'd think some small Java program, based on my research, should do.

Ok, then I'm including the program in this post, so people can copy it out and run it!!!

Easy for you people who can do Java.

Though the wrapping is a problem, in a couple of places easily seen, so you will have to do just a little workd to get it to compile.

If it's too problematic for you I might start up a Yahoo! Group and stick it there, but it's really not that hard to just copy from here and get the program to compile.

James Harris

//Written by James S. Harris. Copyright 2002-2003. All rights reserved.

//My suggestion is to write your own version modifying this one.

//Commercial use is not permitted without my written permission.

//Proper attribution might get me some credit for having found the prime counting function

//So play with this and share, and *please* mention where you got it from.

import java.util.*;

public class PrimeCountH {

public static void main(String[] args) {

long N = Long.parseLong(args[0]);

long displayN = N;

//Internally the program only uses even N, so this handles

//if someone puts in an odd number

if (N!=1 && N%2!=0) N++;

PrimeCountH p = new PrimeCountH();

//I have two instances because that it made it easy for printing out

the prime

PrimeCountH.p1 = new PrimeCountH();

long t1 = System.currentTimeMillis();

m_t = t1;

int m_max = (int)Math.sqrt(N)+1;

//Note that I am building a bigger prime list than necessary

//It would all work with m_max, but a bigger prime list speeds things

up

if (N>120){

PrimeCountH.doSieve(8*m_max);

System.out.println("Sieve Time: "+(System.currentTimeMillis() -

t1));

}

//Put "true" in as your second argument to see more output

if (args.length>1 && args[1].equals("true")) p.printFlag=true;

System.out.println("m_max="+m_max);

System.out.println("pi("+displayN+")="+p.pi(N));

System.out.println("");

System.out.println("Total Time: "+(System.currentTimeMillis() - t1));

System.out.println("");

}

public static PrimeCountH p1;

public boolean printFlag;

public String primes="2, 3, 5, 7, ";

public static long t, dt, tot;

public static long y;

public static int x;

public static int[] primeList;

public static int primeCount;

public static int maxPrime;

public static long m_t;

public static void doSieve(int m_max){

//I separated this part so those of you who want to do your own sieve

//can easily put it in place.

//Just remember to put m_max at the end of your prime list array

//I don't claim that this is the fastest way to do it.

boolean[] temp = new boolean[m_max/2+1];

if (m_max>10000){

PrimeCountH sieveSize = new PrimeCountH();

doSieve((int)Math.sqrt(m_max)+1);

m_max+=m_max&1;

int size = sieveSize.pi(m_max);

primeList = new int[size+2];

int incr=1;

primeList[0]=2;

int i;

for (i=3; i<(int)Math.sqrt(m_max)+1; i+=2){

if (temp[(i-1)>>1]==false){

for (int j=i; j<m_max/i+1; j+=2){

temp[(i*j-1)>>1]=true;

}

primeList[incr]=i;

incr++;

}

}

for (; i<m_max; i+=2){

if (temp[(i-1)>>1]==false){

primeList[incr]=i;

incr++;

}

}

primeCount = incr;

primeList[incr]=m_max;

maxPrime = primeList[incr-1];

}

else {

for (int i=3; i<(int)Math.sqrt(m_max)+1; i+=2){

if (temp[(i-1)>>1]==false){

for (int j=i; j<m_max/i+1; j+=2){

temp[(i*j-1)>>1]=true;

}

}

}

int incr=2;

for (int i=2; i<m_max/2; i++){

if (temp[i]==false) incr++;

}

primeList = new int[incr+1];

incr=2;

primeList[0]=2;

primeList[1]=3;

for (int i=2; i<m_max/2; i++){

if (temp[i]==false){

primeList[incr]=(i<<1)+1;

incr++;

}

}

primeCount = incr;

primeList[incr]=m_max;

maxPrime = primeList[incr-1];

}

}

public int pi(int N){

if (N<121){

if (N<9) return N/2;

if (N<25) return N/2 - (N-4)/6;

if (N<49) return N/2 -(N-4)/6 - (N-16)/10 + (N-16)/30;

return N/2 -(N-4)/6 - (N-16)/10 + (N-16)/30 - (N-36)/14 + (N-22)/42;

}

//The code that follows is what makes a giant speed improvement

if (N<maxPrime){

int size= primeCount>>1;

if (N>>2 < size) size = (int)N>>2;

byte goForward;

int pos = size;

int prime;

while(size>0) {

prime = primeList[pos];

if (prime<N) goForward=1;

else if (prime>N) goForward=-1;

else break;

size=size>>1;

pos = pos + size*goForward;

}

if (pos<primeCount-1) {

prime = primeList[pos+1];

if (prime<N){

do{

pos++;

prime = primeList[pos+1];

} while (prime<N);

}

}

prime = primeList[pos];

if (prime>N){

do{

pos--;

prime = primeList[pos];

} while (prime>N);

}

// System.out.println("pi["+N+"]="+(pos+1));

// System.out.println("prime["+pos+"]="+primeList[pos]);

// System.out.println("");

return (pos+1);

}

int S=0;

int dS=0;

int p=11;

boolean preTransition=true;

int m_max = (int)Math.sqrt(N)+1;

for (int c=4; p<m_max; c++){

x = N/p;

x += x&1;

if (preTransition){

if (p<(int)Math.sqrt(x)+1){

dS = p1.pi(x, p) - c;

}

else {

if (printFlag){

System.out.println("Time to transion was

"+(System.currentTimeMillis() - m_t));

System.out.println("Transition prime equals "+p);

}

dS = p1.pi(x) - c;

preTransition=false;

}

}

else dS = p1.pi(x) - c;

S += dS;

if (false){//printFlag ){

System.out.println("prime="+p+", dS="+dS);

primes+=p +", ";

System.out.println("");

}

p=primeList[c+1];

}

if (false){//printFlag) {

System.out.println(primes);

System.out.println("");

System.out.println("S="+S);

System.out.println("");

}

return N/2 -(N-4)/6 - (N-16)/10 + (N-16)/30 - (N-8)/14 + (N-22)/42

+ (N-106)/70 - (N-106)/210 +2 - S;

}

public int pi(int N, int m_max){

int S=0;

int dS=0;

int p=11;

boolean preTransition=true;

for (int c=4; p<m_max; c++){

x = N/p;

x += x&1;

if (preTransition){

if (p<(int)Math.sqrt(x)+1){

dS = p1.pi(x, p) - c;

}

else {

dS = p1.pi(x) - c;

preTransition=false;

}

}

else dS = p1.pi(x) - c;

S += dS;

p=primeList[c+1];

}

return N/2 -(N-4)/6 - (N-16)/10 + (N-16)/30 - (N-8)/14 + (N-22)/42

+ (N-106)/70 - (N-106)/210 +2 - S;

}

public long pi(long N){

if (N<2147483647) return pi((int)N);

long S=0;

long dS=0;

int p=11;

boolean preTransition=true;

int m_max = (int)Math.sqrt(N)+1;

for (int c=4; p<m_max; c++){

y = ((N+p-1)/(2*p))<<1;

if (preTransition){

if (p<(int)Math.sqrt(y)+1){

dS = p1.pi(y, p) - c;

}

else {

if (printFlag){

System.out.println("Time to transion was

"+(System.currentTimeMillis() - m_t));

System.out.println("Transition prime equals "+p);

}

dS = p1.pi(y) - c;

preTransition=false;

}

}

else dS = p1.pi(y) - c;

S += dS;

p=primeList[c+1];

}

return N/2 -(N-4)/6 - (N-16)/10 + (N-16)/30 - (N-8)/14 + (N-22)/42

+ (N-106)/70 - (N-106)/210 +2 - S;

}

public long pi(long N, int m_max){

if (N<2147483647) return pi((int)N, m_max);

long S=0;

long dS=0;

int p=11;

boolean preTransition=true;

for (int c=4; p<m_max; c++){

y = ((N+p-1)/(2*p))<<1;

if (preTransition){

if (p<(int)Math.sqrt(y)+1){

dS = p1.pi(y, p) - c;

}

else {

dS = p1.pi(y) - c;

preTransition=false;

}

}

else dS = p1.pi(y) - c;

S += dS;

p=primeList[c+1];

}

return N/2 -(N-4)/6 - (N-16)/10 + (N-16)/30 - (N-8)/14 + (N-22)/42

+ (N-106)/70 - (N-106)/210 +2 - S;

}

}