A few months ago I saw Numberphile's videos on Wilson's Theorem. This was such an event. Wilson's theorem basically states that you can determine if a number is prime by seeing if the factorial of one less than the suspected prime, plus one, is divisible by the suspected prime. The formula would look like: ((n-1)! + 1) % n = 0.
To give a simple example: n = 3.
3 - 1 = 2.
2! = 2.
2 + 1 = 3.
3 % 3 = 0.
x! is a way of writing "factorial of x". Factorial means to multiply up all the numbers prior to and including the number in question. 2! = 1 x 2. 3! = 1 x 2 x 3.
% is modulo, which means to find the remainder of. The extrapolation of this would be 3 / 3 = 1, so 0 remainder. 7 % 3 = 1. (3 goes into 7 twice, leaving a remainder of 1.)
Here's Numberphile's Videos on Wilson's Theorem:
I scribbled down the rearranged formula for Wilson's Theorem on a piece of paper when I saw the video. Then the next day I wrote up some pseudocode to give a general outline of the logic needed to process the formula. Then I put it on a shelf and left it, for months.
I came back to the piece of paper a few days ago and decided it sounded like something to look into since I would be programming again shortly (see Arduino Binary Clock projects, serial internal oscillator one finished, standalone upcoming at time of writing this). After a few hours of writing up the basics of the program in C++ (my preferred computer language) with VisualStudio2013 (my very much NOT preferred IDE) it became painfully apparent things weren't working well. Why was this? Well, Wilson's Theorem uses incredibly large numbers because of the factorial function. By incredibly large numbers I mean that simply doing 22!, which is needed to test if 23 is prime (it is) exceeds the intrinsic capacity of a 64bit computer. I realized that I would need a method of working with such large numbers, a guestimation of which is 2^2048, on a 64bit machine.
Lots and lots of searching, asking friends, and plugging away yielded that there are special libraries for this exact purpose. Mostly they're used in cryptography for encryption and data hashing. I found several libraries that looked like they would work, but only one of them had a downloadable file that was recognized by my Windows 8.1 system; BigInteger. Many more hours of tinkering and searching around I find that it is not precompiled and needs to be directly added to your project and compiled with it or compiled in your IDE or on a Unix computer for use. VisualStudio2013 was not letting me just add the files and then compile with my project, so thus began the hunt for a better IDE.
I asked my friends and asked online on one of the technology forums I am a veteran of. I settled on Orwell's Dev-C++ as it looked to be a good fit from both my own investigation and external recommendations. I had also tried out Code::Blocks and CodeLite, but they didn't seem as intuitive or pliant to my needs. A few more hours of getting myself accustomed to the new IDE and some exceptional pointers from my professional programmer buddy Jack and I was up and running.
Here's the grand result: Two executables for windows machines which use Wilson's Theorem.
1) Wilson's Theorem Primality Checker - this lets you enter a number up to 2,147,483,646 ((2^32)-1) [not recommended doing so though, haha] and it will tell you if what you entered is a prime number or not.
2) Wilson's Theorem++ - this lets you enter a number up to 2147483646 ((2^32)-1) and it will list off every prime between 1 and that number as it finds them.
I'd stick to values below 20,000 unless you want to leave your pc running a long time as values over 5000 take a bit to process. You'll be happy to know you can just "X" out of the command window if you're tired of waiting for it though. It also only uses a single core of your processor, so it shouldn't crash any modern multi-core system.
Download Links:
No comments:
Post a Comment