gfndsieve

[rogue]

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.

[Batalov]

This may be useful:

*** 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.

[rogue]

Thanks Serge. I have fixed the code, rebuilt the exe, and updated the link on my page.

[ET_]

The FermatSearch pages have been updated accordingly. Again, thank you Mark.

[rogue]

For a multi-threaded version of gfndsieve, go here.

[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.

[rogue]

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?

[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?

[rogue]

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.

[rogue]

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]

I think I tracked it down. It wasn't obvious. The code was accessing memory beyond the bounds of an vector.