mfaktc: a CUDA program for Mersenne prefactoring

[ixfd64]

c10ck3r came up with an interesting idea over at the mfakto thread: https://mersenneforum.org/showpost.p...postcount=1511

If an exponent already has P-1 done, then we can use the bounds to eliminate any smooth factor candidates and save up to around 26% of the sieving. Would this be hard to implement?

[SethTro]

Hey!

I've recently started on poking around in mkfactc, I was curious about what made mkfactc so much faster than my sieving program. I think I can help out with a couple of features, code cleanups, and maybe even a speedup around gcd.

I've already written a couple of patches around verification[1], support for small exponents[2], general cleanups[3]). I don't see a github repository for mkfactc, what's the appropriate way to get it touch with the active developers?


[1] https://mersenneforum.org/showpost.p...&postcount=151
[2] https://github.com/sethtroisi/mfaktc...bea8c1ecfe59ab
[3] https://github.com/sethtroisi/mkfact...eam...upstream

[kriesel]

Originally Posted by SethTro

Hey!

I've recently started on poking around in mkfactc, I was curious about what made mkfactc so much faster than my sieving program. I think I can help out with a couple of features, code cleanups, and maybe even a speedup around gcd.

I've already written a couple of patches around verification[1], support for small exponents[2], general cleanups[3]). I don't see a github repository for mkfactc, what's the appropriate way to get it touch with the active developers?

[1] https://mersenneforum.org/showpost.p...&postcount=151
[2] https://github.com/sethtroisi/mfaktc/commit/f81b34fa478258f89ad92c94bbbea8c1ecfe59ab
[3] https://github.com/sethtroisi/mkfactc/compare/base_upstream...upstream

1) It's mfaktc, not mkfactc
2) Repositories (sourceforge, github, mirrors) and other info for the various software titles are documented in the attachment at post 2 of https://www.mersenneforum.org/showthread.php?t=23371
3) To my knowledge, mfaktc and other GIMPS trial factoring programs do not use gcd. At all. (P-1 factoring uses gcd.)
4) Your third link, [3] above, gave a 404 error
5) I don't recall the details, but I think there's more to supporting p<100000 than your second link shows. The discussion of those details is probably somewhere months back in the mfaktc thread here.
6) I've been for a while writing and revising a summary of trial factoring concepts, with a distinctly mfaktc oriented flavor. It's at post 6 of https://www.mersenneforum.org/showthread.php?t=23386 and was updated again today.
7) There's a considerable backlog of ideas for improving or updating mfaktc, including for taking full advantage of recently released gpu models. And the author had a prerelease version v0.22 already years ago. Please combine forces with him for efficiency and so you're not working at cross purposes.
8) Welcome.

[SethTro]

Originally Posted by kriesel

1) It's mfaktc, not mkfactc
2) Repositories (sourceforge, github, mirrors) and other info for the various software titles are documented in the attachment at post 2 of https://www.mersenneforum.org/showthread.php?t=23371
3) To my knowledge, mfaktc and other GIMPS trial factoring programs do not use gcd. At all. (P-1 factoring uses gcd.)
4) Your third link, [3] above, gave a 404 error
5) I don't recall the details, but I think there's more to supporting p<100000 than your second link shows. The discussion of those details is probably somewhere months back in the mfaktc thread here.
6) I've been for a while writing and revising a summary of trial factoring concepts, with a distinctly mfaktc oriented flavor. It's at post 6 of https://www.mersenneforum.org/showthread.php?t=23386 and was updated again today.
7) There's a considerable backlog of ideas for improving or updating mfaktc, including for taking full advantage of recently released gpu models. And the author had a prerelease version v0.22 already years ago. Please combine forces with him for efficiency and so you're not working at cross purposes.
8) Welcome.

1) A silly mistake I keep making.
2) Thanks for keeping track of all this information. In this case I did look at that resource. it has two links for mfaktc one is broken and the other is this thread.
3) I have a plan for a fast GPU implementation that I want to combine with the GPU sieve.
4) Yep it was another instance of me misspelling mfaktc. Correctly link is https://github.com/sethtroisi/mfaktc...eam...upstream

5) I'd love more details. I added 180 testcases and tested 500 more know factors and my branch finds them all. I also tried to search this thread but it's several thousand posts...

6) Thanks again for collecting and curated this information. I've seen many of your posts and learned a lot reading them. I'll reread #6

7) There's a considerable backlog of ideas for improving or updating mfaktc, including for taking full advantage of recently released gpu models. And the author had a prerelease version v0.22 already years ago. Please combine forces with him for efficiency and so you're not working at cross purposes.

That's what I'm excited about and why I'm reaching out :)

[chalsall]

Originally Posted by SethTro

1) A silly mistake I keep making.

Silly mistakes are part of being human.

I must apologize for being rather stupid here recently, and causing offense.

This is not an excuse, but I'm under a little bit of pressure at the moment. Working on something which is rather important.

Interacting with other very intense individuals helps me channel my focus, but I understand and appreciate that not everyone understands or appreciates what I'm doing.

Sorry for being an ass. Sincerely.

[Prime95]

Originally Posted by chalsall

Working on something which is rather important.

Sorry for being an ass. Sincerely.

Thanks and welcome back.

