Thursday, August 30, 2012

IsItPrime 1.7.0 Released

I am officially "done" with IsItPrime 1.7.0. At this point, anything else I want to implement will have to be a new version.

You can find the latest version here at any time. Currently, only Windows is supported.

From the readme:

Still to come:
  • Possibly, mutex threads with a central array of factors so it can tell you how many there really are 
  • Upon finding a "prime," re-test the selected range and display remainders so as to be absolutely sure none of them are zero 
  • Hopefully, the ability to pause an in-progress test will be implemented as soon as I figure out exactly how!
This will hopefully not be too difficult to write. It will, however, be a challenge considering I am still completely self-taught in C/C++ and the Windows API.

Additionally, expect a reasonably updated IsItPrime standalone for Mac in the near future - contingent, of course, on a reasonably updated MuPuPriNT for Mac...

IIP Wiki and NCSpiral future

IsItPrime 1.7.0 is going to include exhaustive documentation.

Here is a sample of an article describing all the different testing methods available in this version.

I have decided that SPAT and SPAT-Ex ought to run in verbose mode (why not?)

I also will need to turn my attention towards making a better GUI in the future. I like the design of NCSpiral, for instance.

Speaking of which, NCSpiral really ought to be a web-based applet. That makes more sense, no? I mean, think about it - practically the only reason anyone would write a small single-purpose Java app is for web deployment...

Wednesday, August 29, 2012

Recreational Mathematics, Racing Threads, and an IsItPrime 1.7.0 Progress Report 2

Almost there! I envision releasing IsItPrime 1.7.0 at least by this weekend!

  • BFTD up to n in verbose mode (displays ALL factors)
  • BFTD up to n in non-verbose mode (stops at ONE factor)
  • BFTD up to square root in non-verbose mode (stops at ONE factor)
  • SPAT in non-verbose mode (stops at ONE prime factor)
Still to come:
  • BFTD up to square root in verbose mode (displays more than one factor, but only up to and (possibly) including the square root)
  • SPAT in verbose mode (displays more than one factor, but only the prime factors)
  • SPAT-Ex (larger prime array)
Of the implementations still to come, SPAT in verbose mode makes the most sense - only, it's just for fun. If you are interested in factoring a number, but only wish to display prime factors, then that's the testing method for you!

BFTD up to the square root in verbose mode seems a bit useless, but it isn't. If anything, it will show you a more accurate representation of factors, since it will not display most (or any) quotients of already-found factors. I have already written this, but it's pretty rough and I need to test it.

SPAT-Ex, or Small Prime Array Testing Extended, will use a much larger array of prime numbers, perhaps something like this.  Currently, it stops at 541, which is not an arbitrary number - it's the 100th prime.

An interesting, albeit somewhat unnecessary, way to do that would be to go back to the "arraymaker" code used in GJSieve 1.5.1 (console), which simply creates an array of the numbers 2-99999. That was superseded by the "stupid vector" I talked about awhile ago, which in turn was displaced by a simple loop that increases the trial number without any kind of data structure involved. Much more memory-friendly, that!

The arraymaker implementation could simply be a function that creates an array of the numbers 2-3600 and then tests each of them for primality, and if they are prime, it inserts them into an array and iterates the array up by one. That would create an array of the first 500 primes.

There is really no reason other than recreation, as in "recreational mathematics." :)

I also need to make sure the BFTD threading is working. For up to n in verbose mode, it works great.

