Join PrimeGrid
Returning Participants
Community
Leader Boards
Results
Other
drummerslowrise

Message boards :
Number crunching :
Primes from 4000000000 to 10000000000 calculated in minutes !!!!!
Author 
Message 

Hi,
I have compiled this:
http://cr.yp.to/primegen.html
programm and calculate all primes in the range mentioned in the headline. In a few minutes on a P4@3400MHz !!! (2,7GB disk space output)
It should be no problem to create the primes upto
1000000000000000 with this programm (even on a single maschine !!!) !!
I have it compiled on a Linux maschine.
 


Rytis...any comment?
____________
 


Simply go to the URL mentioned above, download the source and compile it.
You can test it:
> ./primes <startvalue> <endvalue>
I suggest to test it with the ranges mentioned in the puplished results section and compare the out files for correctness.  

RytisVolunteer moderator Project administrator
Send message
Joined: 22 Jun 05 Posts: 2653 ID: 1 Credit: 109,635,410 RAC: 47,548

It might be faster, but does it give correct results? That's the question.
I will surely check it, but, as I've already noted in another thread, it's summer holidays, and I'll only have sporadic internet availability until September. Once I have a rainy day, I'll check this out :)
____________
 


I think it is correct, because the app is from a mathematician professor. See this:
http://en.wikipedia.org/wiki/Daniel_J._Bernstein
 


I've found this:
http://yaojialin.51.net/download/gxq/PrimeNumber.zip
Programmed by a Chinese, it can generate primes in a flash! Much faster than the application in Primegrid!
Here's the library it uses:
http://yaojialin.51.net/download/gxq/HugeCalc.rar  


In fact I do want a faster version. If you have a faster way, why not use it? I'm now thinking about how to hack the BOINC Client to cheat the program and advance my computation by just download the WU, stop the client, substitute the result and then report. That would be much much faster, only limited to my speed of operating.
But when I have no time to hack, I'll have to pause this project. That's it.  


In fact I do want a faster version. If you have a faster way, why not use it? I'm now thinking about how to hack the BOINC Client to cheat the program and advance my computation by just download the WU, stop the client, substitute the result and then report. That would be much much faster, only limited to my speed of operating.
But when I have no time to hack, I'll have to pause this project. That's it.
Well, why don't you write your science app., that takes primegrid tasks as input and outputs results in primegrid format, test it in standalone, compare results to official client (on many tasks  results), and then later (when it outputs valid results) use it to crunch primegrid using BOINC's anonymous platform system.
Greetings and good luck,
____________
 


In fact I do want a faster version. If you have a faster way, why not use it? I'm now thinking about how to hack the BOINC Client to cheat the program and advance my computation by just download the WU, stop the client, substitute the result and then report. That would be much much faster, only limited to my speed of operating.
But when I have no time to hack, I'll have to pause this project. That's it.
Well, why don't you write your science app., that takes primegrid tasks as input and outputs results in primegrid format, test it in standalone, compare results to official client (on many tasks  results), and then later (when it outputs valid results) use it to crunch primegrid using BOINC's anonymous platform system.
Greetings and good luck,
Well, it might be possible to program, but is there any open specification about structure of WU?  


I think this very well might be possible. From another post, Rytis said he was using the 'RabinMiller' test for primality which has a time complexity of O(k * log[n]^3), where k is 40 if the probability of a false result is 10^24.
The sieve of atkins, on the other hand, can find all primes between 0 and n with a bigo of O(n / (log(log(n)) )
What this means, is the sieve of atkins can find all the primes from 0 to 10,000,000,000 in
n / (log(log(n))
operations where n is 10,000,000,000 which is equal to 1.9786507773755612x10^9
On the other hand, for RabinMiller to simply test if a number around 10,000,000,000 is prime would take
40 * log[n]^3
operations where n is 10,000,000,000 which is
1.4663264693289653x10^6
That is to say, in double the time it takes for rabinmiller to test a single prime around 10x10^10, the sieve of atkins can generate all the primes from 0 to 10x10^10.
EDIT: Rytis's post is here:
http://www.primegrid.com/orig/forum_thread.php?id=376
And all the time complexity functions were taken from wikipedia:
http://en.wikipedia.org/wiki/Sieve_of_Atkin
http://en.wikipedia.org/wiki/RabinMiller_primality_test
Also, yes Rabin miller can be brought down to O(k * log[n]^2), but, either way, Sieve of Atkins is wildly more efficient for generating primes. I think the root of the problem here is that we're using the wrong kind of algorithm. Since we are generating primes, we should use an algorithm specifically geared for that (Sieve of Atkins) and not one that's geared for testing the primality of a single number (RabinMiller).  

Message boards :
Number crunching :
Primes from 4000000000 to 10000000000 calculated in minutes !!!!! 