mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > FermatSearch

Reply
 
Thread Tools
Old 2018-01-05, 22:35   #1
rogue
 
rogue's Avatar
 
"Mark"
Apr 2003
Between here and the

5,953 Posts
Default 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.
rogue is online now   Reply With Quote
Old 2018-01-06, 06:11   #2
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

23×7×163 Posts
Default

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.
Batalov is offline   Reply With Quote
Old 2018-01-06, 13:56   #3
rogue
 
rogue's Avatar
 
"Mark"
Apr 2003
Between here and the

5,953 Posts
Default

Thanks Serge. I have fixed the code, rebuilt the exe, and updated the link on my page.
rogue is online now   Reply With Quote
Old 2018-01-06, 15:15   #4
ET_
Banned
 
ET_'s Avatar
 
"Luigi"
Aug 2002
Team Italia

25·149 Posts
Default

The FermatSearch pages have been updated accordingly. Again, thank you Mark.
ET_ is offline   Reply With Quote
Old 2018-02-11, 00:07   #5
rogue
 
rogue's Avatar
 
"Mark"
Apr 2003
Between here and the

10111010000012 Posts
Default

For a multi-threaded version of gfndsieve, go here.
rogue is online now   Reply With Quote
Old 2018-02-18, 17:45   #6
houding
 
houding's Avatar
 
"Adolf"
Nov 2013
South Africa

6110 Posts
Default

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.
houding is offline   Reply With Quote
Old 2018-02-18, 18:59   #7
rogue
 
rogue's Avatar
 
"Mark"
Apr 2003
Between here and the

5,953 Posts
Default

Quote:
Originally Posted by houding View Post
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?
rogue is online now   Reply With Quote
Old 2020-05-18, 09:21   #8
houding
 
houding's Avatar
 
"Adolf"
Nov 2013
South Africa

61 Posts
Default 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?
houding is offline   Reply With Quote
Old 2020-05-18, 12:01   #9
rogue
 
rogue's Avatar
 
"Mark"
Apr 2003
Between here and the

5,953 Posts
Default

Quote:
Originally Posted by houding View Post
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.
rogue is online now   Reply With Quote
Old 2020-05-18, 16:39   #10
rogue
 
rogue's Avatar
 
"Mark"
Apr 2003
Between here and the

5,953 Posts
Default

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.
rogue is online now   Reply With Quote
Old 2020-05-18, 18:38   #11
rogue
 
rogue's Avatar
 
"Mark"
Apr 2003
Between here and the

5,953 Posts
Default

I think I tracked it down. It wasn't obvious. The code was accessing memory beyond the bounds of an vector.
rogue is online now   Reply With Quote
Reply

Thread Tools


All times are UTC. The time now is 17:01.

Thu Oct 29 17:01:22 UTC 2020 up 49 days, 14:12, 2 users, load averages: 2.37, 2.34, 2.11

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.