PrimeGrid
Please visit donation page to help the project cover running costs for this month

Toggle Menu

Join PrimeGrid

Returning Participants

Community

Leader Boards

Results

Other

drummers-lowrise

Advanced search

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

Author Message
Bjoern
Send message
Joined: 18 Jun 06
Posts: 7
ID: 3044
Credit: 682
RAC: 0

Message 3564 - Posted: 20 Jun 2006 | 16:47:21 UTC

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.



MurrayProject donor
Send message
Joined: 15 Jan 06
Posts: 18
ID: 2175
Credit: 25,011
RAC: 0

Message 3573 - Posted: 22 Jun 2006 | 21:53:09 UTC

Rytis...any comment?
____________

Bjoern
Send message
Joined: 18 Jun 06
Posts: 7
ID: 3044
Credit: 682
RAC: 0

Message 3578 - Posted: 23 Jun 2006 | 6:08:07 UTC

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.

Rytis
Volunteer moderator
Project administrator
Avatar
Send message
Joined: 22 Jun 05
Posts: 2639
ID: 1
Credit: 21,321,147
RAC: 88
321 LLR Silver: Earned 100,000 credits (104,475)Cullen LLR Silver: Earned 100,000 credits (291,372)ESP LLR Bronze: Earned 10,000 credits (18,156)Generalized Cullen/Woodall LLR Bronze: Earned 10,000 credits (15,259)PPS LLR Silver: Earned 100,000 credits (113,978)PSP LLR Silver: Earned 100,000 credits (116,517)SoB LLR Silver: Earned 100,000 credits (151,232)SR5 LLR Bronze: Earned 10,000 credits (14,071)SGS LLR Silver: Earned 100,000 credits (100,082)TPS LLR (retired) Silver: Earned 100,000 credits (111,607)TRP LLR Jade: Earned 10,000,000 credits (16,017,500)Woodall LLR Silver: Earned 100,000 credits (101,463)321 Sieve Silver: Earned 100,000 credits (201,501)Cullen/Woodall Sieve (suspended) Silver: Earned 100,000 credits (214,653)Generalized Cullen/Woodall Sieve (suspended) Bronze: Earned 10,000 credits (14,200)PPS Sieve Silver: Earned 100,000 credits (302,417)Sierpinski (ESP/PSP/SoB) Sieve (suspended) Silver: Earned 100,000 credits (200,232)TRP Sieve (suspended) Ruby: Earned 2,000,000 credits (2,453,872)AP 26/27 Silver: Earned 100,000 credits (473,058)GFN Silver: Earned 100,000 credits (163,887)PSA Bronze: Earned 10,000 credits (97,541)
Message 3590 - Posted: 26 Jun 2006 | 15:00:50 UTC

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 :)
____________

Bjoern
Send message
Joined: 18 Jun 06
Posts: 7
ID: 3044
Credit: 682
RAC: 0

Message 3606 - Posted: 27 Jun 2006 | 15:42:23 UTC

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

Profile fwjmath
Send message
Joined: 5 May 06
Posts: 2
ID: 2813
Credit: 12,861,973
RAC: 39
321 LLR Gold: Earned 500,000 credits (587,350)Cullen LLR Bronze: Earned 10,000 credits (11,918)PPS LLR Gold: Earned 500,000 credits (502,684)PSP LLR Bronze: Earned 10,000 credits (50,294)SoB LLR Silver: Earned 100,000 credits (351,049)SR5 LLR Silver: Earned 100,000 credits (211,082)SGS LLR Silver: Earned 100,000 credits (310,277)TRP LLR Bronze: Earned 10,000 credits (16,850)Woodall LLR Bronze: Earned 10,000 credits (16,318)321 Sieve Bronze: Earned 10,000 credits (32,921)Cullen/Woodall Sieve (suspended) Bronze: Earned 10,000 credits (20,062)PPS Sieve Turquoise: Earned 5,000,000 credits (6,478,575)Sierpinski (ESP/PSP/SoB) Sieve (suspended) Bronze: Earned 10,000 credits (20,120)TRP Sieve (suspended) Bronze: Earned 10,000 credits (33,576)AP 26/27 Ruby: Earned 2,000,000 credits (2,950,978)GFN Amethyst: Earned 1,000,000 credits (1,222,380)PSA Bronze: Earned 10,000 credits (43,810)
Message 3749 - Posted: 17 Jul 2006 | 23:37:21 UTC

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

