Contemplating my final project for my C++ class

[NewsBot]

For my final project, my C++ professor has given me two options. I can either do the fifth programming assignment or propose something of similar or greater difficulty and do that instead (with my professor's approval of course).

 

I could do the fifth programming assignment, but it is boring in comparsion to what I am considering doing. Before I describe what I am considering doing, let me describe how I arrived at the idea:

 

A while back, I wrote a C program that searches for prime numbers of the form 2^n - 1. These are called mersenne numbers. It is very simple. It accepts either a range of exponents or a single exponent and tests their corresponding mersenne numbers for primality. To do this, it makes use of a few theorems from mathematics. The first is that if 2^n - 1 is prime, n is prime. That is to say that if n is not prime, 2^n - 1 is not prime by the law of the contrapositive. Therefore, my program implements an erathosthenes sieve, which finds all of the odd prime numbers between 2 and the largest exponent given to it. It uses a function for this, which returns an array of integers, each integer representing the primality of 32 odd numbers. It also makes use of parallelism. When given a range of exponents to test, it is designed to spawn a preset number of threads and wait for them to execute. It uses mutexes to perform syncronization between these threads. To save memory, a linked list containing the mersenne primes it finds (which are very few in number) is returned to the main function. Testing is done using something called a lucas lehmer test and arbitary precision arithmetic is implemented using the GNU Multi-Precision Library.

 

Improvements that could be made to my C program would involve sorting the list, the automated detection of the number of processors avaliable (which is difficult to do in a cross platform manner) and the use of flat files or some sort of database to store information pertaining to what has been checked so it need not be checked again. To make it into something I could submit as my final project, I would have to rewrite it in C++ and use at least 3 classes (all hand-written, although I believe I am allowed to inherit from existing classes). Class wise, I believe I can make:

 

A PrimeArray class that has a single constructor that takes an integer. The integer will represent its upper bound and it will perform an erathothenes sieve, storing the information in an array of integers with each integer storing information for 32 odd numbers. It will have accessor methods to check the primality of a number, even, odd or unknown, mutator methods to shrink or expand the array and a destructor.

 

A List class. Given that C++ already has a list class, I am not sure if my class will extend it, wrap it, only use it in certain methods (e.g. a sort method) or not use it at all. I know that extending a class that lacks a virtual destructor is bad, as then the subclasses' destructor will not be run, so if I decide to use the existing list class and I want to do something like overload the [] operator without iterating through the entire list using pops and pushes, I will have to write my class as a wrapper.

 

A Thread class to act as a wrapper for the pthreads library. After thinking about this for a while, this would be best implemented using three classes. A base threading class that encapsulates basic thread creation and destruction logic, a threadpool class that uses it (while containing logic to the detect the number of cores avaliable on a given machine) and a sub class that is specialized for the testing of mersenne prime numbers using the logic of its parent class. This would allow my program's interface to run asyncronously with my program's mathematical computations. If I do this, when the threadpool class creates a thread, it will not create a thread using some external function, but a member function and call the external function from inside that member function. The object could be initialized with (or perhaps given) a function pointer to a second external function that would be called by the last thread when it terminates, which I believe would correspond to something professional programmers call event handling. Doing that will allow me to implement a queue for the threads to which I could dynamically add additional exponents for testing as the user requests it and also allow the user to check on the status of tests being done.

 

A data storage/access class, that will act as an interface between my program and where ever I choose to store records of what is prime and what is not so that my program need not perform the same calculations repeatily across sessions. If I use binary/flat files, this will have to be made thread safe.

 

A mersenne class, which will contain a few private variables, a few constructors and a single static member function for primality testing. The actual lucas lehmer test could be made a private member function and the static member function could simply implements theorems that could be used to avoid some lucas lehmer tests, such as the one that states that composite exponents are composite mersenne numbers and another involving sophie germain primes. This will heavily interface with the data storage/access class such that it might be a good idea to inherit from it and perhaps use function overriding, especially since the data storage class will be restricted to storing and retrieving mersenne primes.

 

Since this is C++ and not C, I will also be making use of the GNU Multi-Precision Library's C++ wrapper. If I am feeling particularly bold, I could use all of these classes and make a program that utilizes a graphical interface. Since I want this to be Unix compatible, I would be using GTK+, although I wonder whether or not that would matter considering that using a graphical interface will prevent my program from being run on my university's Unix server. Despite that, I could still take the classes, create a library that encapsulates them and use that library in two separate programs, a commandline program that can run on my university's unix server and a graphical user interface program that can run on Windows.

 

Does anyone have any thoughts?

 

 

More...

 

View All Our Microsoft Related Feeds