mersenneforum.org mfaktc: a CUDA program for Mersenne prefactoring
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

2018-09-13, 18:52   #2850
MrRepunit

Mar 2011
Germany

10101112 Posts

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}

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

2018-09-13, 19:05   #2851
MrRepunit

Mar 2011
Germany

3·29 Posts

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.

2018-09-13, 19:39   #2852
Citrix

Jun 2003

5·307 Posts

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.

2018-09-14, 19:17   #2853
GP2

Sep 2003

A1216 Posts

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?

2018-09-14, 19:26   #2854
MrRepunit

Mar 2011
Germany

1278 Posts

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).

2018-09-14, 19:49   #2855
Citrix

Jun 2003

5·307 Posts

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.

2018-09-14, 19:59   #2856
MrRepunit

Mar 2011
Germany

3×29 Posts

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...
Attached Files
 mfaktc-0.21-repunit.zip (1.25 MB, 56 views)

2018-09-14, 20:07   #2857
MrRepunit

Mar 2011
Germany

10101112 Posts

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...

2018-09-14, 20:14   #2858
Citrix

Jun 2003

5×307 Posts

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.

2018-09-17, 14:02   #2859
storm5510
Random Account

Aug 2009
U.S.A.

22×3×101 Posts

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 232-1. A 'wishful thinking' value might be 234-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.

2018-09-17, 22:56   #2860
kriesel

"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest

11×347 Posts

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 232-1. A 'wishful thinking' value might be 234-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<232-5 (the largest prime exponent below 232). 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 232.

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 Bdot GPU Computing 1615 2020-05-16 23:55 firejuggler GPU Computing 748 2019-11-23 16:36 froderik GPU Computing 4 2016-10-30 15:29 fivemack Programming 112 2015-02-12 22:51 xilman Programming 1 2009-11-16 10:26

All times are UTC. The time now is 09:43.

Fri May 29 09:43:17 UTC 2020 up 65 days, 7:16, 0 users, load averages: 1.30, 1.22, 1.25