Profile fwjmath
Send message
Joined: 5 May 06
Posts: 2
ID: 2813
Credit: 12,861,973
RAC: 39
321 LLR Gold: Earned 500,000 credits (587,350)Cullen LLR Bronze: Earned 10,000 credits (11,918)PPS LLR Gold: Earned 500,000 credits (502,684)PSP LLR Bronze: Earned 10,000 credits (50,294)SoB LLR Silver: Earned 100,000 credits (351,049)SR5 LLR Silver: Earned 100,000 credits (211,082)SGS LLR Silver: Earned 100,000 credits (310,277)TRP LLR Bronze: Earned 10,000 credits (16,850)Woodall LLR Bronze: Earned 10,000 credits (16,318)321 Sieve Bronze: Earned 10,000 credits (32,921)Cullen/Woodall Sieve (suspended) Bronze: Earned 10,000 credits (20,062)PPS Sieve Turquoise: Earned 5,000,000 credits (6,478,575)Sierpinski (ESP/PSP/SoB) Sieve (suspended) Bronze: Earned 10,000 credits (20,120)TRP Sieve (suspended) Bronze: Earned 10,000 credits (33,576)AP 26/27 Ruby: Earned 2,000,000 credits (2,950,978)GFN Amethyst: Earned 1,000,000 credits (1,222,380)PSA Bronze: Earned 10,000 credits (43,810)
Message 4183 - Posted: 25 Nov 2006 | 9:31:53 UTC - in response to Message 3590.

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.

Vid Vidmar*
Avatar
Send message
Joined: 16 Aug 05
Posts: 45
ID: 377
Credit: 70,953,229
RAC: 0
321 LLR Amethyst: Earned 1,000,000 credits (1,144,068)Cullen LLR Gold: Earned 500,000 credits (631,529)ESP LLR Bronze: Earned 10,000 credits (38,854)Generalized Cullen/Woodall LLR Silver: Earned 100,000 credits (186,632)PPS LLR Silver: Earned 100,000 credits (497,365)PSP LLR Amethyst: Earned 1,000,000 credits (1,484,342)SoB LLR Amethyst: Earned 1,000,000 credits (1,169,328)SR5 LLR Bronze: Earned 10,000 credits (23,176)SGS LLR Silver: Earned 100,000 credits (120,236)TRP LLR Silver: Earned 100,000 credits (325,761)Woodall LLR Amethyst: Earned 1,000,000 credits (1,941,922)321 Sieve Ruby: Earned 2,000,000 credits (2,144,147)Cullen/Woodall Sieve (suspended) Amethyst: Earned 1,000,000 credits (1,942,972)Generalized Cullen/Woodall Sieve (suspended) Bronze: Earned 10,000 credits (29,485)PPS Sieve Emerald: Earned 50,000,000 credits (56,735,073)Sierpinski (ESP/PSP/SoB) Sieve (suspended) Silver: Earned 100,000 credits (223,823)TRP Sieve (suspended) Amethyst: Earned 1,000,000 credits (1,580,537)AP 26/27 Gold: Earned 500,000 credits (682,470)
Message 4184 - Posted: 25 Nov 2006 | 11:45:09 UTC - in response to Message 4183.

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

JustasProject donor
Send message
Joined: 2 Jan 07
Posts: 16
ID: 4525
Credit: 574,534
RAC: 0
Cullen LLR Bronze: Earned 10,000 credits (12,986)SGS LLR Bronze: Earned 10,000 credits (10,415)TPS LLR (retired) Bronze: Earned 10,000 credits (23,534)Woodall LLR Bronze: Earned 10,000 credits (12,493)321 Sieve Bronze: Earned 10,000 credits (99,911)Cullen/Woodall Sieve (suspended) Silver: Earned 100,000 credits (242,933)PPS Sieve Silver: Earned 100,000 credits (122,728)Sierpinski (ESP/PSP/SoB) Sieve (suspended) Bronze: Earned 10,000 credits (37,209)
Message 4387 - Posted: 5 Jan 2007 | 11:02:30 UTC - in response to Message 4184.

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?

Alex Beal
Send message
Joined: 16 Mar 07
Posts: 1
ID: 6501
Credit: 62
RAC: 0

Message 5175 - Posted: 18 Mar 2007 | 19:08:33 UTC - in response to Message 4387.
Last modified: 18 Mar 2007 | 19:16:00 UTC

I think this very well might be possible. From another post, Rytis said he was using the 'Rabin-Miller' 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 big-o 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 Rabin-Miller 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 rabin-miller 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/Rabin-Miller_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 (Rabin-Miller).

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

[Return to PrimeGrid main page]
DNS Powered by DNSEXIT.COM
Copyright © 2005 - 2019 Rytis Slatkevičius (contact) and PrimeGrid community. Server load 1.27, 1.68, 1.79
Generated 11 Dec 2019 | 8:44:00 UTC