Trial division with CUDA (mmff) -- used, but runs like new!

[Batalov]

Originally Posted by ET_

- What do you mean with "The highest testable N is now 223, and the highest bitlevel is 252. Practically, because k<=2^45 are already tested, the highest usable N is 207"? The previous limit of mmff-0.27 was N<174; is the actual limit equal to N<208?

I mean exactly what I wrote. The previous (0.27) nominal limit was N<192.
You could test N=191 for k's up to 29 bits is size.
Current nominal limit is N<224.
You could test N=223 for k's up to 29 bits is size.

Originally Posted by ET_

- Our previous version was limitd to k>2²⁴. Does this limit still stand?

Maybe it was for very low values of N. For high values of N, 2¹⁴<k<2⁶³ are allowed, and indeed this input line

FermatFactor=217,16384,32767    ; Suyama (1980)

works ...and recovers the factor.

I think I want to modify the code a little bit to report factors in the normalized form. (Albeit it is not too hard to do by hand. But doing it all the time for GFN factors is getting a bit old for me and the output is looking horrendous, even if awe-inspiring) E.g.

GF(181,3) has a factor: 2269880559811350882108268285448756599351611328777559153780432306177 [TF:220:221:mmff-gfn3 0.28 mfaktc_barrett224_F160_191gs]
GF(199,5) has a factor: 5240660087353831676253871671260590507538335119049430450977887836562259969 [TF:241:242:mmff-gfn5 0.28 mfaktc_barrett247_F192_223gs]
GF(206,12) has a factor: 26264920974787795159990461827258813827760860586148343034700355283076513793 [TF:243:244:mmff-gfn12 0.28 mfaktc_barrett247_F192_223gs]

will become

GF(181,3) has a factor: 370291543969*2^182+1 [TF:220:221:mmff-gfn3 0.28 mfaktc_barrett224_F160_191gs]
GF(199,5) has a factor: 407658847371*2^203+1 [TF:241:242:mmff-gfn5 0.28 mfaktc_barrett247_F192_223gs]
GF(206,12) has a factor: 15961621533*2^210+1 [TF:243:244:mmff-gfn12 0.28 mfaktc_barrett247_F192_223gs]

[Batalov]

Here is the patch. Some people will need the output be exactly as it was before, so they should not apply the patch.

*** ../../mmff-0.28/src/output.c        2012-10-22 14:00:18.000000000 -0400
--- output.c    2014-06-23 14:20:52.416938792 -0400
***************
*** 438,454 ****

    if(factor_number < 10)
    {
      if(mystuff->mode != MODE_SELFTEST_SHORT)
      {
        if(mystuff->printmode == 1 && factor_number == 0)printf("\n");
!       printf("%s has a factor: %s\n", exponent_string, factor);
      }
      if(mystuff->mode == MODE_NORMAL)
      {
  #ifndef MORE_CLASSES
!       fprintf(resultfile, "%s%s has a factor: %s [TF:%d:%d%s:mmff %s %s]\n", UID, exponent_string, factor, mystuff->bit_min, mystuff->bit_max_stage, ((mystuff->stopafterfactor == 2) && (mystuff->stats.class_counter <  96)) ? "*" : "" , MFAKTC_VERSION, mystuff->stats.kernelname);
  #else
!       fprintf(resultfile, "%s%s has a factor: %s [TF:%d:%d%s:mmff %s %s]\n", UID, exponent_string, factor, mystuff->bit_min, mystuff->bit_max_stage, ((mystuff->stopafterfactor == 2) && (mystuff->stats.class_counter < 960)) ? "*" : "" , MFAKTC_VERSION, mystuff->stats.kernelname);
  #endif
      }
    }
