mfaktc: a CUDA program for Mersenne prefactoring - Page 260

MrRepunit · 2018-09-13, 18:52

Quote:

Originally Posted by Citrix

For generalized repunits b^p-1 (also for b^p+1 i.e. for negative b) with p prime, they have factors of the form 2*k*p+1 irrespective of b.

The only question is what form these factors can take mod 8? I do not have a general rule for this.

I am working on a special set of odd bases (for b^p+1 and b^p-1) where the factors are always 1 and 5 (mod 8).

Are there any other modular restrictions that I am not aware of?

If you could modify your program to help me.. I would appreciate it. I would prefer the compiled .exe instead of the source code. I am afraid I might not be compile the code.

Thanks.

I try to give you my derivation for base 10 repunits:
Similar to Mersenne factors we find for repunits that

$\text{Legendre}(10,p) \equiv 1$ (10 is a quadratic residue mod p)
$\text{Legendre}(10,p) = \text{Legendre}(2,p)\times\text{Legendre}(5,p)$

$ \text{Legendre}(2,p) = (-1)^{\frac{p^2-1}{8}} = \begin{cases} +1 & \text{if p\equiv1 or 7 mod 8} \\ -1 & \text{if p\equiv 3 or 5 mod 8} \end{cases} $

$ \text{Legendre}(5,p) = (-1)^{\text{Floor}(\frac{p+2}{5})} = \begin{cases} +1 & \text{if p\equiv1 or 4 mod 5} \\ -1 & \text{if p\equiv 2 or 3 mod 5} \end{cases} $

Product must be +1, so either both products of (-1)(-1) and (+1)(+1) are possible.
Filtering the possible values mod 40 gives the following allowed values:
{1,3,9,13,27,31,37,39} or {±1, ±3, ±9, ±13} for 2kp+1.
Thus allowed values for 2kp are: {0,2,8,12,26,30,36,38}
See also: https://math.stackexchange.com/quest...rac10p-right-1

So if you try to adapt it to your numbers I could compile a new version.

MrRepunit · 2018-09-13, 19:05

Quote:

Originally Posted by kriesel

The source is there. See the screen grab below.

I know, I have it from there. And I also follow the mfaktc thread for some years. I also suffered from the Cuda 8 bug myself. It was actually me that told TheJudger that the bug in Cuda 8 was fixed after I found that my repunit adaption was working again after a cuda sdk update.

What I really mean is that I would like to have a source code versioning system for mfaktc (git, svn, mercurial, ...) where one could see the progress. This allows to create different branches without affecting the original. Optimal would be hosting the source on github or gitlab. I know that there is a mfaktc repository on github, but it is not managed by TheJudger, thus I was asking.

Citrix · 2018-09-13, 19:39

Quote:

Originally Posted by MrRepunit

I try to give you my derivation for base 10 repunits:
Similar to Mersenne factors we find for repunits that

$\text{Legendre}(10,p) \equiv 1$ (10 is a quadratic residue mod p)
$\text{Legendre}(10,p) = \text{Legendre}(2,p)\times\text{Legendre}(5,p)$

$ \text{Legendre}(2,p) = (-1)^{\frac{p^2-1}{8}} = \begin{cases} +1 & \text{if p\equiv1 or 7 mod 8} \\ -1 & \text{if p\equiv 3 or 5 mod 8} \end{cases} $

$ \text{Legendre}(5,p) = (-1)^{\text{Floor}(\frac{p+2}{5})} = \begin{cases} +1 & \text{if p\equiv1 or 4 mod 5} \\ -1 & \text{if p\equiv 2 or 3 mod 5} \end{cases} $

Product must be +1, so either both products of (-1)(-1) and (+1)(+1) are possible.
Filtering the possible values mod 40 gives the following allowed values:
{1,3,9,13,27,31,37,39} or {±1, ±3, ±9, ±13} for 2kp+1.
Thus allowed values for 2kp are: {0,2,8,12,26,30,36,38}
See also: https://math.stackexchange.com/quest...rac10p-right-1

