Thread: gfndsieve
View Single Post
Old 2018-01-05, 22:35   #1
rogue's Avatar
Apr 2003
Between here and the

11000101000002 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:

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