--- 438,473 ----

    if(factor_number < 10)
    {
+     char k[155]; int carry, i, l, N;
+
+     /* SB: don't want to mess with lower functions; I will simply do the k calculation here on a decimal string */
+     /* factors are extremely rare, anyway */
+
+     l = strlen(factor)-1;
+     memcpy(k, factor,l+2);
+     for(N=0; N==0 || (k[l]%2)==0; N++) {      /* factor = "k*2^N+1"; disregard last odd digit once */
+       for(i=carry=0; i<=l; i++) {
+         int d = k[i] - '0' + 10 * carry;
+         carry = d & 1;
+         k[i]  = d / 2 + '0';
+       }
+     }
+     l++; /* now it is strlen */
+     for(i=0; k[i]=='0'; i++);         /* squeeze leading zeroes */
+     if(i) { l -= i; memmove(k, k+i, l); }
+     sprintf(k+l, "*2^%d+1", N);
+
      if(mystuff->mode != MODE_SELFTEST_SHORT)
      {
        if(mystuff->printmode == 1 && factor_number == 0)printf("\n");
!       printf("%s has a factor: %s\n", exponent_string, k);
      }
      if(mystuff->mode == MODE_NORMAL)
      {
  #ifndef MORE_CLASSES
!       fprintf(resultfile, "%s%s has a factor: %s = %s [TF:%d:%d%s:mmff %s %s]\n", UID, exponent_string, k, factor, mystuff->bit_min, mystuff->bit_max_stage, ((mystuff->stopafterfactor == 2) && (mystuff->stats.class_counter <  96)) ? "*" : "" , MFAKTC_VERSION, mystuff->stats.kernelname);
  #else
!       fprintf(resultfile, "%s%s has a factor: %s = %s [TF:%d:%d%s:mmff %s %s]\n", UID, exponent_string, k, factor, mystuff->bit_min, mystuff->bit_max_stage, ((mystuff->stopafterfactor == 2) && (mystuff->stats.class_counter < 960)) ? "*" : "" , MFAKTC_VERSION, mystuff->stats.kernelname);
  #endif
      }
    }

[Batalov]

Attached is the mmff-gfn v.0.28 source. I've tested it thoroughly on all new bit ranges, but let me know if you will encounter errors.

When building the binaries, build five times (after editing Makefile, the row "BASE = ..."), and do 'make clean' between builds. Jerry will probably help us build all Windows binaries as previously.

Good hunting to all!

[Batalov]

Originally Posted by ET_

As I am actually lacking a GPU system, may I ask for some volunteering effort? Our site would benefit from an executable version of mmff-0.28 for the main OSes.

Thank you

Luigi

Luigi, until yesterday I could only build and test on linux. I can build and post the linux64 binaries with 2.0, 2.1, 3.0 and 3.5 enabled and based on CUDA 5.0. I cannot build distributable Windows binaries (I tried - it sort of builds...); we'll have to ask Jerry.

I will have to dig deep back into PMs where Xyzzy sent me instructions how to ftp binaries to the site. It's been 2 years - I don't remember any passwords at all.

[flashjh]

mmff and mmff-gfn 0.28 Windows binaries x86 and x64 posted to:

http://mersenneforum.org/mmff/

and

http://mersenneforum.org/mmff-gfn/

Everything is CUDA 6.0, sm_20, 21, 30, 32, 35 and 50.

If you need anything else, let me know.

[Batalov]

Many thanks! ;-)

[flashjh]

Originally Posted by Batalov

Many thanks! ;-)

No problem

[ET_]

Originally Posted by flashjh

mmff and mmff-gfn 0.28 Windows binaries x86 and x64 posted to:

http://mersenneforum.org/mmff/

and

http://mersenneforum.org/mmff-gfn/

Everything is CUDA 6.0, sm_20, 21, 30, 32, 35 and 50.

If you need anything else, let me know.

Thank you!

I will soon update FermatSearch with your executable.
Now, only Linux and MAC executables are missing...

Luigi

[ET_]

New CUDA version, new mmff required.

A friend of us required a mmff version compiled for his GTX 1060 and CUDA 8.

I have no Nvidia SDK or boards on my PC at the moment, so I can provide neither Linux nor Windows ones. I hope I will have a Windows version soon (thanks to Jerry).

Thank you!!

Luigi

[RichD]

I have compiled mmff-gfn with CUDA 8.0 on linux with sm_30, 35, 50, 52, 61. The binary is mmff-gfn3.exe. Hopefully, this is helpful.

The source of the file is here.

[ET_]

Originally Posted by RichD

I have compiled mmff-gfn with CUDA 8.0 on linux with sm_30, 35, 50, 52, 61. The binary is mmff-gfn3.exe. Hopefully, this is helpful.

The source of the file is here.

That friend of mine tried to compile the source of mmff 0.28 under Windows for a GTX 1060 with no success. Source is available to mersenneforum/mmff, download.mersenne.ca and doublemersennes.org. It is the executable for Windows (and Linux) for CUDA 8 I am looking for, as I have no CUDA platform available at this time.