Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > Java > fastest time?

Reply
Thread Tools

fastest time?

 
 
Neil Morris
Guest
Posts: n/a
 
      06-15-2008
Dear All
I rang the following code for finding prime numbers the results I got
for my computer is
105097565 prime numbers
2147483629 being the highest
13:31:14 taken 13 hours 31 minutes and 14 seconds

can anyone beat this on a computer, also how does this compare to a
mainframe/server farm setup

Thanks in advance
Neil Morris
ps I am using intek QX9650 4gb ram



import java.lang.*;

public class prime {

public static void main(String[] args) {
double start=(double)System.currentTimeMillis();
int input=Integer.MAX_VALUE;
int count=1;
for(int number=1;number<input;number++) {
boolean prime=true;
for(int i=2;(i*i>0)&&(i*i<=number);i++) {
if (number%i==0) {
prime=false;
break;
}
}
if(prime) {
double next=(double)System.currentTimeMillis();
double diff=(next-start)/1000;
double days=Math.floor(diff/86400);
diff=diff-(days*86400);
double hours=Math.floor(diff/3600);
diff=diff-(hours*3600);
double minutes=Math.floor(diff/60);
double seconds=diff-(minutes*60);
System.out.println(count+") "+number+"
:"+(long)days+":"+(long)hours+":"+(long)minutes+": "+(long)seconds+":");
count++;
}
}
}
}
 
Reply With Quote
 
 
 
 
Roedy Green
Guest
Posts: n/a
 
