GJSieve Files

GJSieve v1.9.0
22 August 2012
by Jaska (NullCoding)
http://code.google.com/p/gjsieve
http://ncprime.blogspot.com

/////////////////////////////////////////
About:

GJSieve is a basic calculator and primality tester for Proth numbers. A Proth number is any positive integer of the form k * 2^n +1 where k is a positive odd integer and n is a positive integer such that 2^n is greater than k.

This is version 1.9.0. Much has changed since previous versions, as there has been nearly a month between releases. Please read the Changes section below for details!


/////////////////////////////////////////
Changes:

- Calculating and testing the Proth number has been divided into a two-step, two-button process. Press Calculate to determine the Proth number, and Test to test it.

- Additionally, there are now two different options to test primality - brute force trial division (BFTD) and small prime array testing (SPAT). See Notes below for details. 

- Multi-threading: The test itself now runs in a separate thread, leaving you free to do things like move or resize the window (or close it, if need be) whilst the test is in progress. This also completely eliminates the "Not Responding" status that was erroneously displayed before, when the worker thread responsible for displaying the window was simultaneously performing the intense primality test. 

- The window has been re-formatted and arranged in a much better way. It is at least more conducive to reading everything naturally (that is, left to right) as well as displaying very large calculated Proth numbers in the now-larger box. 

- Some boxes have been added (but none removed). This includes a small messages box that is only used for informational messages regarding SPAT.

- The boxes for k and n have shrunk, since they are single-line anyway.

- The status bar, which was originally implemented in 1.8.0, now updates properly. It functions as a "heads-up display" of sorts. 

- Results are now saved in more descriptive files in a GJSieve 1.9.0 Results directory, which you can find in your Documents folder - whatever that may be.

/////////////////////////////////////////
How to use:

1. Input k and n in their respective boxes.

2. Click Calculate...

3. Select a testing method using the radio buttons near the top - BFTD or SPAT.

4. Press TEST!

5. Click Save As Formula if you wish to save your results. The file is automatically placed in a GJSieve 1.9.0 Results folder created in your Documents directory.

6. Click Clear to clear the boxes and reset for another test. 

/////////////////////////////////////////
Notes:

There are now two ways of testing numbers calculated in GJSieve - BFTD and SPAT - as noted in the Changes section above. 

BFTD is more accurate, but has the potential to take much longer - possibly many hours. It begins at the number 3 and uses it to divide the Proth number, then determines the remainder. This number increases by 1 each test. The upper limit for this test is the Proth number's square root plus one, since any factors found beyond the square root will be complements to factors already found. If the remainder is 0, and the number is less than the square root plus one, the trial number is a factor and GJSieve reports that it is composite. If no factors are found in this range (that is, if the remainder is always greater than 0), the number is marked as a possible prime.

BFTD's implementation in GJSieve is unfortunately still flawed, as the trial number is of type unsigned long int. The maximum value for this is 4,294,967,295. It is not the largest-capacity data type available in native C++ (that would be unsigned long long), but in order to retain this program's ability to run on native 32-bit systems, I had to settle for a 32-bit data type. This means that if sqrt(proth)+1 > 4,294,967,295, the application will enter an infinite loop where it keeps testing 4,294,967,295 until you kill it. 

SPAT is much faster, but consequently much less accurate. There is no hard evidence that a composite number is entirely likely to have factors that are small primes. I have tested numbers where the first factor found is in the hundred thousands. However, SPAT is a good way to quickly rule out numbers with small factors. For example, a LOT of numbers have the factors 3, 5, or 7. SPAT will catch those quickly. However, BFTD will do so as well.

That's why after a SPAT test finishes, your default option is to repeat the test using BFTD. Do be aware that this can run for many, many hours and IS CPU-INTENSIVE, using up to 100% of one core. Kill the application with the PANIC button if the test enters an infinite loop.  

Additionally, it should be noted that the Clear button is still (and likely always will be) simply for aesthetic purposes. It clears text from the boxes, not from memory. Since memory is dynamically and manually allocated and freed during the testing process, you theoretically don't need a Clear button at all. However, it also functions as a Reset button, so in order to test again you will need to click Clear.

/////////////////////////////////////////
Known Issues:

- The infinite loop problem described above.

- There are still vestigial menu items that do nothing.

- Re-sizing the window is possible, but ugly and pointless.

- Color choosing is a bit messed up, but works okay.

- There is no way to pause an in-progress test (yet) because it runs in an independant thread, not a synchronized mutex. 

- Sometimes, on clicking PANIC when a test is in progress, the thread will fail to exit properly and you may not be able to re-open the application until you kill the gjsieve190 process in Task Manager.