Good luck with your stressful project.

[kriesel]

Originally Posted by SethTro

1) A silly mistake I keep making.

Silly mistakes and their close kin stupid questions are my favorites. They're generally the easiest to address. ;)

2) Thanks for keeping track of all this information. In this case I did look at that resource. it has two links for mfaktc one is broken and the other is this thread.

Glad it's useful. I'll check those links.

3) I have a plan for a fast GPU implementation that I want to combine with the GPU sieve.
4) Yep it was another instance of me misspelling mfaktc. Correctly link is https://github.com/sethtroisi/mfaktc...eam...upstream

5) I'd love more details. I added 180 testcases and tested 500 more know factors and my branch finds them all. I also tried to search this thread but it's several thousand posts...

Read it a little at a time and take notes as you go. It pays off. For example, re lower p bound, see Laurv's post at https://www.mersenneforum.org/showpo...postcount=2735

6) Thanks again for collecting and curated this information. I've seen many of your posts and learned a lot reading them. I'll reread #6

My posts are easy to find, since there are so many.

(re collaborating and making headway on the considerable backlog of enhancement ideas):

That's what I'm excited about and why I'm reaching out :)

Please consider backporting mfakto's approach to more-classes/less-classes if practical. It would cut down on the number of flavors of mfaktc needed, to have it be an ini file entry as I recall mfakto does. Here's what that looks like in the mfakto ini file:

# MoreClasses is a switch for defining if 420 (2*2*3*5*7) or 4620 (2*2*3*5*7*11) classes of
# factor candidates should be used. Normally, 4620 gives better results but for very small classes
# 420 reduces the class initialization overhead enough to provide an overall benefit.
# Used only when sieving on the GPU; the CPU-sieve will always use 4620 classes.
#
# Possible values:
# MoreClasses=0 (use 420 classes)
# MoreClasses=1 (use 4620 classes)
#
# Default: MoreClasses=1

MoreClasses=1

And one of my priority wishlist items is user-optional reduction of screen output independently of selecting moreclasses or lessclasses. See https://mersenneforum.org/showpost.p...postcount=2703

[Rodrigo]

Help! I'm trying to set up MFAKTC on a newly arrived (refurbished) GTX 960 running in an old Windows XP machine, but thus far without success.

The XP has been happily TFing on MFAKTC (CUDA 4.2) with a GeForce GT 730. Somewhere along the way I came to understand that a GTX 960 won't run on CUDA 4.2, so I downloaded the CUDA 6.5 version of MFAKTC, extracted it to its own directory on the XP, and tried to run it from a command prompt as usual. However, the program keeps failing with a dialog box stating that, "MFAKTC-WIN-32.EXE is not a valid Win32 application," and then a new line is output to the command line saying that, "Access is denied."

What am I doing wrong, and what do I need to do to get this working? There are a lot of balls to juggle here, and I don't know which one I'm failing to catch.

[kriesel]

Originally Posted by Rodrigo

Help! I'm trying to set up MFAKTC on a newly arrived (refurbished) GTX 960 running in an old Windows XP machine, but thus far without success.

The XP has been happily TFing on MFAKTC (CUDA 4.2) with a GeForce GT 730. Somewhere along the way I came to understand that a GTX 960 won't run on CUDA 4.2, so I downloaded the CUDA 6.5 version of MFAKTC, extracted it to its own directory on the XP, and tried to run it from a command prompt as usual. However, the program keeps failing with a dialog box stating that, "MFAKTC-WIN-32.EXE is not a valid Win32 application," and then a new line is output to the command line saying that, "Access is denied."

What am I doing wrong, and what do I need to do to get this working? There are a lot of balls to juggle here, and I don't know which one I'm failing to catch.

Per https://en.wikipedia.org/wiki/CUDA the GTX960 requires CUDA 5.2, so you seem to have gotten that part right. I suggest checking what version of Windows your newly downloaded mfaktc.exe was compiled for. Also look into what NVIDIA driver version you have installed and what CUDA levels that supports. And what version dlls you have in place; should be a match to the mfaktc.exe; CUDA6.5.

[Rodrigo]

Originally Posted by kriesel

Per https://en.wikipedia.org/wiki/CUDA the GTX960 requires CUDA 5.2, so you seem to have gotten that part right. I suggest checking what version of Windows your newly downloaded mfaktc.exe was compiled for. Also look into what NVIDIA driver version you have installed and what CUDA levels that supports. And what version dlls you have in place; should be a match to the mfaktc.exe; CUDA6.5.

OK, I have this driver installed, it's the one that the Nvidia site led me to when entering the particulars on the driver downloads page.

How does one check which version of Windows MFAKTC 0.21 was compiled for? The ZIP file contains 32- and 64-bit versions and this XP is 32 bits, so...

Regarding the other types of info you asked about, I've struck out on all of them. The release notes for this driver were of no help, and I didn't find anything that looked useful in Device Manager. A Web search for "what CUDA level does 368.81 driver support" didn't turn up anything; the specifications page for the 960 says merely that "Yes" it supports CUDA, but not what levels.

[Rodrigo]

According to the first post on this page, the 368.81 driver should support CUDA 8.0 as well as previous levels. The thread addresses Ubuntu, but I have to think that the concepts are equally applicable to Windows.