      06-15-2008
On Sun, 15 Jun 2008 16:55:00 +0100, Neil Morris
<(E-Mail Removed)> wrote, quoted or indirectly quoted someone
who said :

> public static void main(String[] args) {
> double start=(double)System.currentTimeMillis();
> int input=Integer.MAX_VALUE;
> int count=1;
> for(int number=1;number<input;number++) {
> boolean prime=true;
> for(int i=2;(i*i>0)&&(i*i<=number);i++) {
> if (number%i==0) {
> prime=false;
> break;
> }
> }


There are many faster algorithms than that. You don't need to divide
by anything unless it is prime.

You can use a seive.

See http://mindprod.com/jgloss/prime.html
--

Roedy Green Canadian Mind Products
The Java Glossary
http://mindprod.com
 
Reply With Quote
 
 
 
 
Daniel Pitts
Guest
Posts: n/a
 
      06-15-2008
Neil Morris wrote:
> Dear All
> I rang the following code for finding prime numbers the results I got
> for my computer is
> 105097565 prime numbers
> 2147483629 being the highest
> 13:31:14 taken 13 hours 31 minutes and 14 seconds
>
> can anyone beat this on a computer, also how does this compare to a
> mainframe/server farm setup
>
> Thanks in advance
> Neil Morris
> ps I am using intek QX9650 4gb ram
>

[snip op code]
On my machine: the following got the same results as you, in 5 minutes.
It is a bit more memory intensive, you'll have to run it with "java
-Xmx786M PrimeSeive" to avoid OutOfMemoryException.

import java.util.BitSet;

public class PrimeSeive {
public static void main(String[] args) {
final long startTime = System.currentTimeMillis();
long lastUpdate = startTime;
final BitSet composites = new BitSet(Integer.MAX_VALUE);
composites.set(0);
composites.set(1);
for (int j = 4; j >= 0 && j < Integer.MAX_VALUE; j += 2) {
composites.set(j);
}
int primes = 2;
int highestPrime = 2;
for (int prime = 1; prime < Integer.MAX_VALUE; ) {
prime = composites.nextClearBit(prime+2);
if (prime == Integer.MAX_VALUE) {
break;
}
primes++;
highestPrime = prime;
if (System.currentTimeMillis() - lastUpdate > 200) {
lastUpdate = System.currentTimeMillis();
printUpdate(startTime, primes, prime);
}
for (int j = prime * 2;
j >= 0 && j < Integer.MAX_VALUE;
j += prime) {
composites.set(j);
}
}
printUpdate(startTime, primes, highestPrime);
}

static void printUpdate(long startTime, int primes, int prime) {
long timeDifference = System.currentTimeMillis() - startTime;
long seconds = (timeDifference /= 1000) % 60;
long minutes = (timeDifference /= 60) % 60;
long hours = (timeDifference /= 60) % 24;
long days = (timeDifference /= 24) % 7;
System.out.println(primes + ": ("+prime+") "+
days+" day(s), "+
hours+" hour(s) "+
minutes+" minute(s) and "+
seconds+" second(s)");
}
}
--
Daniel Pitts' Tech Blog: <http://virtualinfinity.net/wordpress/>
 
Reply With Quote
 
Neil Morris
Guest
Posts: n/a
 
      06-15-2008
Daniel Pitts wrote:
> Neil Morris wrote:
>> Dear All
>> I rang the following code for finding prime numbers the results I got
>> for my computer is
>> 105097565 prime numbers
>> 2147483629 being the highest
>> 13:31:14 taken 13 hours 31 minutes and 14 seconds
>>
>> can anyone beat this on a computer, also how does this compare to a
>> mainframe/server farm setup
>>
>> Thanks in advance
>> Neil Morris
>> ps I am using intek QX9650 4gb ram
>>

> [snip op code]
> On my machine: the following got the same results as you, in 5 minutes.
> It is a bit more memory intensive, you'll have to run it with "java
> -Xmx786M PrimeSeive" to avoid OutOfMemoryException.
>
> import java.util.BitSet;
>
> public class PrimeSeive {
> public static void main(String[] args) {
> final long startTime = System.currentTimeMillis();
> long lastUpdate = startTime;
> final BitSet composites = new BitSet(Integer.MAX_VALUE);
> composites.set(0);
> composites.set(1);
> for (int j = 4; j >= 0 && j < Integer.MAX_VALUE; j += 2) {
> composites.set(j);
> }
> int primes = 2;
> int highestPrime = 2;
> for (int prime = 1; prime < Integer.MAX_VALUE; ) {
> prime = composites.nextClearBit(prime+2);
> if (prime == Integer.MAX_VALUE) {
> break;
> }
> primes++;
> highestPrime = prime;
> if (System.currentTimeMillis() - lastUpdate > 200) {
> lastUpdate = System.currentTimeMillis();
> printUpdate(startTime, primes, prime);
> }
> for (int j = prime * 2;
> j >= 0 && j < Integer.MAX_VALUE;
> j += prime) {
> composites.set(j);
> }
> }
> printUpdate(startTime, primes, highestPrime);
> }
>
> static void printUpdate(long startTime, int primes, int prime) {
> long timeDifference = System.currentTimeMillis() - startTime;
> long seconds = (timeDifference /= 1000) % 60;
> long minutes = (timeDifference /= 60) % 60;
> long hours = (timeDifference /= 60) % 24;
> long days = (timeDifference /= 24) % 7;
> System.out.println(primes + ": ("+prime+") "+
> days+" day(s), "+
> hours+" hour(s) "+
> minutes+" minute(s) and "+
> seconds+" second(s)");
> }
> }


Dear Daniel
Indeed your method is alot faster than my method, I guess the repeated
computions vs setting or unsetting bits in the BitSet data type goes to
show that if you have enough memory virtual or otherwise this is the
method to use!

ps the results from my machine is 2 minutes 55 seconds anyone can beat that?

Neil Morris

I used a edited version as follows it only shows the overall time


import java.util.BitSet;

public class PrimeSeive {
public static void main(String[] args) {
final long startTime = System.currentTimeMillis();
final BitSet composites = new BitSet(Integer.MAX_VALUE);
composites.set(0);
composites.set(1);
for (int j = 4; j >= 0 && j < Integer.MAX_VALUE; j += 2) {
composites.set(j);
}
int primes = 2;
int highestPrime = 2;
for (int prime = 1; prime < Integer.MAX_VALUE; ) {
prime = composites.nextClearBit(prime+2);
if (prime == Integer.MAX_VALUE) {
break;
}
primes++;
highestPrime = prime;
for (int j = prime * 2;
j >= 0 && j < Integer.MAX_VALUE;
j += prime) {
composites.set(j);
}
}
printUpdate(startTime, primes, highestPrime);
}

static void printUpdate(long startTime, int primes, int prime) {
long timeDifference = System.currentTimeMillis() - startTime;
long seconds = (timeDifference /= 1000) % 60;
long minutes = (timeDifference /= 60) % 60;
long hours = (timeDifference /= 60) % 24;
long days = (timeDifference /= 24) % 7;
System.out.println(primes + ": ("+prime+") "+
days+" day(s), "+
hours+" hour(s) "+
minutes+" minute(s) and "+
seconds+" second(s)");
}
}
 
Reply With Quote
 
Roger Lindsjö
Guest
Posts: n/a
 
      06-15-2008
Daniel Pitts wrote:
> Neil Morris wrote:
>> Dear All
>> I rang the following code for finding prime numbers the results I got
>> for my computer is
>> 105097565 prime numbers
>> 2147483629 being the highest
>> 13:31:14 taken 13 hours 31 minutes and 14 seconds
>>
>> can anyone beat this on a computer, also how does this compare to a
>> mainframe/server farm setup
>>
>> Thanks in advance
>> Neil Morris
>> ps I am using intek QX9650 4gb ram
>>

> [snip op code]
> On my machine: the following got the same results as you, in 5 minutes.
> It is a bit more memory intensive, you'll have to run it with "java
> -Xmx786M PrimeSeive" to avoid OutOfMemoryException.


On mine it takes just over 4 minutes. Then, if I just transform the
bitset to not include even numbers (thus halving the size), the time is
reduced to 2 min 40 seconds.

I'm sure there are even better algorithms, but I'm not sure what the
O.P. wanted to accomplish.

> import java.util.BitSet;
>
> public class PrimeSeive {
> public static void main(String[] args) {
> final long startTime = System.currentTimeMillis();
> long lastUpdate = startTime;
> final BitSet composites = new BitSet(Integer.MAX_VALUE);
> composites.set(0);
> composites.set(1);
> for (int j = 4; j >= 0 && j < Integer.MAX_VALUE; j += 2) {
> composites.set(j);
> }
> int primes = 2;

Why do you say you have 2 primes? I thought you only started with 1
prime (2).

> int highestPrime = 2;
> for (int prime = 1; prime < Integer.MAX_VALUE; ) {
> prime = composites.nextClearBit(prime+2);
> if (prime == Integer.MAX_VALUE) {
> break;
> }
> primes++;
> highestPrime = prime;
> if (System.currentTimeMillis() - lastUpdate > 200) {
> lastUpdate = System.currentTimeMillis();
> printUpdate(startTime, primes, prime);
> }
> for (int j = prime * 2;
> j >= 0 && j < Integer.MAX_VALUE;
> j += prime) {

start with prime * 3 and then step with prime * 2 since the other values
will be even which has already been set by your original "clear even" loop.

> composites.set(j);
> }
> }
> printUpdate(startTime, primes, highestPrime);
> }
>
> static void printUpdate(long startTime, int primes, int prime) {
> long timeDifference = System.currentTimeMillis() - startTime;
> long seconds = (timeDifference /= 1000) % 60;
> long minutes = (timeDifference /= 60) % 60;
> long hours = (timeDifference /= 60) % 24;
> long days = (timeDifference /= 24) % 7;
> System.out.println(primes + ": ("+prime+") "+
> days+" day(s), "+
> hours+" hour(s) "+
> minutes+" minute(s) and "+
> seconds+" second(s)");
> }
> }



--
Roger Lindsjö
 
Reply With Quote
 
Arne Vajhøj
Guest
Posts: n/a
 
      06-17-2008
Daniel Pitts wrote:
> public class PrimeSeive {


Maybe rename it to PrimeSieve ...



Arne
 
Reply With Quote
 
Arne Vajhøj
Guest
Posts: n/a
 
      06-22-2008
Neil Morris wrote:
> I rang the following code for finding prime numbers the results I got
> for my computer is
> 105097565 prime numbers
> 2147483629 being the highest
> 13:31:14 taken 13 hours 31 minutes and 14 seconds


This reminds me of the mid 1980's and playing with Macro-32.



See code below for one way of doing it.

Arne

================================================== ==

// run with -Xmx300m
public class Primes {
private final static int[] MASK = { 1, 2, 4, 8, 16, 32, 64, 128 };
private static boolean isBitSet(byte[] b, int ix) {
int bytix = ix >> 4;
int bitix = (ix & 0x0F) >> 1;
return (b[bytix] & MASK[bitix]) > 0;
}
private static void setBit(byte[] b, int ix) {
int bytix = ix >> 4;
int bitix = (ix & 0x0F) >> 1;
b[bytix] |= MASK[bitix];
}
private static void findPrimes(int n) {
long t1 = System.currentTimeMillis();
byte[] b = new byte[n / 16 + 1];
int sqrtn = (int)Math.sqrt(n);
for(int i = 3; i <= sqrtn; i += 2) {
if(!isBitSet(b, i)) {
for(int j = 3 * i; j <= n && j > 0; j += (2 * i)) {
setBit(b, j);
}
}
}
int nprim = 1;
for(int k = 3; k <= n && k > 0; k += 2) {
if(!isBitSet(b, k)) {
nprim++;
}
}
long t2 = System.currentTimeMillis();
System.out.println(nprim + " primes in " + n + " numbers -
found in " + (t2 - t1) / 1000.0 + " seconds");
}
public static void main(String[] args) {
findPrimes(100000);
// for reasons unknown to me it does not work with
Integer.MAX_VALUE if -server is used
findPrimes(Integer.MAX_VALUE - 1);
}
}
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
perl efficiency -- fastest grepping? Bryan Krone Perl 1 11-08-2004 11:15 PM
Fastest 5 mp Digital Camera ? Fastest 4 mp Digital Camera? photoguysept102004@yahoo.com Digital Photography 6 10-28-2004 11:33 AM
Re: fastest way to access global vars =?Utf-8?B?cmdoYXRvbA==?= ASP .Net 1 03-05-2004 06:13 PM
fastest way to access global vars? rghatol@unionbankph.com ASP .Net 1 03-02-2004 04:54 PM
diff between pc-msvc pc-cygwin and svg-GDI - which is fastest vc Firefox 10 02-28-2004 01:05 AM



Advertisments