GFN Deep Sieve

AthGFNSv.zip | - 32 bit Sieve - Build 213, March 13, 2003 |

AthGFNSv.exe | - 32 bit Sieve - Build 213, March 13, 2003 |

AthGfn64.zip | - 64 bit Sieve - Build 304, September 3, 2009 |

AthGfn64.exe | - 64 bit Sieve - Build 304, September 3, 2009 |

AthGfn64B306.zip | - 64 bit Sieve - Build 306, November 21, 2011 |

**AthGfn64**

Build 306 - Modified the factor output file per PrimeGrid factoring file requirements. There are references to packed K files and running non-wide mode in the user interface. These are all disabled for the PrimeGrid release version, which only runs in wide mode.

Build 304 - Rearranged the user interface for clarity. Added an optional starting P and ending P value. When in use, set these values to an even number. That way it guarantees exclusive coverage. Overlapping 1 p value when splitting the sieve into multiple ranges is a very small price to pay for full coverage.

The pipelined optimization routines require a minimum exponent value of 32 to fill the pipelines. Anything less than that will not run.

Build 303 - Initial release. AthGfn64 is 60% to 80% faster than AthGFNSv on my test machines. Only wide sieve mode is supported. Always start with a lower limit of 2. Anything higher does not speed up the calculations, but only inhibits the values in the output file. The starting and stopping B values must be even.

One note about the factors file. It is opened in non-shared mode. You cannot view the factor file when it is open. The fix is another future enhancement. For now, the program closes the factors file (if open) every 5 seconds. It does not re-open until another factor is found. To look at the factors file of a running program, you really have to wait until not much is being written, and then open it before another factor is found.

Even though this is much faster than AthGFNSv, it still contains all the verification routines. The logic is:

- Generate a trial p value. Actually generate many of them in parallel.- Calculate the first primitive root.

- Verify the first primitive root, i.e. 0 = root^2^N+1 mod p

- Calculate 1/2 of the 2^N roots. Derive the rest via the additive inverse.

- Discard all roots > b Max

- For each new root not previously found, verify the result before accepting it.

I have never seen an error message from any verification step in many CPU-years of running (except when debugging and program verification). Just the same, I feel better leaving the verification code in the program.

**AthGFNSv**

Build 213 - Add logging all output to athgfnsv.log in the same directory as the executable. Add control of the priority class under the options menu. The worker thread is always below normal priority in whatever class is selected.

Build 212 - No changes to the wide sieve logic or implementation. Some speed increases were added to the standard trial division sieve (SSE2 version) when processing small numbers of candidates. Also there was an occasional consistency warning generated in this section. The cause of the warning was fixed. Lower the minimum number of candidates required in a standard sieve to 1. The packed K file logic was enabled. There are various updates to specialized features and report generation currently used only by the author.

Build 206 - Removed the GFN lower limit of 8192. N can now be any GFN exponent. Also updated the resume sieve for the non-wide mode to allow for a resume of a standard sieve without a factoring input file. Leave this input blank (empty) to resume a standard sieve from only a sieve output file.

Build 204 - Added SSE2 support for Pentium 4 computers. The P4 and Athlon versions are now both very fast. Build 204 runs on PIII, P4, or Athlon. It is optimized only for Athlon and P4.

**Credits Update**

Phil Carmody lead the research into the math required for a wide GFN sieve algorithm. His ideas made wide sieving possible.

Yves Gallot provided some key ideas into optimizing the SSE2 implementation. I am very grateful for the time and effort he contributed to this effort.

Warning, with AthGFNSv if you forget to select the Wide Range Math option and specify a wide range, you may try to allocate hundreds of megabytes of RAM to do a normal process. Expect 1 MB for each 10,000 b values in the range. With Wide Range Math, this is not a consideration.

New Wide Sieve - Select Start New Sieve, check Wide Range Math, select factors output file and candidates output file, exponent and b range, and hit start. In wide range math, the factors are appended to the factors output file. If wide range math is not selected, the factors output file is overwritten (after a warning and a chance to abort before actually overwriting it.) The factors file is not sorted by b values.

Continue Wide Sieve - Select Resume Old Sieve, check Wide Range Math, select factors output file, in candidate file and out candidate file. Again, in wide range math, the factors are appended to the factors output file. If wide range is not selected, a warning will be given with an abort option before overwriting the factors file.

To regenerate a sorted factor and candidate file from a factors file generated by Wide Range Math, select the Build From Factors option. All the factors are double checked, sorted, and written using the format of the normal factoring options. Candidates are sorted and written in standard format (which is the same for wide or normal mode). It does not matter whether the Wide Range Math checkbox is selected. Use this for only small ranges, 40,000 b ranges or less since the memory requirements and sorting times are not optimized.

The Generate Report option takes a standard factors file and a proth.log file (verbose with date format selected) and generates a report with the factors and composite tests. It checks to make sure all b values are either in the factors file or the proth.log file. This routine is very dependent upon data format and is a quick and dirty method basically for the author only and not generally supported.

**Credits**

I would like to thank Yves Gallot for assistance and for an independent verification routine to help double check that factors identified are really factors.

**Disclaimer**

The software on this page is free to the general public for usage in their prime number searches. Each user must understand that they use this software at their own risk. If LLR, PRP, Proth, or Prime95 make your computer run too hot, so will this software. The only guarantee I can provide is that I personally use this software in my prime searches.

David Underbakke