Corning Community College
CSCS2330 Discrete Structures
To continue our exploration of algorithms, their implementation, their optimization, their efficiency, and collaboratively authoring and documenting the project and its specifications.
To assist with consistency across all implementations, data files for use with this project are available on lab46 via the grabit tool. Be sure to obtain it and ensure your implementation properly works with the provided data.
lab46:~/src/SEMESTER/DESIG$ grabit DESIG PROJECT
Your task is to implement a program that determines, within provided command-line constraints, the matching N-ary values.
Contributing to project documentation is also a core part of this project. If from reading the existing documentation or through your own exploring, you find something lacking, unclear, or outright missing, that is an opportunity to potentially contribute content.
You want the project documentation to provide you (as if coming in with no awareness of the project) with sufficient information so as to allow you to proceed. Asking questions on the discord is a great way of getting more information that you can use to add content.
Having done the baseline implementation in discrete/cnv0, the aim here is to explore various algorithmic optimizations, and compare processing runtimes against that baseline.
You will want to go here to edit and fill in the various sections of the document:
CNV1 is an introduction to program and algorithm optimization. We will be revisiting our cnv0 program, and we will make it harder, better, faster, and stronger.
There are 5 levels of optimization that could potentially be called upon simultaneously, with some exceptions.
The numbers on the left represent binary positions.
Recall binary numbers and their position values.
0 0 0 0 0 0 0 0 128 64 32 16 8 4 2 1
You may take “optimizations” as a program argument or use an environment variable with getenv.
The optimizations should be a single argument or environment variable, for example the optimization argument of 19 would equal the following optimizations: 16 goes into 19, so approx sqrt would be activated & 2 goes into 19 - 16, so odds would be enabled & finally, 1 goes into 19 - 16 - 2, so the break optimization would be enabled.
* 6n±1: This formula defines all prime numbers above 3. Every prime number follows the 6n±1 equation where n is any integer, 1 or greater. All prime numbers follow this pattern, although the resulting number will not necessarily be a prime number.
For the approximate square root functionality you will have a “square root point”, this point is the approximation of the square root for the number you're checking.
Start with this point equal to 2. The point will increase when ( number to check > point * point ).
For example, when the number to check is 10, the point will be 3 (10 > 3*3), and therefore the approximate square root of 10 is 3.
The starting value of 2 should be used as the approximation for numbers 2-8 however when the number to check reaches 9, (9 > 2*2), so the point will increase to 3.
Examples:
With map, you are pretty much only doing the calculations if the valueToCheck is equal to the value given from the equation 6n(+/-)1, where n is a number > 1. If it is not equal to this, then go to the next value rather than doing the calulations.
With break, you are aiming to reduce the program run time by breaking out of the check when the total factors of the current number exceeds that of the given nary value. This will drastically reduce the time, especially if you are checking larger numbers with a small nary value.
Odds and Map are only to be used during nary 1 (when dealing with prime numbers).
*Our task is to ask questions on Discord or in class and document our findings on this wiki page collaboratively, regarding the functionality of this project.
*For anybody interested in editing the wiki page, here is the dokuwiki user guide: https://www.dokuwiki.org/wiki:syntax#basic_text_formatting -Ash
Program should output the same as cnv0. The only difference is using the optimizations, your optimized version should be for the most part, faster than the cnv0 or zero optimization equivalent of the same operation.
Similar to cnv0, there is no makefile. However, output doesn't change for this program, only the time. To verify, make sure your times when using optimizations are less than the times without optimizations.
To be successful in this project, the following criteria (or their equivalent) must be met:
Let's say you have completed work on the project, and are ready to submit, you would do the following (assuming you have a program called uom0.c):
lab46:~/src/SEMESTER/DESIG/PROJECT$ make submit
You should get some sort of confirmation indicating successful submission if all went according to plan. If not, check for typos and or locational mismatches.
I'll be evaluating the project based on the following criteria:
117:cnv1:final tally of results (117/117) *:cnv1:used grabit to obtain project by the Sunday prior to duedate [13/13] *:cnv1:clean compile, no compiler messages [13/13] *:cnv1:implementation passes verification tests [26/26] *:cnv1:adequate modifications to code from template [26/26] *:cnv1:program operations conform to project specifications [26/26] *:cnv1:code tracked in lab46 semester repo [13/13]