mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Hardware > GPU Computing

Reply
 
Thread Tools
Old 2018-09-13, 18:52   #2850
MrRepunit
 
MrRepunit's Avatar
 
Mar 2011
Germany

10101112 Posts
Default

Quote:
Originally Posted by Citrix View Post
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)

<br />
  \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}<br />

<br />
  \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}<br />


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 is offline   Reply With Quote
Old 2018-09-13, 19:05   #2851
MrRepunit
 
MrRepunit's Avatar
 
Mar 2011
Germany

3·29 Posts
Default

Quote:
Originally Posted by kriesel View Post
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.
MrRepunit is offline   Reply With Quote
Old 2018-09-13, 19:39   #2852
Citrix
 
Citrix's Avatar
 
Jun 2003

5·307 Posts
Default

Quote:
Originally Posted by MrRepunit View Post
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)

<br />
  \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}<br />

<br />
  \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}<br />


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.
Citrix is offline   Reply With Quote
Old 2018-09-14, 19:17   #2853
GP2
 
GP2's Avatar
 
Sep 2003

A1216 Posts
Default

Quote:
Originally Posted by MrRepunit View Post
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?
GP2 is offline   Reply With Quote
Old 2018-09-14, 19:26   #2854
MrRepunit
 
MrRepunit's Avatar
 
Mar 2011
Germany

1278 Posts
Default

Quote:
Originally Posted by Citrix View Post
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).
MrRepunit is offline   Reply With Quote
Old 2018-09-14, 19:49   #2855
Citrix
 
Citrix's Avatar
 
Jun 2003

5·307 Posts
Default

Quote:
Originally Posted by MrRepunit View Post
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.
Citrix is offline   Reply With Quote
Old 2018-09-14, 19:59   #2856
MrRepunit
 
MrRepunit's Avatar
 
Mar 2011
Germany

3×29 Posts
Default

Quote:
Originally Posted by GP2 View Post
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
File Type: zip mfaktc-0.21-repunit.zip (1.25 MB, 56 views)
MrRepunit is offline   Reply With Quote
Old 2018-09-14, 20:07   #2857
MrRepunit
 
MrRepunit's Avatar
 
Mar 2011
Germany

10101112 Posts
Default

Quote:
Originally Posted by Citrix View Post
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...
MrRepunit is offline   Reply With Quote
Old 2018-09-14, 20:14   #2858
Citrix
 
Citrix's Avatar
 
Jun 2003

5×307 Posts
Default

Quote:
Originally Posted by MrRepunit View Post
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.
Citrix is offline   Reply With Quote
Old 2018-09-17, 14:02   #2859
storm5510
Random Account
 
storm5510's Avatar
 
Aug 2009
U.S.A.

22×3×101 Posts
Default

Quote:
Originally Posted by MrRepunit View Post
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.

storm5510 is offline   Reply With Quote
Old 2018-09-17, 22:56   #2860
kriesel
 
kriesel's Avatar
 
"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest

11×347 Posts
Default

Quote:
Originally Posted by storm5510 View Post
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?
kriesel is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
mfakto: an OpenCL program for Mersenne prefactoring Bdot GPU Computing 1615 2020-05-16 23:55
The P-1 factoring CUDA program firejuggler GPU Computing 748 2019-11-23 16:36
"CUDA runtime version 0.0" when running mfaktc.exe froderik GPU Computing 4 2016-10-30 15:29
World's second-dumbest CUDA program fivemack Programming 112 2015-02-12 22:51
World's dumbest CUDA program? 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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.