So if you try to adapt it to your numbers I could compile a new version.

I am working on numbers such that b^p+-1 where p is an odd prime and b=n*p and n is a natural number.

From your example the Legendre (b,p)= Legendre (n*p,p)=Legendre (0,p)=0

How do we proceed from here?

Thanks.

GP2 · 2018-09-14, 19:17

Quote:

Originally Posted by MrRepunit

I would say possibly yes, but not easily. When I converted mfaktc to base 10 repunits I had to calculate the possible modular classes for base 10 and adapt the corresponding parts in the source code.

Also the current mfaktc version is not well suited to handle numbers in the range of general repunits, so one has to create kernels that are faster. I did this already by implementing a kernel for numbers < 64 bits.

I can put the source code here if there is some interest.

Sure, I'd be interested.

Modifying the class_needed function seems simple enough if you just want to hardcode it for some particular base, for instance 3. And the selftest stuff can be temporarily commented out. What other changes did you need to make to the rest of the source code? For instance the part where it checks against b^p − 1 rather than 2^p − 1.

Are the faster kernels also applicable to Mersenne testing? Can they simply be contributed to the existing source code?

MrRepunit · 2018-09-14, 19:26

Quote:

Originally Posted by Citrix

I am working on numbers such that b^p+-1 where p is an odd prime and b=n*p and n is a natural number.

From your example the Legendre (b,p)= Legendre (n*p,p)=Legendre (0,p)=0

How do we proceed from here?

Thanks.

Not sure. I am not really fluent in this kind of math (I am a theoretical physicist). My first thought was that we can use Legendre (n*p,p)=Legendre (0,p)*Legendre(n,p). Legendre (0,p) is trivially 0, so that Legendre(n,p) can be anything.

But I think that we cannot use this here since we need the Legendre symbol to be equal to 1 to make some useful statements (correct me if I am wrong).

Citrix · 2018-09-14, 19:49

Quote:

Originally Posted by MrRepunit

Not sure. I am not really fluent in this kind of math (I am a theoretical physicist). My first thought was that we can use Legendre (n*p,p)=Legendre (0,p)*Legendre(n,p). Legendre (0,p) is trivially 0, so that Legendre(n,p) can be anything.

But I think that we cannot use this here since we need the Legendre symbol to be equal to 1 to make some useful statements (correct me if I am wrong).

I am more interested in the case where n=1. Looking at the factors of these numbers they are 1 and 7 (mod 8). I do not know how to prove this.

If you could compile a version that just restricts the factors to 2*k*p+1, that would be great.

MrRepunit · 2018-09-14, 19:59

Quote:

Originally Posted by GP2

Sure, I'd be interested.

Modifying the class_needed function seems simple enough if you just want to hardcode it for some particular base, for instance 3. And the selftest stuff can be temporarily commented out. What other changes did you need to make to the rest of the source code? For instance the part where it checks against b^p − 1 rather than 2^p − 1.

Are the faster kernels also applicable to Mersenne testing? Can they simply be contributed to the existing source code?

I modified class_needed, 10 has to be exponentiated instead of 2, I added a 64 bit shortcut. I guess most of the 64 bit stuff can be used for mersenne numbers, but might need some changes or are missing some minor stuff. I think I removed some bit shift methods since they were not used for base 10.
Also a snippet from the readme:
- Removed Barrett and 72 bit kernels
- Removed Wagstaff related stuff
- Added 64 bit kernels
- Implemented repunit factorization (hardcoded)
- Improved performance compared to older version (0.18-repunit) about 30%
- Notes
- Compiling with more-classes flag seem to be slightly faster, thus it is switched on
- Not tested on Windows yet
- GPU sieving utilizes 100% of the GPU, so 1 mfaktc instance is enough
- GPU sieving makes the system response slow (tested on Ubuntu 14.04 64 bit with Geforce 460 GTS)
Setting GPUSieveSize in mfaktc.ini to 8 or lower makes the system more responsive

I did not remove the git directory, so if anybody is interested in the single commits feel free to take a closer look. I also added the linux executable. Not sure if I can quickly provide a windows variant...

