Monday, August 27, 2012

IsItPrime 1.7.0 Progress

This afternoon, I took another look at the way each thread determines if another thread has found factors or not.

It turns out that since they are non-mutex threads, this is very difficult. They essentially communicate only after the fact, and even then it's indirect. Imagine that instead of handing someone a written note, you instead leave it sitting on a table, then walk away and the other person later comes to look at it.

I am still fussing with the problem of finding the number itself to be a factor. Something to do with the way MPIR integer comparison functions work doesn't seem to allow me to check if the candidate number is bigger than the trial number. Since the function I use is actually a macro, I guess it evaluates its argument when the numbers are both different and the same, however that works.

I have also made some changes to the interface (even since this morning):

Tooltips over each of the radio buttons up top provide a description of what they're actually doing (or should do, or will do) - the last two do nothing as of right now.

Those buttons, labelled "square root" and "up to n," will allow you to decide the range of each of your tests. Their functions should be fairly obvious - "square root" will test only up to sqrt(n), a range in which most of a number's factors are statistically more likely to be, whilst "up to n" goes all-out and tests every single number from 2 up to (but not including) the candidate number.

These options will only be available for BFTD, as SPAT is basically just for fun. There is no solid evidence that any given number n is that much more or less likely to have small prime factors.

"Square root" will be the default setting, but "up to n" can be selected instead.

I also moved some buttons around. The Instructions button is now more visible, up in the top left, and the PANIC button has gotten bigger.

However, there are still some odd things with how that works. Both the PANIC button and the red X in the top right will call _endthread() before DestroyWindow(), which is perhaps bad practice but otherwise guarantees (or should, anyway) that the parent thread will exit. This should destroy the child threads created during tests. If a test has not been run, or has finished, then quitting any way works the same.

This goes back to the issue of the test threads being non-mutex. It would be a lot easier to use ThreadProcs and suchlike so that there could be a button on the main interface to allow the user to pause, resume, or stop one or all testing threads.

On that note, I'm going to have to write a great deal of code to get the individual "square root" and "up to n" test methods to work. Currently, BFTD runs only in one thread and only goes up to the square root. What's going to happen is three threads running at once, each stopping when their trial number equals or exceeds the value of the square root+1, or the value of n (whichever button is pressed at the time).

This requires a lot more effort than is immediately apparent. Each method requires at least 3 source files, for one thing (6 including function headers); the grand total of different testing methods and options will be this list:

  • BFTD up to sqrt(n)
  • BFTD up to sqrt(n) displaying all factors
  • BFTD up to n
  • BFTD up to n displaying all factors
  • SPAT
And describing them should be fun:
  • mid-length and relatively accurate
  • mid-length and relatively accurate and verbose
  • long and very accurate
  • long and very accurate and verbose
  • short and passably accurate and verbose
SPAT is useful for ruling out potential primes very, very quickly. As a number n increases in size, it will have more and more factors (if it has any). This is not true of every composite, but certainly most.

The way NCPrime applications work involve trial-dividing by smaller numbers first. So, if you put in an even number, 2 will be found instantly and the test will stop (unless you are in verbose mode). Many numbers also have 3, 5, or 7 as factors. These can be ruled out easily with SPAT, although any variant of BFTD will also find them.

BFTD just happens to lend itself much better to verbose mode.

The current implementation of BFTD, however, need not be changed. It stops after finding the quotient of the candidate number and the first factor found, or when it reaches (or exceeds) n.

This can easily be changed to be the "BFTD up to n displaying all factors" mode.

I don't see why one would want to run in non-verbose mode, where it gives little indication of what it's currently testing, unless you don't really care to factor a number. The more factors you find, the more sure you can be of a number's compositeness. However, the "BFTD up to n" and "BFTD up to sqrt(n)" modes will do what other NCPrime applications do, and stop after finding a single factor.

This will take several days of work at least, but everyone likes having options, so it must be done!

No comments:

Post a Comment