[QUOTE=henryzz;345028]This has been discussed in the past.
[URL]http://www.mersenneforum.org/showthread.php?t=16250&highlight=bsgs&page=3[/URL]
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.[/QUOTE]

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.

[QUOTE=rogue;345031]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.[/QUOTE]

It will be about 256 times slower....

[QUOTE=Citrix;345057]It will be about 256 times slower....[/QUOTE]
I didn't expect full speed with multiple cores. I was hoping for better than a linear decrease in speed.

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.

:smile:

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

[URL="http://primes.utm.edu/primes/page.php?id=114845"]74*500^218184-1[/URL] (588874 digits)

[QUOTE][URL="http://primes.utm.edu/primes/page.php?id=114845"]74*500^218184-1[/URL] (588874 digits) [/QUOTE]

Nice one. Makes R500 a 3ker.:bow:

S683 is proven with [URL="http://primes.utm.edu/primes/page.php?id=115157"]18·683^141239+1[/URL].
Residues are in the email. Base released.

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

59506*6^780877+1 is Prime


Lennart

Congrats Lennart! :smile: We were definitely overdue on S6.