mersenneforum.org gfndsieve
 Register FAQ Search Today's Posts Mark Forums Read

 2018-01-05, 22:35 #1 rogue     "Mark" Apr 2003 Between here and the 22×19×83 Posts gfndsieve I have finished my optimization changes for the single-threaded version of gfnsieve. You can d/l it from here. This program can be used in lieu of fermfact. Since I tend to write portable code, this program can be compiled and run on any OS running on x86 CPUs. fermfact (as we know) only runs on Windows. Here are some ideas for speed comparing the original release with the current release and fermfact: Code: v1.0: gfndsieve -n1e4 -N2e4 -k1e5 -K2e5 -P1e6 -x : 89.19 v1.0: gfndsieve -n1e4 -N2e4 -k1e5 -K2e5 -P1e6 : 20.11 v1.0: gfndsieve -n1e4 -N2e4 -k1e5 -K2e5 -P1e9 -x : 762.18 v1.0: gfndsieve -n1e4 -N2e4 -k1e5 -K2e5 -P1e9 : 677.41 v1.1: gfndsieve -n1e4 -N2e4 -k1e5 -K2e5 -P1e6 -x : 93.53 v1.1: gfndsieve -n1e4 -N2e4 -k1e5 -K2e5 -P1e6 : 18.08 v1.1: gfndsieve -n1e4 -N2e4 -k1e5 -K2e5 -P1e9 -x : 482.57 v1.1: gfndsieve -n1e4 -N2e4 -k1e5 -K2e5 -P1e9 : 413.25 fermfact -mn=10000 -Mn=20000 -mk=100000 -Mk=200000 -O=ff -abcd1d -p=1000000 : 35.403 fermfact -mn=10000 -Mn=20000 -mk=100000 -Mk=200000 -O=ff -abcd1d -p=1000000000 : 579.689 fermfact -mn=10000 -Mn=20000 -mk=100000 -Mk=200000 -O=ff -abcd1d -p=1000000 -v- : 33.984 fermfact -mn=10000 -Mn=20000 -mk=100000 -Mk=200000 -O=ff -abcd1d -p=1000000000 -v- : 563.121 You can see that it is 20% faster than fermfact (with factor validation turned on) and almost 40% faster with it turned off. As you can see the main "pain" with factor validation is with small factors so there is little cost to factor validation past 1e6. When searching to larger p, the overall performance of gfndsieve compared to fermfact should get closer to 40% as one has already paid the cost for factor validation for small p. The other main advantage of gfndsieve are that it can handle a much larger range of n and k. It is only limited by memory. gfndsieve outputs ABCD files where each ABCD line is for a specific n. This format is not compatible with srfile or ppsieve. In the next release I intend to support both ABCD formats and in doing so it will be able to convert between the formats and process factor files from ppsieve. The current format is best when used with the Fermat Search project as users tend to sieve small ranges of n and larger ranges of k. If you run fermfact and gfndsieve for comparison there are a few things to note:fermfact will go slightly beyond the limit for p so it can find factors larger than the p specified. gfndsieve can go up to 3 primes past p. This is due to the main function doing 4 powmods at once, each for a different p. fermfact will produce smaller files, but that is because it uses Unix line feed (\n) instead of Windows carriage return plus line feed (\r\n). This will make it difficult to compare the output between the two programs, but not impossible. Other future changes such as support for multi-threading and OpenCL are possible.
 2018-01-06, 06:11 #2 Batalov     "Serge" Mar 2008 Phi(4,2^7658614+1)/2 100100110101112 Posts This may be useful: Code: *** gfnd/GFNDivisorSieveApp.cpp-1 2018-01-05 22:04:55.873078080 -0800 --- gfnd/GFNDivisorSieveApp.cpp 2018-01-05 22:05:06.152450527 -0800 *************** *** 455,460 **** --- 455,461 ---- } } + fclose(termsFile); return termCount; } ...or else the intermediate save files are not full-length. They are truncated in a haphazard fashion.
 2018-01-06, 13:56 #3 rogue     "Mark" Apr 2003 Between here and the 18A416 Posts Thanks Serge. I have fixed the code, rebuilt the exe, and updated the link on my page.
 2018-01-06, 15:15 #4 ET_ Banned     "Luigi" Aug 2002 Team Italia 2×29×83 Posts The FermatSearch pages have been updated accordingly. Again, thank you Mark.
 2018-02-11, 00:07 #5 rogue     "Mark" Apr 2003 Between here and the 22·19·83 Posts For a multi-threaded version of gfndsieve, go here.
 2018-02-18, 17:45 #6 houding     "Adolf" Nov 2013 South Africa 61 Posts I downloaded the zip file and tried to use the program. But it gives me errors. Am I supposed to compile it before using it? Can it be used as is? Because my compiling skills not that hot so don't want to spend time trying to do something that will not happen anyway.
2018-02-18, 18:59   #7
rogue

"Mark"
Apr 2003
Between here and the

22·19·83 Posts

Quote:
 Originally Posted by houding I downloaded the zip file and tried to use the program. But it gives me errors. Am I supposed to compile it before using it? Can it be used as is? Because my compiling skills not that hot so don't want to spend time trying to do something that will not happen anyway.
What OS? What errors are you getting?

 2020-05-18, 09:21 #8 houding     "Adolf" Nov 2013 South Africa 61 Posts Fatal error running gfndsieve I downloaded the latest mtsieve package to use gfndsieve. Running the command I get: C:\downloads\mtsieve_1.9.6>gfndsieve -n1e4 -N2e4 -k1e5 -K2e5 gfndsieve v1.6, a program to find factors of k*2^n+1 numbers for variable k and n Sieve started: 3 < p < 2^62 with 500050000 terms (100001 <= k <= 199999, 10000 <= n <= 20000, k*2^n+1) Fatal Error: 189461*2^10117+1 mod 1830192 = 1372097 Something that I'm missing?
2020-05-18, 12:01   #9
rogue

"Mark"
Apr 2003
Between here and the

22·19·83 Posts

Quote:
 Originally Posted by houding I downloaded the latest mtsieve package to use gfndsieve. Running the command I get: C:\downloads\mtsieve_1.9.6>gfndsieve -n1e4 -N2e4 -k1e5 -K2e5 gfndsieve v1.6, a program to find factors of k*2^n+1 numbers for variable k and n Sieve started: 3 < p < 2^62 with 500050000 terms (100001 <= k <= 199999, 10000 <= n <= 20000, k*2^n+1) Fatal Error: 189461*2^10117+1 mod 1830192 = 1372097 Something that I'm missing?
I will look into this.

 2020-05-18, 16:39 #10 rogue     "Mark" Apr 2003 Between here and the 22·19·83 Posts Very annoying. I can trigger the error, but not in debug mode. It is likely a memory leak as the error does not occur with the same prime each time.
 2020-05-18, 18:38 #11 rogue     "Mark" Apr 2003 Between here and the 22×19×83 Posts I think I tracked it down. It wasn't obvious. The code was accessing memory beyond the bounds of an vector.