Report top-5000 primes here - Page 28

rogue · 2013-07-01, 22:52

Quote:

Originally Posted by henryzz

This has been discussed in the past.
http://www.mersenneforum.org/showthr...ht=bsgs&page=3
Is the memory usage dependent on p or the range of p?
Also you talk about needing 256 sets of 80MB data as there are 256 cores. Is there a way to utilize multiple cores on the same set of data?
Another option is to make it use only a few cores(as many as possible) and expect the user to also run a thread of mfaktc to saturate the gpu.

Memory usage is dependent upon p.

As for multiple cores for each p, I haven't investigated. If that can be done, it might be the way to go.

Citrix · 2013-07-02, 07:52

Quote:

Originally Posted by rogue

Memory usage is dependent upon p.

As for multiple cores for each p, I haven't investigated. If that can be done, it might be the way to go.

It will be about 256 times slower....

henryzz · 2013-07-02, 10:08

Quote:

Originally Posted by Citrix

It will be about 256 times slower....

I didn't expect full speed with multiple cores. I was hoping for better than a linear decrease in speed.

Citrix · 2013-07-02, 17:29

The easiest way of doing this would be:

Suppose you were sieving from k*2^x+1 to k*2^y+1
Then divide the range into 256 pieces

x, x1,x2,xi....y

Then send each range for a fixed p to the GPU core.

Each core will require 1/16 th of the memory needed for the BSGS algorithm.
(Which is generally low for the low weight k's like CRUS; I am not sure how much memory each core has)

Multmods needed will be 2* sqrt (n/256) *256
Since there are 256 cores, multmods will be 2* sqrt (n/256) per core

Overall you will see it is 16 times faster compared to BSGS but requires 16 times more memory.

There are other algorithms that can be implemented with little memory use but at the cost of not finding all but most of the factors.

The only definite way (non-probabilistic) without requiring alot of memory would be brute force (test every n) or index calculus (which will be very cumbersome and hard to implement).

For some of the extremely low weight k's left or small range of n's... brute force can be implemented helping the project out. BSGS might also be implementable for an extremely small n range.

gd_barnes · 2013-07-03, 10:03

Outstanding prime Borys and well deserved! I was hoping base 10 would finally yield one before n=1M.

unconnected · 2013-07-30, 19:42

74*500^218184-1 (588874 digits)

MyDogBuster · 2013-07-31, 02:12

Quote:

74*500^218184-1 (588874 digits)

Nice one. Makes R500 a 3ker.

Batalov · 2013-08-20, 16:16

S683 is proven with 18·683^141239+1.
Residues are in the email. Base released.

gd_barnes · 2013-08-20, 17:47

Nice one Serge! Any prime that knocks down all of the n=1.29M primes a notch is a good one.

Lennart · 2013-08-20, 23:43

59506*6^780877+1 is Prime

Lennart

gd_barnes · 2013-08-21, 04:54

Congrats Lennart!

We were definitely overdue on S6.

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Report top-5000 primes for all k<=1001	gd_barnes	No Prime Left Behind	1502	2021-06-22 05:30
Report top-5000 primes for k=1003-3000	gd_barnes	No Prime Left Behind	688	2020-04-24 07:31
All top 5000 primes will have the same number of digits in 2014 ;-)	Batalov	Conjectures 'R Us	10	2013-03-29 01:29
Twenty Oldest Primes on Top 5000 List	masser	Lounge	9	2008-08-27 12:31
get all the 5000 biggest primes above 100K digits	jasong	jasong	1	2007-06-09 22:51

2013-07-02, 17:29	#301
Citrix Jun 2003 2·7·113 Posts	The easiest way of doing this would be: Suppose you were sieving from k2^x+1 to k2^y+1 Then divide the range into 256 pieces x, x1,x2,xi....y Then send each range for a fixed p to the GPU core. Each core will require 1/16 th of the memory needed for the BSGS algorithm. (Which is generally low for the low weight k's like CRUS; I am not sure how much memory each core has) Multmods needed will be 2* sqrt (n/256) 256 Since there are 256 cores, multmods will be 2 sqrt (n/256) per core Overall you will see it is 16 times faster compared to BSGS but requires 16 times more memory. There are other algorithms that can be implemented with little memory use but at the cost of not finding all but most of the factors. The only definite way (non-probabilistic) without requiring alot of memory would be brute force (test every n) or index calculus (which will be very cumbersome and hard to implement). For some of the extremely low weight k's left or small range of n's... brute force can be implemented helping the project out. BSGS might also be implementable for an extremely small n range.

2013-07-03, 10:03	#302
gd_barnes May 2007 Kansas; USA 10403₁₀ Posts	Outstanding prime Borys and well deserved! I was hoping base 10 would finally yield one before n=1M.

2013-07-30, 19:42	#303
unconnected May 2009 Russia, Moscow 2,593 Posts	74*500^218184-1 (588874 digits)

2013-08-20, 16:16	#305
Batalov "Serge" Mar 2008 Phi(4,2^7658614+1)/2 2⁴×593 Posts	S683 is proven with 18·683^141239+1. Residues are in the email. Base released.

2013-08-20, 17:47	#306
gd_barnes May 2007 Kansas; USA 101·103 Posts	Nice one Serge! Any prime that knocks down all of the n=1.29M primes a notch is a good one.

2013-08-20, 23:43	#307
Lennart "Lennart" Jun 2007 1120₁₀ Posts	59506*6^780877+1 is Prime Lennart

2013-08-21, 04:54	#308
gd_barnes May 2007 Kansas; USA 28A3₁₆ Posts	Congrats Lennart! We were definitely overdue on S6.