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

}

}

### Wednesday, March 02, 2005

## JSH: Multiple tools

So now I'm talking about my prime counting function again, and I think that I like returning to it, as with it I can probe the depths of irrationality from the math community, and properly set things up so that people can be certain that mathematicians do lie to them.

It takes time.

But also I'm just scattered about it.

I basically see it as an onerous task pushed upon me by a strange situation that I continue to try and understand.

There are quite a few ways I can bring things to a close now, as I keep doing research.

I can stress prime counting and the popularity of primes and prime research as well as the supposed importance of them to mathematicians.

Or I can talk about finding a new way to factor. As time progresses, the weight of it grows greater, and there is always the worst case possibility that someone figures out how to get it to work well, and just forces the issue, but that is out of my hands.

Or I have other research I can discuss.

Who knows what I'll have tomorrow.

In response I mostly see, well, I don't see much at all except a passive-aggressive strategy of wait and see.

You wait and see, and you give an active mind more time to complete a stupendous task.

I needed that time. Now I need it less. When I need no more time, it will be over, just like that.

You sit back and hope, and I think of new ways to spread the information with the stated goal being out there for some time—undermining the current mathematical establishment because it is

corrupt.

Time is my weapon, not yours. With time I take away plausible deniability. I present a case that travels better than many of you may realize.

And I make my case in what is basically a public prosecution.

You are on trial, and have been on trial for some time.

In playing my role I want nothing more than maximum evidence, and part of my evidence is the behavior that's taking place now because I need maximum impact so that the world knows that something must be done as mathematics is too important of an area for corruption to be left alone.

The future of the world depends on my efforts.

I have the weight of the future on my shoulders, and it is Fated that I will not fail.

I will not fail.

My Fate is sealed. And so is yours.

Oh crap. I'm actually getting kind of bored with these type posts.

They use to be fun for a while, but the fun is gone.

Here's what I see.

Surrogate factoring ends it all.

That means that surrogate factoring is basically the big whammy that I think it is, and my having it now, at this time is probably it.

It takes away the need to talk, which just ruins the fun.

You people no longer have any control at this point, and I don't think it matters what you do any more.

You are trapped, just like I am with the inevitable.

Surrogate factoring will make things happen, whether I do anything else or not, or whether any of you do anything else or not.

It's out of our hands.

It takes time.

But also I'm just scattered about it.

I basically see it as an onerous task pushed upon me by a strange situation that I continue to try and understand.

There are quite a few ways I can bring things to a close now, as I keep doing research.

I can stress prime counting and the popularity of primes and prime research as well as the supposed importance of them to mathematicians.

Or I can talk about finding a new way to factor. As time progresses, the weight of it grows greater, and there is always the worst case possibility that someone figures out how to get it to work well, and just forces the issue, but that is out of my hands.

Or I have other research I can discuss.

Who knows what I'll have tomorrow.

In response I mostly see, well, I don't see much at all except a passive-aggressive strategy of wait and see.

You wait and see, and you give an active mind more time to complete a stupendous task.

I needed that time. Now I need it less. When I need no more time, it will be over, just like that.

You sit back and hope, and I think of new ways to spread the information with the stated goal being out there for some time—undermining the current mathematical establishment because it is

corrupt.

Time is my weapon, not yours. With time I take away plausible deniability. I present a case that travels better than many of you may realize.

And I make my case in what is basically a public prosecution.

You are on trial, and have been on trial for some time.

In playing my role I want nothing more than maximum evidence, and part of my evidence is the behavior that's taking place now because I need maximum impact so that the world knows that something must be done as mathematics is too important of an area for corruption to be left alone.

The future of the world depends on my efforts.

I have the weight of the future on my shoulders, and it is Fated that I will not fail.

I will not fail.

My Fate is sealed. And so is yours.

Oh crap. I'm actually getting kind of bored with these type posts.

They use to be fun for a while, but the fun is gone.

Here's what I see.

Surrogate factoring ends it all.

That means that surrogate factoring is basically the big whammy that I think it is, and my having it now, at this time is probably it.

It takes away the need to talk, which just ruins the fun.

You people no longer have any control at this point, and I don't think it matters what you do any more.

You are trapped, just like I am with the inevitable.

Surrogate factoring will make things happen, whether I do anything else or not, or whether any of you do anything else or not.

It's out of our hands.