Also, BFTD up to the square root in non-verbose mode works fine. Each thread simply checks the length of text in the factor display box after completing a test (unless it's the one writing to the box). If there is text in the box, it knows a factor has been found by another thread and it stops.

So it is essentially a race  - which thread can find a factor first? Exciting! Especially when, you know, it doesn't immediately stop at 3 or something...

Tuesday, August 28, 2012

IsItPrime: BFTD -v / -nv

Or at least, that's what it would look like as a console application. -v and -nv switches (or more likely, just -v) for verbose and non-verbose modes.

Implementing the non-verbose BFTD testing method for trial<n was easy. Copy the existing BFTD implementation that tests only up to the square root and change the parts where it uses the square root.

There are a lot of buttons and switches and check boxes and stuff now, but the general idea is that BFTD has many, many more options available.

So, here is a hypothetical to explain why these options are needed. Assume that your time is important and you'd rather not wait more than you absolutely have to!

You have a number that is kind of large and you'd like to test it. You open IsItPrime and select SPAT. It finds nothing. You select BFTD up to the square root, and it seems to find nothing either. You are still unsure, so you select BFTD up to n in verbose mode, since you really would like to see what is being tested.

Perhaps it finds a factor. Maybe not. Either way, using every testing option available to you is pretty important, especially when considering that no mathematician would take you seriously if you just tested up to the square root by trial division using this silly IsItPrime app you found on SourceForge one day between browsing artistic and eco-friendly desktop environments for your latest obscure Linux distro.

IsItPrime is, like any other "primality tester," much better at finding composites. Numbers you might think are prime sometimes turn out to have a couple factors up in the range of 6-9 digits - who would have thought? And that million-digit number you just calculated? Yeah, it has the factor 3.

IsItPrime really shines in verbose mode, since if you really want to factor a number, you sure can. It still sometimes finds the trial number = candidate number = factor, but that can and will be fixed.

The next big hurdle is rewriting GJSieve, GJSieveW, GJSieveC, and GJSievePy to all use this triple-threaded testing method. Already, their implementations in MuPuPriNT 1.1 all use separate threads for tests, but only one at a time. Considering the numbers being tested usually exceed 100,000 digits...that doesn't really make sense!

Oh and I haven't forgotten about Mac. I'm working on it. Probably today, actually!

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!

IsItPrime 1.7.0 in progress

This morning I took a look at the IsItPrime interface and enlarged it (though I actually deleted things rather than add them). There is now plenty of room for all the necessary changes, as you can see below.

There is also a third thread now - it starts at 4 and tests 7, 13, 16, 19, etc. Now the only number not tested is one.

This comes with some new problems. Now that no numbers are ever missed, you'll sometimes get false-positives. Not that numbers are prime when they are not, but rather that they are "composite" because they were found to be a factor of themselves - surprise surprise! Read the wiki entry here.

Because of some other major code changes, including ensuring that the PANIC button actually kills open threads prior to destroying the window, I have styled this version 1.7.0, despite 1.6.0 being the current version as of yesterday. I changed most of the interface, though anyone who has used an NCPrime application before will hardly feel lost.

Remember that IsItPrime is now a separate project and can be found at its new home on SourceForge, not Google Code.

GJSieve and MuPuPriNT are still in development on an individual basis. MuPuPriNT 1.1 will include IsItPrime 1.5.6 and GJSieveP, C, and W versions 1.9.1.

The next version of MuPuPriNT will include IsItPrime version 1.7.0 (or whatever the current version might be at that time) as well as double- or triple-threaded versions of GJSieve and friends.

More on this futuristic stuff later. For now, have a picture of IsItPrime 1.7.0b:

Sunday, August 26, 2012

Multi-multi-threading - Oops, you missed a spot!

Multi-threading involves having multiple threads in a single process. This means running several tasks in parallel. This is (and has been) the future of computing - at least, since Intel demonstrated that a single processing core can act as two by executing two sets of instructions at once. My old Pentium 4 520 is still kicking, its hyper-threaded core running tests for PrimeGrid.

IsItPrime version 1.6.0, which I just released, uses not one but two separate threads to test its candidate number. It's identical to 1.5.6 (which has not been released yet), meaning they share the same basic code. However, it is quite different on the testing side of things.

IsItPrime 1.6.0 uses three threads to run - one is the "worker thread," responsible for drawing, rendering, and displaying the client window and its controls. The other two are "testing threads," which are only created when the TEST button is pressed.

In the case of brute-force trial division testing, multi-threading really shines because each thread can test a different range of numbers. This has its pros and cons for sure, but at this point I think the benefits seriously outweigh the drawbacks.

The first thing that's apparent is that neither thread is going to find the same exact factors. This is good. They run faster and, since they both calculate quotients, the aggregate factor/quotient display remains the same.

Thread One begins testing at 2, while Thread Two begins testing at 3. They both operate within a loop that exits once one of two conditions is satisfied (I'll get to that). This loop has them increase their trial division number by 3 each time. So, the first few instances of the loop will look like this:

Thread One: 2
Thread Two: 3
Thread One: 5
Thread Two: 6
Thread One: 8
Thread Two: 9

and so on.

The major flaw here becomes evident rather quickly, no? That's right - numbers are skipped.

The solution to this would be to start a third thread and have it test 4, 7, 10, 13, 16, and so on.

This is not a big enough deal to merit a complete re-work of the program...or maybe it is. I wanted to get IsItPrime out there first before re-doing its inner workings entirely!

The loop it uses to test, however, is fine. It takes the candidate number and adds two, creating variables iip and iip+2. When it begins testing, each thread creates an array called factorarray[], and as it finds factors (if any), they are inserted into the array. They also create and initialize a variable called bread (because I used the first thing that came to mind), which is set to the quotient of iip divided by factorarray[0].

The loop will exit upon satisfying one (but never both) of these conditions:
  • the trial number exceeds iip and/or equals iip+2
  • the trial number equals or exceeds bread
The latter option is more likely. That means that the test has reached the beginning and found all possible factors in that range.

On redesigning the interface (again):

The interface already looks like this:

I tout it as "user-friendly." Well, isn't it? It's just a bunch of boxes, a few easily-understood buttons, and two progress bars (one per thread).

Now, imagine there was a third thread. That will ultimately have to happen, yes, but would require these major interface changes:
  • A third big factor display box on the bottom
  • A third progress bar
  • A third message box
  • A third slot in the status bar, which is already strapped for space
Not to mention the several hundred more lines of code that would need to be written. Have you ever designed a window completely from scratch using only Win32 API code? It's not particularly difficult, but it's not exactly simple either, and it's kind of time-consuming to boot.

Creating something in a window (let's say a button) is a 12-argument function; four of those arguments are X, Y, width, and height. Never mind that the client area is not exactly what you tell it to be - this is annoying! To put another box in at the top, for instance, I'd have to move everything down!

That and it's just easier to divide something in half than into thirds.

So - the next version of IsItPrime will be released very soon. It will have three testing threads and will not skip any numbers. 

IsItPrime 1.6.0 and New Site!

Whilst working on MuPuPriNT version 1.1 for Windows, I realized that IsItPrime would probably be better-suited to being a standalone application instead of something that only exists in the multi-tester.

Thus, it joined GJSieve (the original) in having standalone status!

Practically as soon as I had imported the proper files into Visual Studio and set up the project's directories and linker settings correctly, I began working on improving IsItPrime 1.5.6, which as of now remains the version included in MuPuPriNT.

The result, after several days of work and a lot of learning on-the-fly, is IsItPrime 1.6.0. It is powerful and competent, and I am quite proud of it. It is a "beta" release, but it is pretty darn stable. As usual, I would like to hear comments and questions.

I also migrated the project to SourceForge, which I love. Their site is a bit confusing, but also affords developers a TON of control over their projects. It's quite well set up. I just can't quite figure out how to do things like set an avatar or a logo...yet...

You can find IsItPrime's new home here.

Friday, August 24, 2012

NCPrime Mac - Reflections

Long story short: Don't worry - I have not forgotten about the Mac versions of my applications!

Long story long: Years ago, I suddenly became a Mac person when my parents bought me a black MacBook for Christmas in 2006. I loved that computer from the day I got it until I reluctantly sold it for parts in June. But, in the nearly six years I had that computer, I learned nothing about programming, for Mac or otherwise.

I upgraded to a mid-2010 MacBook Pro with maxed specs just a few weeks after I began my first year of college, giving my black MacBook to my younger brother. Despite liking this new laptop even more, I still made no efforts to pursue programming.

In retrospect, I have no idea why. I had styled myself "NullCoding" since the end of 2008, based on some very, very limited experience with VBA (back when Excel supported native VBA, from what I understand). Needless to say, I was disinterested in programming for no good reason.

I only started Mac programming around the end of July 2012. I had been learning C/C++ seriously for about a month before I even started looking at how to do it on a Mac, so once I learned that the Objective-C language used on Mac OS X for native application development is syntactically identical to pure C, I jumped on it. I soon discovered that Obj-C takes many cues from Java and that the XCode IDE is indeed similar in appearance to NetBeans. I drew a hierarchy in my head - Java influenced C#, which is based on C, on which C++ is based, as well as Objective-C. It all started to come together.

It took me less than two days to write a working version of GJSieve 1.7.0 for Mac, most of which was time spent trying to compile the GMP library for multiple platforms from the command line (I figured it out). MuPuPriNT for Mac followed soon after.

I actually started off a little before my GJSieve porting endeavors by giving myself a crash-course in compiling C++ code on Mac. I simply copied over the NCSpiral source from my Windows machine and compiled it using Apple Developer Tools (after I installed them, anyway). It took less than 5 minutes to learn how to use C++ on the Mac - it just works! Whaddaya know?

Since then, however, I have found myself competing against myself!  At the very least, potential application development projects are competing for space in my head and my schedule. I don't have the ability to develop the same application for two different platforms simultaneously. My brain does not work like that. If I finish a major release of, say, GJSieve for Windows, only then can I go to the Mac and implement those same changes.

See, I can't just copy and paste code. In fact, I recognize that to be what my future father-in-law calls "the worst possible thing any programmer can do." So I wrote GJSieve and MuPuPriNT for Mac completely from scratch.

I love Objective-C. Something about it is just quintessentially Apple - straightforward, encapsulated, shiny, fresh, and above all, easy to use. And yet it pleasantly does not give me the impression that "any idiot can write a Cocoa app."

I am so eager to learn, in fact, that I often stare at page after page of official documentation and unofficial tutorials and references trying to find new things to implement. When I found out that OS X Mountain Lion would have full social networking integration, I laughed about it for a bit and then promptly got myself a copy. One flash drive and one hour later, my MacBook Pro was running a sleek and totally up-to-date version of Apple's latest entry into their dubiously feline-themed virtual product line.

I even drove to another state just to buy a shiny new iMac for my father so he too could take advantage of all the exciting new features Apple has given us!

..just kidding, I bought him an iMac because his was going on 7 years old and running Tiger. I also owed him several years' worth of Father's Day gifts...better late than never. Also, come on, the man who consistently forgets how to make folders on his desktop is going to use the Twitter and Facebook integration and iCloud and whatnot? Please. He just needs something that'll last until at least 2018.

I was disappointed with the new (to me) version of XCode, however. Since I was previously running Snow Leopard 10.6.8, I could only use XCode 3.2.6, with which I'd become quite familiar. XCode 4.x had been out for awhile (since the release of Lion last year) but I'd not used it before and consequently had to essentially re-learn everything about how to navigate the IDE.

I figured it out, though, and re-wrote (or at least re-compiled) MuPuPriNT for Mac, deployed to a target OS of 10.8.0. I smugly enjoyed the sense of satisfaction that came from staying ahead of the curve - Mountain Lion had not even been out for three weeks, and my little applications were already compatible!

Not only that, but I soon learned about the NSSharingService class and its method ShareOnTwitter. How easy could it get? I mean really. To share on Windows, I have to do all this, and even then it just takes you to the website! It doesn't post it for you like the Mac does!

At any rate, I am not suspending Mac development, nor will I forgo Windows development because one is easier or harder. I do, however, take into account the fact that the Mac application is actually markedly faster at calculating a massive number. I think this is because of the innately better memory management of Objective-C, which is great considering most applications built in this language are meant for mobile devices. But I don't know. All I know is that it doesn't even appear that the Mac applications need to be multi-threaded! ...yet.

A friend of mine recommended a great cross-platform GUI solution - wxWidgets. This friend is not exactly well-versed in programming in the sense of writing code, but he certainly knows facets of technology and keeps well abreast of the latest and greatest trends (and apparently industry standards as well).

I'd love an easy, cross-platform development solution for my GUI! Just one thing - I'd still have to write two separate groups of code on two different computers in two different IDEs. Given that MuPuPriNT is currently nearly 300 source files and some 7,000 total lines of code (and it's nowhere near done), I think I'll pass and stick to what I know (somewhat) - pure VC++/Win32 API for Windows, and pure Objective C/Cocoa for Mac.

Yes, my Mac apps are native 64-bit. So is any Mac made past 2008. No, my Windows apps are not. They are 32-bit. Not because it's the "Win32" API, but because of the inline assembly code I use. Inline _asm intrinsics do not exist in the 64-bit VC++ environment. I would have to re-do the entire project with specific instructions to use MASM's ML64.exe externally as a custom build step...blah! Not knowing a single word of Assembly, I think I'll pass!

I think that's enough for now. In the near future, I'll be continuing work on MuPuPriNT 1.1 for Windows. Once that is done (give me a week or so with classes starting and all that), I can begin to focus on my Mac apps, specifically IsItPrime and GJSieve, both of which are due for massive overhauls as their standalone versions are currently older and less reliable (and less shiny) than their counterpart implementations in MuPuPriNT for Mac.

MuPuPriNT for Mac, by the way, is technically still on version 0.4a. The Windows version on which I'm currently working is at 1.1b. It will be a lot of work to implement all of the changes - at least the major, important ones - in the Mac app to retain at least some indication that they are, indeed, the same applications on different platforms.

Big ideas...and classes start in just three days. For the record, I don't study computer science...!

IsItPrime 1.5.6 Preview

As I continue working on MuPuPriNT v1.1, I have implemented a lot of changes and new features in IsItPrime. These include:
  • Multi-threading like GJSieve and its counterparts
  • More straightforward interface (that is, you can't press buttons when you aren't meant to, etc)
  • Option to display every factor for that number*
  • Two testing options*
  • Twitter posting**
  • Sound when a factor is found (and/or the test completes successfully)
  • Confirmation box before testing to let you know it could take awhile
I am working on MuPuPriNT at the moment, but once I have finalized a design for IsItPrime within the multi-tester application, I will also make a standalone version of IsItPrime, since I recognize it's probably better-suited to that anyway.

Most of these are ideas that came to me within less than an hour, so I had to divide my time wisely today in order to get them all implemented (at least partially) in a safe and reasonably efficient manner.

I am quite happy with the multi-threading now present in all my Windows applications. Maximum memory usage appears to be below 5MB globally - this is an insane improvement over previous versions, when memory usage would inevitably (and sometimes inexplicably) exceed 500MB...or even 1GB.

It should be noted, however, that all applications within MuPuPriNT, and indeed all NCPrime applications, are CPU-intensive. They will only utilize one core for serious processing, since the thread responsible for displaying the window is backgrounded and barely uses any resources anyway.

I should take a moment to acknowledge the wonderful help and support I received (and always have received) from the experienced professionals over at Dream.In.Code. Without their pointers and expertise (not to mention patience), I'd likely have made about a tenth of the progress I have thus far. I also wouldn't have nearly the same knowledge of C and C-based languages that I do, which would make things a lot harder for me in the long run if I'm going to eventually study computer science!

Here's a peek at the current IsItPrime interface:

* these features are also implemented or in the process of being implemented in GJSieve and its counterparts

** unlike my Mac OS X applications, this is not integrated with the operating system but rather opens the Twitter site with a pre-made tweet you can post instantly with no editing (unless you want to). Tweets from any application within MuPuPriNT for Windows look like this:

Thursday, August 23, 2012

MuPuPriNT 1.1 Progress

I am currently in the process of re-writing MuPuPriNT (for Windows) as version 1.1, based on GJSieve 1.9.0.

Thus far, I have implemented the main chooser window, the Proth window (GJSieve) and the Cullen window (GJSieveC), as well as most of the Woodall window (GJSieveW), although I have yet to write the testing algorithms for the latter.

There are definitely over a hundred source files now. Hard to believe that when we started this project back in March, we had but main.cpp!

I also fixed an odd issue with saving results files that for some reason never reared its head before now. If you consistently get "error - could not create results directory," sorry! It would appear that sometimes, the string terminates before it is a complete path (ie if you have a long username or your Documents folder is uh elsewhere).

I also really need to test GJSieve on other computers - mainly those running Windows 7,  but also XP as I do have several of those lying around anyway.

Once I iron out the kinks in saving (which appears to have been successful) as well as a few other minor fixes, I'll say it's now GJSieve 1.9.1 - that's what MuPuPriNT is saying, anyway.

So here's what I'm working with right now:


1.9.0 Fix

I released the wrong version of GJSieve 1.9.0 - ironically, not the Release configuration, but the Debug configuration.

The URL is the same - find it here. It should now work on any Windows system regardless of whether or not you have the Visual C++ 2010 redistributable installed.

If there are any problems running it, or any compatibility issues at all, please let me know.

Wednesday, August 22, 2012

GJSieve 1.9.0

GJSieve version 1.9.0 is released! Find it here.

I recommend checking out the readme file for information on all the changes and new features in this version, but here is a short synopsis (from the readme):

  • 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.
This is a major step forward. GJSieve has come quite far from where we were in March, with a simple console executable capable of only n < 23 and numbers no longer than 11 or 12 digits!

I have used GJSieve to successfully calculate million-digit numbers. Primality testing takes a good long time, since brute-force trial division is not incredibly efficient, but it definitely works, and I'm incredibly satisfied with the results.

In the near future, expect updates to the Mac version of GJSieve to reflect the changes implemented here. Additionally, MuPuPriNT for Windows is due for an overhaul, as it has essentially not been updated since GJSieve 1.7.0 was prototyped about a month ago!

Expect the multi-tester application to be changed so that all of its included applications are like GJSieve 1.9.0. This will likely involve a complete re-write, so it will take a couple of weeks or so, but I'm definitely going to continue making my applications better and better no matter how long it takes.

Also, I want to expand on what I can do in Java, as that's what is taught here at college and I really don't want to sit in an intro class when I could be dealing with advanced data structures instead. Granted, the fact I can do that stuff (sort of) in C/C++ is all but irrelevant...but I digress.

As always, comments and questions welcome (even if you don't understand how the program works at all!)

Tuesday, August 21, 2012

GJSieve 1.8.* -> 1.9.0

On July 31st, I released GJSieve 1.7.0. This marked a major improvement in both computation and graphical appearance.

1.7.0 was not without its issues, and thus after a few days' rest, I began working hard on GJSieve 1.8.0.

My primary goal was to fix the way results files were printed, as well as adding some additional features. I also wanted to work on overall computation performance in one of two ways:
  • Provide indicators of performance (that is, live metrics) or
  • Actually implement changes that would reduce computation time and stress
Well, it turns out that I actually had to do both of these things.

GJSieve 1.8.0 included performance metrics that measured computation time fairly accurately as well as a prototype function for determining your CPU type and amount of physically installed memory (which on my system appears accurate enough).

GJSieve 1.8.0 was not particularly well-organized, however. I took someone's helpful advice and trimmed the giant, ~2000-line cpp file into a bunch of smaller files, each of which contains a single function - sometimes several.

For example, the window procedure LRESULT CALLBACK WinProcPROTH(...) is now in its own little cpp file. Within that, even, things needed to be trimmed down. The part of the window procedure that gives creation instructions was particularly long because of all the multi-line CreateWindowEx() functions - each of which takes 12 arguments! So, I moved everything under case WM_CREATE to another cpp file. That means that instead of this:

I have this:

I called this re-organized, easier-to-navigate version GJSieve 1.8.5. Version 1.8.0 will never be released, as it was never fully written (that is, I disabled some things and never re-enabled them!).

GJSieve 1.8.5, however, was based on and in fact written on top of the exact same Visual Studio solution I had used for every previous version of the GJSieve GUI. Yuck! 

My solution (don't pardon the pun) was to make a completely new solution and re-import everything from my personal source control, which is a folder in my Code library.

So now everything is fresh and clean and - oh yeah! - multi-threaded.

GJSieve 1.9.0 has the most changes of any version yet, including re-working the number testing into a two-button process.

The Calculate button simply determines the Proth number and prints it. The Test button actually tests it. The major difference is that the Test button runs the (newly optimized) prime-testing algorithm in a separate thread, leaving you free to do things like move the window, resize it, and click menu items and buttons without freezing the program (or simply being unable to).

This means that yes, the Panic! button now has a purpose other than simply quitting when you're done. At least on my system, you are unable to quit with the red X whilst the test is in progress, but the Panic! button will destroy the window and both GJSieve threads instantly. That means that if the test is taking too long, or it actually starts to hang, you can kill it.

GJSieve 1.9.0 is definitely still in testing, but I just thought a progress report was in order!


Saturday, August 18, 2012

NCSpiral 0.4b

I have written a completely configurable generator of Ulam's Spiral using Java Swing. Find it here.

Java is cross-platform, so this ought to work on any computer that can launch a JAR executable. You will find that in the dist folder of the unarchived file.

  • you can set the size of the spiral (it's a square, so you only need to enter one number)
  • set the background color
  • set the dot color
  • it's organized better
Have fun!

Friday, August 17, 2012

Output > Input (Progress)

I titled this post the way I did to reflect on the imbalance between what I create and what I receive.

MuPuPriNT is perhaps what one might call my "flagship" application - it is, after all, the biggest and most feature-rich. It currently allows both Windows and Mac users to test 4 different types of numbers - Proth, Cullen, Woodall, and Pythagorean - as well as any random number of their choosing. The Mac version (which is faster, more modern, and more efficient) even allows you to post to Twitter!

If enough people tell me they wish to be able to test other kinds of potential primes, I will certainly consider implementing other testing applications in the future. As of now, however, MuPuPriNT (and NullCoding projects in general) have received limited feedback and, indeed, equally or more greatly limited attention.

I consistently ask for feedback, even from those not at all interested in number theory. Please remember that these programs are not and likely never will be reputable or irrefutable tests of integer primality.

In fact, the only reason I write these programs at all is due to the way in which I learn. I am a completely self-taught programmer. I am a computer technician and technical consultant by trade, and I study Chinese language, history, and culture at a small liberal-arts college. Although there is certainly overlap between my job and my pursuit of programming, it is not a requirement for me to do my job well and certainly not anything related to my field of study.

But the way I learn is different from the way most people learn. I learn by doing, and I'm simply more motivated to do stuff if it has to do with something I like. Thus, if I wanted to learn a programming language, I would:
  • Gather the basics - IDE, documentation, tutorials, books, and the like
  • Obtain a basic understanding of what the language can do
  • Think of something in which I'm interested
  • Determine if I can write a program, no matter how simple, along those lines
Because of my growing interest in number theory, and my history of participation in PrimeGrid, I decided back around February or March to have my partner help me write a Proth number testing application. GJSieve 0.1 was born.

I became so intent on improving it, adding things here and there, that I sometimes found myself sitting in a lecture class with half my mind on the notes I should have been taking and the rest of my focus on the code I was editing on my laptop! Although my partner wrote most (if not all) of the first version, I added much of the functionality myself, such as file writing and looping.

I also wrote early versions of GJSieveC and GJSieveW myself, as well as the first few (pre-GMP/MPIR) versions of  IsItPrime? by myself, although admittedly their functionality was based directly on implementations used in GJSieve (Proth).

If that was all too involved for you, all you need to know is that I write prime-number testing applications because - if anything - I'm simply inexperienced.

I am an artist - a photographer and musician - so creativity is certainly not the problem. I can definitely think of applications I'd like to write that currently don't exist (that I know of!) - this is not the issue. The issue is that I would not have the slightest clue how to go about actually doing that.

Most programmers are just that - programmers. I am far too many things to make programming the central part of my life, and even if I did want to do that, I simply don't know enough just yet to actually begin developing, testing, building, re-testing, deploying, and supporting a serious application meant for large-scale distribution.

More bulleted lists! My knowledge includes:
  • C
  • C++ / Visual C++
  • Objective-C
  • Win32 API
  • Cocoa
  • limited Java
  • limited C#
  • Using Visual Studio 2010
  • Using XCode 3.x
  • limited knowledge of  Using XCode 4.x 
Most programmers have one or a few languages in which they specialize whilst knowing at least a passable amount of many others - at least to the point where they don't need to consult some kind of reference material every other line of code!

I'm certainly at a point where I can consider myself fairly well-versed in C-based languages, since I do have about a month of teaching myself for at least 6 hours a day, sometimes more. My self-teaching is essentially just writing applications, but it's very involved.

If I need to make something do something, I learn about how that piece of code works, not just how to do it.

For instance, if I need to write to a file, I don't just look for the commands and type them in. Rather, I learn about the FILE* type in C and what fprintf() does, and how to set a filename programatically, and so on - all of which are implemented in GJSieve and MuPuPriNT for Windows.

When I decided to port GJSieve to Mac, I realized Visual C++ would obviously not work and looked into using Objective-C instead. I instantly loved its simplicity and ease-of-use coupled with the fact I didn't have to use some kind of automagic IDE.

Within a few days, I had learned enough to:
  • build and compile a dynamic library from command line
  • link the dylib to my project
  • implement classes and interfaces through objects
  • make buttons and text fields work
  • save everything to a file in a directory the program makes
  • properly allocate memory the whole way through
And thus we have Mac versions of GJSieve and MuPuPriNT.


Throughout this post, I've basically been bragging. Cool. I do that. I prefer to call it "being proud of my accomplishments" or, better yet, "You'd talk about yourself a lot too if you put your mind to something and did it and it worked and you saw your efforts pay off and it made you happy!"

But I recognize that people, in general, will ultimately pay little attention to what my future father-in-law calls "toy programs." He's kind of tactless and a bit too blunt sometimes (oh please, so am I), but he's totally correct - my programs are not impressive on a grand scale, nor do they have any real practical application.

That won't stop me from writing them, though! Hey, I think it's fun! :)

MuPuPriNT Mac 0.4a

I've just started getting used to the new (to me) XCode 4 interface, and have certainly run into my fair share of obstacles already - but I have managed to tweak MuPuPriNT, the Multi-Purpose Prime Number Tester for Mac, so that it will run (very well) on the new OS X 10.8, or Mountain Lion.

Changes include:
  • Sharing - tell your friends what you're testing in MuPuPriNT right from the application!
  • Updated readme file
  • Some memory management tweaks and fixes
  • Addressed an issue in IsItPrime? where pasting in some numbers caused overflow
Read the updated wiki page here and download it here.
 Known issues:

  • Certain combinations of numbers in GJSieve (Proth) will lock up the program - this is true for both the standalone and MuPuPriNT on both Windows and Mac, and I do not have a clue as to why! For now, avoid the following combinations:
    • k = 3 and n = 33
    • k = 3 and n = 332
    • k = 3 and n = 333 
  • IsItPrime? still somewhat limits the length of the number you can test. Strings have a limited size, and I believe the cutoff is in the neighborhood of 30K digits. Numbers longer than a certain length cause overflow, and at the moment I do not see a way around it. Sorry for any inconvenience.
On that last point - it should be noted that if you are for some reason testing a gargantuan number with IsItPrime? then it is probably one which can be represented as a Proth, Cullen, Woodall, or even Pythagorean number. 

As always, have fun!

Thursday, August 16, 2012

NCSpiral (Graphical)

I wrote a Java application yesterday that generates a prime spiral in exactly the same way as the C application NCSpiral, but it draws it graphically on a panel.

Find it here.

It takes a few minutes to work, but it certainly does work.

Here's what it does (spoiler alert):

Pretty, no? ^_^

Wednesday, August 15, 2012

GJS/MPP Mac Compatibility Issues

I was running Snow Leopard (OS 10.6.8) until about an hour ago. I just upgraded to Mountain Lion, which is 10.8.0.

Besides some unfortunate compatibility issues with a few applications, XCode won't quite work (yet), nor will any of the apps I have made.

Thinking back, I believe I set their build target to 10.6 and used Snow Leopard SDK, not Lion+.

I will rectify this as soon as possible, provided it is not too difficult to simply re-build the apps.

Tuesday, August 14, 2012


Thinking about it, I realize that GJSieve needs a lot of improvement but that it's also a dead-end project.

Prime number testing applications have one practical purpose, and the industry standards are well set in place.

I have decided to suspend active development of GJSieve for a short time. I will get back to it, yes, but not for several months.

I would rather pursue other programming ideas of mine as I try and teach myself as many languages as for which I have room in my head.
  • NCSpiral was a great idea and could be improved too. 
  • A graphical version of NCSpiral (think scatter plot)
  • Prime Spiral Java applet!
  • A program that takes input of a number and returns its canonical form
  • something else
I have my work cut out for me in just about everything right now, but NCPrime and other NullCoding programming projects will not suffer.

In fact, I just got Petzold's 5th edition as well as a ton of books about Java and C/C++ etc programming, so there's really nowhere to go but up.

Friday, August 10, 2012

Multitester 0.3a Mac

I've fixed versioning, info boxes (dialogs), and library linking. Find the latest version of the Mac multi-purpose prime number tester here.

As usual, this is a source archive with a release folder.

This is the last major alpha release - if I do change any more, it will be something major and will probably merit a lot of re-writing of code...

Tuesday, August 7, 2012

MuPuPriNT for Mac!

MuPuPriNT, the multi-purpose prime number tester, is now available for Mac.

Find it here and read the Wiki here.

Note that this Mac app is substantially faster and more thread-safe than its Windows counterpart. It has much better memory management simply owing to the fact it's written in Objective-C.

As usual, have fun...

Sunday, August 5, 2012

GJSieve Issues + Future

Currently, GJSieve's documentation is either sparse or out-of-date (or both) as far as current, known issues are concerned.

The Mac version (0.2a), polished though it may be for a relatively quick job, is somewhat flawed in that it returns incorrect results for some small numbers, namely those where the square root happens to be the first factor. This can be easily solved by testing up to sqrt(N) + 1, which I will implement as soon as I have the time, which won't be for a day or two.

The Windows version (1.7.0b), which has had substantially more development, is arguably more flawed and less efficient than the Mac version due to threading and memory management. It also has a lot of trouble printing files.

I finally figured out that the reason it would not print the whole Proth number when it was very big is because I was using the "int" type to determine the length the string ought to be. "int" only goes up to 65535, so if the Proth number had more digits than that, it would get cut off. I have since changed that so the length is determined by an unsigned long int. If you manage to generate a number with more than 2 billion digits, it will break. You'll also likely set some kind of record.

Version 1.8.0b (Windows) is currently in development. I have already solved the file problem by simply using the standard-C output file stream. It also closes the file properly now, so you no longer have to quit the program to open the file.

Version 1.8.0b is also vectorless, which I thought would substantially reduce memory usage and overall computation time. For whatever reason, that doesn't seem to be the case. I am at a loss as to why the Mac application is 3 to 4 times faster, but I'm not complaining. Windows users might, however, so I'm definitely looking into that.

It's worth noting that with the school year starting for me in about two weeks, sustaining active development will become more difficult, as I'll no longer be able to spend all day every day programming. This doesn't mean I'm going to stop, only that releases will be more spaced out.

I am also planning on porting the multitester (MuPuPriNT) to Mac. This should not be too hard, since it basically involves copying and pasting GJSieve three times, porting the comparatively small IsItPrime?, and writing a simple host application window to tie it all together. That said, I don't plan on being done with that for at least a week, possibly longer.

I will be on vacation the next two weeks in historic Newtown Square, Pennsylvania, where my parents and siblings live. I can work there, but likely won't as much as I do here at college. I'll still post updates, though.

Friday, August 3, 2012

Stupid Vectors

GJSieve for Windows uses a vector to determine a trial division number. It's set up like this:

Whereas with the Mac version, it looks like this:

And guess what? It does the same thing.

Now, this may be the reason GJSieve for Windows is a bit more limited in what it can do. Vectors are luckily thread-safe and not a memory leak, but a vector of the maximum size possible? That can't be too kind to the program.

I'm going to re-write GJSieve for Windows to use this vector-less approach, which simply makes more sense in both an implementation and practical sense.

I have to say though, Objective-C is really wonderful in memory management and whatnot. Even if there was a leak, it would probably tell me how to patch it up.

So, expect a new version of GJSieve for Windows in the near-ish future. If it works well (or, preferably, better), the vector-less approach will be implemented in MuPuPriNT as well.

Speaking of the multi-tester, expect a Mac version of that sometime soon-ish as well!

gjsieveOSX v0.2a

A matter of hours later, I have gotten GJSieveOSX (gjsieve for Mac) to be fully functional.

You can find it here. It's in the Release folder after unzipping.

Be sure to check the readme, which you can now do from the program itself. And if you're going to move the Release folder, move the whole thing with the readme, or else that button won't work anymore.

You can safely delete the source folder in its entirety if you don't want it.

  • Full saving functionality (to a folder it makes in Documents)
  • Instructions box has real text
  • ReadMe button opens the ReadMe
  • Logo :)
  • Better limit checking
Please don't put in a value of n greater than ten million. It really doesn't like that.

Feedback welcome as always...

gjsieveOSX v0.1a

I spent most, if not all, of yesterday working on a version of gjsieve for Mac OS X. It was not easy, but then again it was luckily not too difficult.

You can find a wiki about it here and download it here.

Please don't be alarmed that it is a ZIP file. This is targeted towards Mac, where in order to decompress RARs, you need additional software. Some people think viruses and trojans are distributed via ZIP files, but that's just because they're easy to make.

If Sophos doesn't like my program, tell me. I'll give them a call.

Also, please remember this is a super-duper early alpha. Like, before dawn early. As in before my dad gets up. That early of an alpha. So please, read the wiki I linked to above if you want to know what's wrong with (or more accurately, not yet implemented in) this program.

As always, questions or comments welcome via e-mail or something.

Thursday, August 2, 2012

[Objective-C beginLearning];

Contrary to whatever I ranted about here, I have in fact decided that it is in my best interest to learn Objective-C.

Objective-C (ObjC) is a language used almost exclusively by Apple for OSX and iOS application development, namely using the Cocoa framework. In relative terms:

ObjC:Apple :: VC++:Microsoft ; Cocoa:OSX :: WinAPI:Windows

The obvious advantage here is that both ObjC and VC++ are derived directly from C.

Imagine that you know and understand Latin. You want to learn both English and Spanish. You know going in that this is not a huge deal, because both come directly from Latin. You also know that English is a lot more complicated than Spanish - Spanish has things like endings, gender, conjugations, and declensions just like Latin does, whereas English boasts none of these amenities.

Now replace "Latin" with "C." You know C. You probably also know C++. You can learn VC++ (let's say it's like Spanish) with relative ease. The syntax is about the same, but the vocabulary is different and also more expansive. Objective-C, then, is English: a very complicated but extremely useful language that takes a long time to learn and even longer to master.

A Chinese guy learning English will struggle with it for some time because it's so radically different from his native tongue. However, after several months of disciplined study, he can probably hold a basic but fully-coherent conversation with a native English speaker.

Similarly, learning Objective-C seems like something where I'll be able to soon write a simple program like GJSieve, but will have next to no idea about the intricacies and complexities of the language and will therefore be unable to take advantage of all the language has to offer.

People say that Macs are simplistic, and after only a day of learning the language behind Mac programs, I have to say they're wrong.

It seems to be a widely-held opinion amongst professional programmers that "Objective-C is needlessly complex" - but those people will tell you in the same breath that this, more often than not, means there is only one way to do things. This means that if you write this:

@interface doStuff : NSObject {

IBOutlet NSTextView *TextPlace

@property(nonatomic,retain) IBOutlet id TextPlace

- (IBAction)doThatThing:(id)sender;


then there is only really one way to properly implement it:

@implementation doStuff
@synthesize TextPlace;

- (IBAction)doThatThing:(id)sender
NSTextStorage *TextStorage = [TextPlace textStorage];
NSString* String = [NSString stringWithFormat: @"It did stuff."];
[TextStorage beginEditing]
[TextStorage appendString:String];
[TextStorage endEditing];

You should note that this example wouldn't really work. I mean, it might, but then again it might need a few minor changes...

The point is, Objective-C thrives on interface and implementation. Much like the Windows API, there are 3 steps to getting things to do stuff in Cocoa:
  1. define the way the thing is supposed to behave
  2. define how the thing does stuff when it behaves
  3. link the thing to a button or some other control that tells it to start doing stuff
The "thing," of course, is a class (or "object.")

I had never noticed how convenient these are. It's fantastic, actually. I make a separate file for each button, and while that takes up space, it also means no more hunting around one giant file!

You want a button that displays a window? Okay cool.
  1. Make a window in the Interface Builder (compare to Windows' Resource Editor)
  2. Make a button in the main window, also in IB
  3. Make an ObjC class that's a subclass of NSObject
  4. Tell that class the window and the button you made are "outlets"
  5. Tell that class to show the window when the action message is received
  6. In IB, link the action message and outlet pointer to the button and the other outlet to the window
  7. go
Obviously steps 3-5 take a bit more work, but I'm not ready to share my code yet. I mean, there's not much to share!

So, I'll leave you with this to showcase my (limited) achievements in Objective-C thus far (click for full view):

Wednesday, August 1, 2012

NCSpiral Mac

I made a version of NCSpiral for Mac. Find it here.

For more about the program, see here.

A few notes:
  • You need XCode to edit the code in its existing project form. If you code on Mac, you probably have this anyway. If not, I kind of wonder how you get along without developer tools. 
  • To view the resulting file, I'd recommend opening the text file with a web browser. That way, the spacing stays the same but you have the ability to zoom out to see the full effect!