MrRepunit · 2018-09-14, 20:07

Quote:

Originally Posted by Citrix

I am more interested in the case where n=1. Looking at the factors of these numbers they are 1 and 7 (mod 8). I do not know how to prove this.

If you could compile a version that just restricts the factors to 2*k*p+1, that would be great.

I try to do it this weekend, but I can only provide a linux executable quickly if I succeed. Windows will take a bit longer...

Citrix · 2018-09-14, 20:14

Quote:

Originally Posted by MrRepunit

I try to do it this weekend, but I can only provide a linux executable quickly if I succeed. Windows will take a bit longer...

Thanks. I would need windows, I do not have linux.

I will wait, I am not in a hurry.

storm5510 · 2018-09-17, 14:02

Quote:

Originally Posted by MrRepunit

I modified class_needed, 10 has to be exponentiated instead of 2, I added a 64 bit shortcut. I guess most of the 64 bit stuff can be used for mersenne numbers, but might need some changes or are missing some minor stuff. I think I removed some bit shift methods since they were not used for base 10.
Also a snippet from the readme:
- Removed Barrett and 72 bit kernels
- Removed Wagstaff related stuff
- Added 64 bit kernels
- Implemented repunit factorization (hardcoded)
- Improved performance compared to older version (0.18-repunit) about 30%
- Notes
- Compiling with more-classes flag seem to be slightly faster, thus it is switched on
- Not tested on Windows yet
- GPU sieving utilizes 100% of the GPU, so 1 mfaktc instance is enough
- GPU sieving makes the system response slow (tested on Ubuntu 14.04 64 bit with Geforce 460 GTS)
Setting GPUSieveSize in mfaktc.ini to 8 or lower makes the system more responsive

I did not remove the git directory, so if anybody is interested in the single commits feel free to take a closer look. I also added the linux executable. Not sure if I can quickly provide a windows variant...

It pleases me to see that this is getting some lattention.

At some point, the ceiling value for exponents will need to be increased. If memory serves, the current value is 2³²-1. A 'wishful thinking' value might be 2³⁴-1

Either way, a Windows 64-bit compile would be nice The current version does not work my GTX 1080 all that hard. Core temps stay in the mid 60's with factory default settings.

kriesel · 2018-09-17, 22:56

Quote:

Originally Posted by storm5510

It pleases me to see that this is getting some lattention.

At some point, the ceiling value for exponents will need to be increased. If memory serves, the current value is 2³²-1. A 'wishful thinking' value might be 2³⁴-1

Either way, a Windows 64-bit compile would be nice The current version does not work my GTX 1080 all that hard. Core temps stay in the mid 60's with factory default settings.

Re exponent limit, I estimate we and our successors have about a century yet before running out of Mersenne hunting work in p<2³²-5 (the largest prime exponent below 2³²). There was a discussion a while back about the additional amount of programming required to support exponents above the current level, and it was definitely nontrivial. see starting post 1439 of the mfakto thread https://mersenneforum.org/showthread...15646&page=131 and particularly post 1447. Note also there's no work or results coordination site for Mersenne hunting at exponents above 2³².

Re your GTX1080, how do you know you don't simply have very good cooling? What does TechPowerUp GPU-Z or CPUID HWMonitor say about gpu % load and reasons for it being less than 95-100%? Are you running high enough bit depths, and/or the less-classes version, or running on a solid state disk, so that I/O is not limiting throughput?

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
mfakto: an OpenCL program for Mersenne prefactoring	Bdot	GPU Computing	1719	2023-01-16 15:51
gr-mfaktc: a CUDA program for generalized repunits prefactoring	MrRepunit	GPU Computing	42	2022-12-18 05:59
The P-1 factoring CUDA program	firejuggler	GPU Computing	753	2020-12-12 18:07
mfaktc 0.21 - CUDA runtime wrong	keisentraut	Software	2	2020-08-18 07:03
World's second-dumbest CUDA program	fivemack	Programming	112	2015-02-12 22:51