This is the home of NCPrime software, providing free and open-source programs relating to prime numbers!
It's also generally a blog about programming with the occasional rambling on number theory or discrete mathematics.
In a perfect world, GJSieve would still use trial division, but in
such a way that each operation took place in a separate process that
communicated with others. It would then be a true sieve, which are
designed to find factors, rather than a strange hybridization that also
happens to tell you if the number might (likely) be prime.
for other NCPrime applications are bouncing around everywhere -
MuPuPriNT 1.2 for one, now that the reverse implementation is ready to
be expanded to other types of numbers - but as far as GJSieve goes, I'd
like to do this:
localize for Chinese (Traditional) and German
create a true 64-bit version
a central database of previous tests so that you can see whether or not
you've tested a specific number before and/or whether or not it was
The latter would be quite difficult to do (initially).
The localization should be fairly straightforward in terms of resource
files (simply localize satellite assembly files within Visual Studio)
but time-intensive for everything else (user-visible runtime strings).
The approach would have to be similar to how one localizes a Mac
application using runtime macros.
Making a 64-bit version would actually be the easiest thing on this list to do. It would involve removing the intrinsic assembly code that finds and displays your CPU and RAM, but as that's simply an aesthetic feature (and distinguishes program screenshots to a degree), it shouldn't be missed too much!
Additionally, expanding GJSieve's interface and functionality to become MuPuPriNT would be considerably easier in a true 64-bit environment. I won't say too much on that now, as many of my initial ideas are likely wrong or based on incomplete information at the moment.
As an aside, it'd also be kind of cool to implement a function that takes a screenshot of the window...but I think I might have a way to do that already. 64-bit first, though.
I have eliminated the "first factor finder" loop I had tried to implement in GJSieve 2.0. It simply makes more sense to test only up to the square root, even in verbose mode. There is no reason to go all the way up to the first quotient found, as it will return and print the quotients as it finds factors anyway.
Additionally, the dual-loop system was simply causing too many problems with communication and the like.
I am now using only four thread structures - one for info and handles used across threads, and three thread information/variable structures (one for each actual testing thread).
That all said, I am STILL having the issue where I cannot stop a test, clear out the boxes, and then start a new test.
I am, however, on the verge of figuring it out (I hope). It almost definitely has something to do with the way in which thread structures are kept in memory and the way the stop event is signaled (set) and signaled (reset). I just can't quite figure out what.
Currently, the way I have it set up is not really working either. In fact, only one thread appears to actually stop (the second one) - this makes absolutely no sense! I will admit, however, that I am not incredibly familiar with synchronization...so that is probably why.
Just thought I'd check in again, since lately I've either not been posting much or I've been posting about the Mac versions on which I've been focusing. Considering that as of late I've run into a pretty obnoxious localization problem, I may as well go back to the Windows apps I've let sit in their unfinished and problem-ridden state for going on three weeks!
With the release of OS X 10.8.2, Facebook is now an integration and sharing option in the Mac operating system, as it has been in iOS for some time now. This means that you need only click a little button in, for example, Preview in order to post a picture to Facebook directly from your desktop.
Twitter integration came with the original release of Mountain Lion, so I jumped on that with IsItPrime and, later, GJSieve. It's somewhat pointless, but fun just the same. It is also a useful thing to know how to do. With the advent and inevitable promulgation of social media, there is almost no situation in which one lacks the option to stay "plugged in."
I suppose that, in a strange way, this includes the niche of recreational mathematics, a field in which no progress is ever or can be made without communication and sharing of results and findings.
Facebook sharing from IsItPrime looks like this:
I don't believe it is possible to change where it says "via OS X" (to something like "via NullCoding" or "via IsItPrime") without either making IsItPrime a Facebook application or somehow integrating the Facebook API...
I also can't exactly figure out a way to include links/tags in the post. Links would be easy, but to what? I guess the project site, right? Seems like a decent enough idea. Twitter posts include a shortened link to the SourceForge site, after all.
I had another idea (actually, as I was writing this) to include a database-type file in the program that keeps track of numbers you have already tested. I'm imagining a drawer on the side of the window with records of previous tests where the tooltip text for each list entry (that is, each number) is something like "X is prime" or "Y has Z factors" or something cool like that.
In my work with Java lately, I have been trying to figure out the best way to dynamically append a JList (a simple list container) from a file where each item in the list is a line from the file. This is not exactly related to IsItPrime, but the concept of appending (rather than re-writing) the same file over and over is essentially the same.
I have also been working on localizing IsItPrime and GJSieve, specifically in German and traditional Chinese. The window and buttons and such are done, but the menu is not and neither are any of the internal (user-visible) strings. I know how to do it, but can't quite get it to work. Something about "genstrings..."
I'll work on it later. I believe this will officially be version 0.5b. I may possibly re-brand it as a version 1 point something if I find it stable and/or complete/feature-rich enough.
I just took a look at the NSThread class in Objective C and successfully implemented it for testing large numbers in IsItPrime. It supports stopping the test, but not pausing/resuming.
From what I understand, it is unsafe to sleep and resume a thread in Objective-C. The way to do it would be using a thread pool with worker threads and a central delegate which would provide them with functions containing different testing ranges.
That would be a lot of work. A lot of work. But that's not to say I will never get to it. The year is still quite young.
The next step is to implement the same practice in GJSieve for Mac.
After that, I can finally begin work on MuPuPriNT 0.7a for Mac. This will include GJSieve for Proth, Cullen, Woodall, and Pythagorean numbers. This will also forgo the "chooser" window in favor of a series of check boxes and stuff like that.
And it's Friday, meaning I should hopefully be able to work a lot this weekend!
It ought to be fairly easy to figure out how this program works. Simply enter a dimension (even multiples of 10 greater than 100 recommended) and choose two colors - first the background and then the dot color.
It can still take some time to generate the spiral, so be patient. On slower systems, it will take a lot longer.
This program may not work if you are running a version of Java prior to SE 1.6.*.
I have finished a cursory testing process and have deemed GJSieve for Mac to be fully operational - if not even somewhat stable!
You can find it here. Bear in mind that yes, OSX 10.8.0 or later (Mountain Lion) is in fact required. I still do not know for sure if this will run on previous versions of OSX.
In other news, GJSieve 2.0 for Windows is coming along...it no longer fails to test multiple times in a row, but I am hitting a weird problem where subsequent tests after a cancelled test simply stop at the first factor regardless of verbose mode being enabled or not.
I gave up on the threading implementation I tried in GJSieve 2.0 for Windows. It was far too cumbersome and (as it turns out) incredibly unstable. So I am trying a new method using a single giant class. Hopefully it works better.
This involves two separate structures which pass pointers to each other. I sincerely hope that following this advice will help alleviate the serious stability issues I found.
At the same time, GJSieve for Mac is in progress. This will be version 0.5, technically. It will look a lot like IsItPrime 0.2, though not identical. One of the (few) perks of an automagic IDE such as XCode is the ability to use the exact same graphical layout across multiple applications simply by copying and pasting and changing a few important parameters.
It has been a strange day. I spent most of the last hour waiting for webpages to load on the junky old laptop I bring to class with me. I really ought to buy a new one - thinking of an ASUS K53, but any suggestions on inexpensive (as in less than $400) but not-terribly-quality laptops are welcome!
After much fussing with the file-saving mechanism in IsItPrime for Mac, I have finally completed a relatively satisfying release candidate!
For those of you keeping score at home, I was using deprecated methods to create files and folders - by which I mean they went obsolete around 2008 - and thus was consistently trying to access memory registers that don't really exist. Oops! Well, at any rate, it's fixed now and there ought to be no problems.
Indeed, there are no serious issues with IsItPrime for Mac. It is in fact considerably faster than its Windows complement (and I am still unsure of exactly why) and uses much less memory and CPU time.
It is still CPU-intensive, though - just not for as long. IsItPrime for Mac is also not multi-threaded, meaning that if you enter a particularly large number that just so happens to be prime, the interface may lock up (though hopefully not for long).
You can find a (hopefully) attractively laid-out disk image here. Alternatively, check out the main project site if you haven't already.
Wiki and documentation updates are forthcoming.
Bear in mind that this version of IsItPrime for Mac, along with all other forthcoming NCPrime applications for Mac require at least OSX 10.8.0 (that is, Mountain Lion) on a 64-bit (native or emulative) CPU.
I have not tested this application on any previous version of OSX, as I do not exactly have access to a slew of testing machines. However, I can tell you that since I used the 10.8 SDK as the base architecture for this build, it may not even open on previous versions of OSX and, if it does, may exhibit unusual or undefined behavior.
That sure sounds intimidating! Don't let it stop you from checking out IsItPrime for Mac.
I have finalized the threading procedure for GJSieve 2.0, which will later be implemented in every NCPrime application. First and foremost, I will polish GJS 2.0, and then begin work on what will eventually become MuPuPriNT 1.2b.
This next version of MuPuPriNT will ultimately forgo the "chooser" window in favor of a GJSieve-like interface where you will have the ability to select Proth, Cullen, Woodall, or Pythagorean tests using radio buttons. This will involve the removal of the CPU/RAM display window. It was originally there just for fun, anyway.
As I have mentioned before, this also allows for the creation of a fully 64-bit version of NCPrime applications, since inline assembly code using the _asm intrinsic is only available in 32-bit (for now). Perhaps VS2012 will change that, but I don't really know. I will find out, however.
Additionally, I have been thinking about doing translations of my applications. Partially, this would also be "just for fun" (as with most of what I do with programming to begin with), but would also serve the purpose of giving me a practical outlet for my linguistic studies.
I have also been working on updating IsItPrime for Mac, which will also allow for the eventual re-writing of other NCPrime applications for Mac. I am currently seeking support/help for and with XCode and other programming methods, since my main problems stem not from my applications themselves, but rather the IDEs I use to design them!
Strongly considering switching to Notepad++ and a command line...
Also, I can't figure out SVN or Git to save my life. It's a problem.
MuPuPriNT 1.2 will essentially be GJSieve 2.0 with buttons to select the type of number you wish to test as opposed to having to open an entirely different window.
Additionally, I think I may remove the box using Assembly code to retrieve and display your CPU and RAM. Formatting of this string is different on practically every machine I have tested - sometimes there are no spaces, and other times there are far too many! It was a nice idea. But, that space could be reclaimed and put to better use.
GJSieve 2.0 is still under development. I have some serious issues with thread management at the moment, so I must fix that up before I even consider expanding the already-huge project to include what is essentially (and have previously been) three separate applications.
I decided (about two hours ago) that GJSieve 2.0 was going to calculate the Proth number in a separate thread.
So, I implemented that. In retrospect, I don't really know why. Turns out that the reason GJSieve (for Windows, at least) took so long to "calculate" huge numbers was not due to the calculation at all - it was the printing of the number to the box!
So now, I am faced with a choice - find a way to incrementally print the calculated number to the box that does not involve a single giant string, or else severely limit the size of the numbers the user can test (rendering the application essentially useless).
Currently, if I were to calculate a number 3 million digits in length, it takes 0.003 seconds. However, the time taken to print it to the display box is seemingly (and inconveniently) infinite. I cannot quite tell if the thread is actually hanging or working (as CPU and memory usage remain quite high), but I'm willing to bet that writing a 3 million digit number to what is essentially an array with 3 million slots, followed by performing the necessary conversion to a wide-character array (also 3 million in length) is a generally terrible idea.
In C++, array length is virtually unlimited, yet physically highly limited. The first limit is obviously stack size, which I increased all the way to 25MB (which is admittedly small) before stopping to head off to work. I wasn't getting overflows...yet. The second limit is physically installed memory, of which I must rather hesitantly admit I have only 4GB - yes, even on my custom-built, highly optimized NCS Northwave machine.
The solution which first came to mind is using a vector to cycle through the number's digits and essentially print them one at a time, pushing and popping Assembly-style as necessary. This is not exactly possible, nor would it be much fun to write.
The other idea I had is to use gmp_snprintf() instead of mpz_get_str(). This should fill up, but not exceed, the buffer initialized with the size of the Proth number. sprintf() has no protection against this. Oops!
At any rate, I will have to try all that at some other time...
The basic idea with the experimental six-thread testing method is to speed up the overall testing process. But how?
Well, I started on it last night when I randomly got the idea, and drew out a schematic whilst bored in class earlier today. I call it "Reverse," which is probably a bad name, but does describe what half of the threads do.
Threads 1, 2, and 3 each look for the first factor of the Proth number. Upon finding it, they test like this:
first factor + 1 up to sqrt(Proth)/2 with first factor += 3
first factor + 2 up to sqrt(Proth)/2 with first factor += 3
first factor + 3 up to sqrt(Proth)/2 with first factor += 3
Threads 4, 5, and 6 don't care about the first factor, but they do care about the square root. They care a lot. They set the variable mpTrial to sqrt(Proth) and test like this:
mpTrial -1 down to sqrt(Proth)/2 with mpTrial -= 3
mpTrial -2 down to sqrt(Proth)/2 with mpTrial -= 3
mpTrial -3 down to sqrt(Proth)/2 with mpTrial -= 3
This effectively cuts the testing range (from 2 to the square root) in half.
However, it does not work properly. Not at all. In fact, it only does some of what it's meant to do. That's why I was posting about thread management (of the SAFE variety) and why GJSieve 2.0 is not available to download!
Naturally, now that I know how to multi-thread my application, I have found excuses to do it just about everywhere. Yet to come is a separate thread for calculating (as opposed to testing) the number, so that the application doesn't seize up when you tell it to calculate a million+ digit number. That ought not be too difficult.
With GJSieve 2.0 being well on its way to "completion," I've taken another look at MuPuPriNT for Windows 1.1 and decided to scrap it.
Currently, it contains GJSieveP, GJSieveC, GJSieveW, and GJSievePy version 1.9.0 and IsItPrime version 1.5.6. Within the next week or so, I should be able to write GJSieveC, W, and Py versions 2.0 based on the triple-threaded testing method seen in GJSieve (Proth) version 2.0.
IsItPrime is currently on version 1.7.0 (which can be found on SourceForge).
MuPuPriNT for Mac, meanwhile, is terribly outdated, although multi-threading appears unnecessary at the moment.
In the near future, I will create a separate project for MuPuPriNT on SourceForge as well as subprojects for the various flavors of GJSieve.
The next release of MuPuPriNT will likely still be 1.1, although I will probably append a sub-release number.
The versioning of my applications may seem random and/or like the steps are too large. For instance, IsItPrime went from 1.5.6 to 1.6.0 to 1.7.0 in a matter of two weeks or so. But this makes sense. Major coding changes, coupled with overhauls of the graphical interface and overall changes to the way it actually tests numbers necessitated an increase in sub-version numbers.
Generally speaking, I name things 0.* if they are considered an alpha or testing release, meaning I am not entirely sure they do what I want or everything I want them to do in exactly the way I wish for them to do it.
Versions 1.* are considered stable betas at this point. That means they do everything they're meant to in a stable and efficient manner, although there are definitely still changes and things yet to be implemented.
GJSieve (Proth), where it all began, is on version 2.0 after months of development. It has a rich history of evolution, and I'm proud of the progress I've made even after becoming essentially the sole developer.
More on this later. For now, expect MuPuPriNT to become the focus of NCPrime projects for at least the foreseeable future. After all, what's the point of intensively developing and updating various standalones whilst their implementations in MuPuPriNT lag a version or two behind?
Here's an idea that literally just came to me.
Instead of a main "Chooser" window from which you select an application to run using boring buttons, imagine a window that simply looks like GJSieve 2.0, only with the addition of radio buttons or something to that effect labelled "Proth," "Cullen," "Woodall," "Pythagorean," and "Any number." Obviously "Any number" would be IsItPrime.
The trick is the entry box for k, as that is only used in the Proth number tester.
I suppose I could just have it become disabled upon selecting a test that is not Proth, but that could look a bit ugly. If it was easier (using the Win32 API) to simply hide and show things like edit controls and buttons, I would do it.
I will definitely look into that. MuPuPriNT for Mac will likely be where I'll prototype this unified implementation, so also be on the lookout for that!
Obviously, it is still in testing - but it seems to be working just fine. I was able to implement everything on the to-do list, too!
As you may well notice, there are indeed three testing threads, each of which now has their own message and display window. The boxes up on the top right have been changed around (and one deleted) to make things a bit easier to read and understand.
Perhaps most importantly, the PANIC button has been shrunk (though not deprecated) to make room for the Pause and STOP buttons. The Pause button will pause an in-progress test on all three threads, whilst the STOP button cancels the test outright and returns control to the main thread.
So, scenario time.
The test is running too long, but the application is responding and progress is being made - STOP
The test is running too long, and appears to be hanging and/or not responding - PANIC
You're bored of watching the test and/or need to give the CPU a break - Pause
Additionally, the results files printed by the Save to File command are much more detailed and also better formatted.
Tweeting is new in GJSieve (for Windows anyway), although the implementation is exactly the same as IsItPrime's with the obvious change of tweeting the Proth number.
Tweets will not/cannot show results.
Technically speaking, in order to save a results file and/or post a Tweet from GJSieve 2.0, you need only enter k and n and press Calculate. You needn't have actually tested a number at all. However, the results file will show nothing at all, and I'm likely going to put in a check to make sure you aren't trying to save results for tests that were never performed!
One known issue arises with the "Show Proth Number" button. Currently, it shows a window that is populated upon pressing the "Calculate..." button. This is all well and good, except that you MUST click the button again (when it says "Hide Proth Number") rather than closing the window itself. For some reason, simply destroying the window sends mixed messages and leads to undefined behavior.
I can/will fix that - I'm just not entirely sure how.
I also have to make tooltips for every new thing here...
Additionally, a 64-bit version of GJSieve 2.0 is in the works. The biggest (and perhaps only) noticeable difference will be the absence of the CPU and RAM display bar, as 64-bit Windows API does not support inline assembly code (the _asm intrinsic). Oh well.
experiment with different thread management techniques
The latter implies I use a different way to create the thread such that it is possible to call a function that pauses an active test thread (or, more accurately, all three). I know this is possible, but my ideas have not ever been tested...