This shows you the differences between two versions of the page.
Both sides previous revisionPrevious revisionNext revision | Previous revisionLast revisionBoth sides next revision | ||
playground:playground [2019/01/22 19:54] – jwilli57 | playground:playground [2023/09/12 19:29] – [Objective] rford5 | ||
---|---|---|---|
Line 1: | Line 1: | ||
- | ====== | + | discrete fall2022 eoce 0x3 |
+ | ======================== | ||
+ | |||
+ | =====Objective===== | ||
+ | To explore | ||
+ | only ONE loop to drive central processing. | ||
+ | |||
+ | |||
+ | |||
+ | <WRAP center round box 60%> | ||
+ | messing with this | ||
+ | </ | ||
+ | |||
+ | < | ||
+ | |||
+ | =====Background===== | ||
+ | In mathematics, | ||
+ | divisible | ||
+ | no others. | ||
+ | **composite** numbers. | ||
+ | |||
+ | The number **6** is a **composite** number, as in addition to 1 and 6, it | ||
+ | also has the factors of 2 and 3. | ||
+ | |||
+ | The number | ||
+ | than 1 and 17 can be evenly divided into it. | ||
+ | |||
+ | =====Calculating the primality of a number===== | ||
+ | As of yet, there is no quick and direct way of determining the primality | ||
+ | of a given number. | ||
+ | determine if it fails primality (typically by proving it is composite). | ||
+ | |||
+ | This process incurs | ||
+ | task, so much so that increasingly | ||
+ | amounts of time. Often, approaches | ||
+ | various algorithms, which offer various benefits (less time) and drawback | ||
+ | (more complex code). | ||
+ | |||
+ | Your task for this project is to implement a prime number program using | ||
+ | the straightforward, | ||
+ | the primality of a number in a "trial by division" | ||
+ | |||
+ | =====Main algorithm: brute force===== | ||
+ | The brute force approach is the simplest to implement | ||
+ | cost in the form of time). | ||
+ | |||
+ | As we will be looking | ||
+ | comparisons, | ||
+ | it. | ||
+ | |||
+ | To perform the process of computing | ||
+ | attempt to evenly divide | ||
+ | number in question. If any one of them divides | ||
+ | **NOT** prime, but instead composite. | ||
+ | |||
+ | Checking | ||
+ | division was clean (having 0 remainder indicates such a state). | ||
+ | |||
+ | For example, the number 11: | ||
+ | |||
+ | < | ||
+ | 11 % 2 = 1 (2 is not a factor of 11) | ||
+ | 11 % 3 = 2 (3 is not a factor of 11) | ||
+ | 11 % 4 = 3 (4 is not a factor of 11) | ||
+ | 11 % 5 = 1 (5 is not a factor of 11) | ||
+ | 11 % 6 = 5 (6 is not a factor of 11) | ||
+ | 11 % 7 = 4 (7 is not a factor of 11) | ||
+ | 11 % 8 = 3 (8 is not a factor of 11) | ||
+ | 11 % 9 = 2 (9 is not a factor of 11) | ||
+ | 11 % 10 = 1 (10 is not a factor of 11) | ||
+ | </ | ||
+ | |||
+ | Because none of the values | ||
+ | passed the test: **11 is a prime number** | ||
+ | |||
+ | On the other hand, take 119: | ||
+ | |||
+ | < | ||
+ | 119 % 2 = 1 (2 is not a factor of 119) | ||
+ | 119 % 3 = 2 (3 is not a factor of 119) | ||
+ | 119 % 4 = 3 (4 is not a factor of 119) | ||
+ | 119 % 5 = 4 (5 is not a factor of 119) | ||
+ | 119 % 6 = 5 (6 is not a factor of 119) | ||
+ | 119 % 7 = 0 (7 is a factor of 119) | ||
+ | 119 % 8 = 7 | ||
+ | 119 % 9 = 2 | ||
+ | 119 % 10 = 9 | ||
+ | 119 % 11 = 9 | ||
+ | 119 % 12 = 11 | ||
+ | 119 % 13 = 2 | ||
+ | ... | ||
+ | </ | ||
+ | |||
+ | Because, during our range of testing every value from 2-118, we find that | ||
+ | 7 evenly divides into 119, it failed | ||
+ | is instead a composite number. | ||
+ | |||
+ | Please NOTE: Even once a number | ||
+ | MUST **CONTINUE** evaluating the remainder of the values (up to 119-1, or | ||
+ | 118). It might seem pointless (and it is for a production program), but I | ||
+ | want you to see the performance implications this creates. | ||
+ | |||
+ | ====algorithm==== | ||
+ | Some things to keep in mind on your implementation: | ||
+ | |||
+ | * you will want to have exactly ONE loop in the central processing for | ||
+ | this program. | ||
+ | |||
+ | * you will need to flatten | ||
+ | in the nested loop | ||
+ | |||
+ | * be mindful of what the underlying conditions are | ||
+ | |||
+ | * you know the starting | ||
+ | have a clear starting and ending point to work with. | ||
+ | |||
+ | * I do **NOT** want to see ambiguous, one-letter variables used in your | ||
+ | implementation(s). Please use // | ||
+ | |||
+ | * Some good examples of variable names would be: | ||
+ | |||
+ | * **number**: the number being tested | ||
+ | |||
+ | * **factor**: the value being divided | ||
+ | primality | ||
+ | |||
+ | * **step**: the rate by which some variable is changing | ||
+ | |||
+ | * **qty**: the count of the current tally of primes | ||
+ | |||
+ | * **max**: the maximum count we seek | ||
+ | |||
+ | * **start**: a value we are starting at | ||
+ | |||
+ | * **lower**: a lower bound | ||
+ | |||
+ | * **upper**: an upper bound | ||
+ | |||
+ | * see how much more readable and meaningful | ||
+ | as compared | ||
+ | helps with debugging and understanding your code better. | ||
+ | |||
+ | * let the loop drive the overall | ||
+ | status separate from loop terminating conditions. | ||
+ | |||
+ | * and remember, | ||
+ | a value as composite, but won't terminate the loop. | ||
+ | |||
+ | * your timing | ||
+ | processing), | ||
+ | output newline outside the loops. | ||
+ | |||
+ | * you may **NOT** split **qty** and **range** functionality | ||
+ | separate | ||
+ | set as indicated. | ||
+ | |||
+ | =====prime algorithm optimizations===== | ||
+ | To give us a decent | ||
+ | development | ||
+ | optimizations that we will be implementing. | ||
+ | |||
+ | The optimizations we will be implementing in this section include: | ||
+ | |||
+ | * **break | ||
+ | composite, there is no need to continue processing: break out of the | ||
+ | factor check logic and proceed to the next number | ||
+ | |||
+ | * **mapping factors of 6** - it turns out that, aside from the initial | ||
+ | primes of **2** and **3**, that **all** prime numbers fall to a +1 or | ||
+ | -1 off a factor of six (there is an algorithm for this: **6a+/ | ||
+ | This optimization | ||
+ | +/-1 off of factors of 6 (how might this impact overall processing? | ||
+ | |||
+ | * **odds-only | ||
+ | numbers are odd. Therefore, there is zero need to perform a composite | ||
+ | check on an even number, allowing | ||
+ | values (luckily, they seem to occur in a predictable pattern). | ||
+ | |||
+ | * **sqrt() trick** - mathematically it has been shown that if a number | ||
+ | has any evenly divisible factors, at least one half of that factor | ||
+ | pair will occur by the square root point of the number being tested. | ||
+ | |||
+ | * **sqrt()-less square | ||
+ | in the math library, | ||
+ | calculation. | ||
+ | corresponding to the approximate square | ||
+ | our own logic | ||
+ | considerable performance impact. | ||
+ | |||
+ | Unless | ||
+ | implement the algorithm and optimization(s) specified. | ||
+ | |||
+ | Some of these optimizations can co-exist easily | ||
+ | sqrt()), | ||
+ | a certain | ||
+ | approximated | ||
+ | combinations that are possible using this scheme. | ||
+ | |||
+ | ====Program Specifications==== | ||
+ | Your program should otherwise work like the discrete/ | ||
+ | |||
+ | * obtain | ||
+ | arguments** section below). | ||
+ | |||
+ | * check to make sure the user indeed supplied enough parameters, and | ||
+ | exit with an error message if not. | ||
+ | |||
+ | * argv[1]: maximum | ||
+ | should run until it discovers **that** many primes). | ||
+ | |||
+ | * this value should be an integer value, greater than or equal to 0 | ||
+ | |||
+ | * if argv[1] is 0, disable the quantity check, and rely only on | ||
+ | provided lower and upper bounds (thru argv[4] would be required | ||
+ | in this case). | ||
+ | |||
+ | * argv[2]: N-ary specification; | ||
+ | **1** | ||
+ | |||
+ | * argv[3]: | ||
+ | Most of the time, this will probably be **2**, but should be a | ||
+ | positive integer greater than or equal to 2. This defines where the | ||
+ | program will start its prime quantity check from. | ||
+ | |||
+ | * if omitted, assume a lower bound of **2**. | ||
+ | |||
+ | * if you desire | ||
+ | MUST provide the lower bound argument under this scheme. | ||
+ | |||
+ | * argv[4]: **conditionally optional** | ||
+ | provided, this is the ending value you'd like to check to. | ||
+ | |||
+ | * If doing a quantity run (argv[1] is NOT 0), you don't need this. | ||
+ | |||
+ | * If doing a quantity run AND you specify an upper bound, whichever | ||
+ | condition is achieved first dictates program | ||
+ | is, upper bound could override quantity (if it is achieved before | ||
+ | quantity), and quantity can override | ||
+ | achieved before reaching the specified upper bound). | ||
+ | |||
+ | * argv[5]: specification of optimizations. Like in discrete/ | ||
+ | values are bitwise-specified in a single numeric value, | ||
+ | as follows: | ||
+ | |||
+ | 0 - no optimizations (naive, brute force approach) | ||
+ | 1 - break on composite | ||
+ | 2 - odds-only checking | ||
+ | 4 - map | ||
+ | 8 - sqrt | ||
+ | 16 - approximate square root | ||
+ | |||
+ | * for each argument: | ||
+ | complied | ||
+ | message (displayed to STDERR) otherwise: | ||
+ | |||
+ | * for insufficient quantity | ||
+ | insufficient number of arguments!** | ||
+ | |||
+ | * for invalid argv[1], display: **PROGRAM_NAME: | ||
+ | |||
+ | * for invalid argv[2], display: **PROGRAM_NAME: | ||
+ | |||
+ | * invalid | ||
+ | |||
+ | * if argv[3] is not needed, ignore (no error displayed not forced | ||
+ | exit, as it is acceptable defined behavior). | ||
+ | |||
+ | * invalid | ||
+ | |||
+ | * if argv[4] is not needed, ignore (no error displayed nor forced | ||
+ | exit, as it is acceptable defined behavior). | ||
+ | |||
+ | * In these error messages, **PROGRAM_NAME** | ||
+ | program being run; this can be accessed as a string stored in | ||
+ | **argv[0]**. | ||
+ | |||
+ | * perform | ||
+ | We are producing | ||
+ | comparison. | ||
+ | |||
+ | * please take note on differences in run-time, contemplating the impact | ||
+ | the algorithm | ||
+ | specifically). | ||
+ | |||
+ | * immediately | ||
+ | **timing** section below). | ||
+ | |||
+ | * perform | ||
+ | command-line input(s) given. | ||
+ | |||
+ | * your program is to have no fewer and no more than 1 loop in this | ||
+ | prime processing section. | ||
+ | |||
+ | * display identified primes (space-separated) | ||
+ | **stdout** | ||
+ | |||
+ | * stop your stopwatch immediately following your prime processing loops | ||
+ | (and terminating newline display to **stdout**). Calculate | ||
+ | that has transpired (ending time minus starting time). | ||
+ | |||
+ | * output the processing run-time to the file pointer called **stderr** | ||
+ | |||
+ | * your output | ||
+ | **execution** section below. This is also a test to see how well you | ||
+ | can implement to specifications. Basically: | ||
+ | |||
+ | * as primes are being displayed, they are space-separated | ||
+ | prime hugs the left margin), and when all said and done, a newline | ||
+ | is issued. | ||
+ | |||
+ | ====Coding Restrictions==== | ||
+ | Since a lot of our explorations this semester were algorithmic in nature, | ||
+ | we made a lot of use of restricting various approaches | ||
+ | the implementation of our solutions. | ||
+ | |||
+ | As | ||
+ | implementations: | ||
+ | |||
+ | * no global variables | ||
+ | * no infinite loops | ||
+ | * no if() shunts (have good conditions!) | ||
+ | * what is the difference | ||
+ | conditional | ||
+ | iterations; | ||
+ | processing that occurs every iteration. | ||
+ | * one return statement (max) per function | ||
+ | * exit() calls are limited to command-line or resource allocation error | ||
+ | processing | ||
+ | * avoid redundant sections of code (merge logic or break out functions) | ||
+ | |||
+ | Remember, the focus should be on writing elegant code, and NOT on brute | ||
+ | forcing | ||
+ | semester- write clean, well commented, consistently indented code. | ||
+ | |||
+ | =====Makefile operations===== | ||
+ | Makefiles provide a build automation system for our programs, instructing | ||
+ | the computer | ||
+ | type compiler | ||
+ | other useful, | ||
+ | administration of the project. | ||
+ | |||
+ | Basic operation | ||
+ | " | ||
+ | project directory. | ||
+ | |||
+ | A description of some available commands include: | ||
+ | |||
+ | * **make**: compile everything | ||
+ | |||
+ | * any **warnings** or **errors** | ||
+ | into a file in the base directory of pnc0 in a file called | ||
+ | **errors**; you can **cat** it to view the information. | ||
+ | |||
+ | * **make debug**: compile everything with debug support | ||
+ | |||
+ | * any **warnings** or **errors** | ||
+ | displayed to the screen as the programs compile. | ||
+ | |||
+ | * **make clean**: remove all binaries | ||
+ | |||
+ | * **make save**: make a backup of your current work | ||
+ | |||
+ | =====Command-Line Arguments===== | ||
+ | To automate our comparisons, | ||
+ | arguments in our programs. | ||
+ | |||
+ | ====header files==== | ||
+ | We don't need any extra header files to use command-line arguments, but | ||
+ | we will need an additional header file to use the **atoi(3)** function, | ||
+ | which we'll use to quickly | ||
+ | integer, and that header file is **stdlib.h**, | ||
+ | with the others: | ||
+ | |||
+ | <code c> | ||
+ | #include < | ||
+ | #include < | ||
+ | </ | ||
+ | |||
+ | ====setting up main()==== | ||
+ | To accept (or rather, to gain access) to arguments given to your program | ||
+ | at runtime, | ||
+ | While the names don't matter, | ||
+ | **argc** | ||
+ | abbreviated as **ac** and **av**. | ||
+ | |||
+ | Please declare your main() function as follows: | ||
+ | |||
+ | <code c> | ||
+ | int main (int argc, char **argv) | ||
+ | </ | ||
+ | |||
+ | There are two very important | ||
+ | actually | ||
+ | actually quite, variable; | ||
+ | things like " | ||
+ | |||
+ | * int argc: the count (an integer) | ||
+ | (program name + arguments) | ||
+ | |||
+ | * < | ||
+ | array of an array of char) that contains " | ||
+ | tokens provided on the command-line. | ||
+ | |||
+ | The arguments are accessible via the argv array, in the order they were | ||
+ | specified: | ||
+ | |||
+ | * argv[0]: program invocation (path + program name) | ||
+ | * argv[1]: our maximum / upper bound | ||
+ | * argv[2]: should be provided as a 1 for this project | ||
+ | * argv[3]: conditionally optional; represents lower bound | ||
+ | * argv[4]: conditionally optional; represents upper bound | ||
+ | * argv[5]: conditionally optional; represents optimizations, | ||
+ | |||
+ | Additionally, | ||
+ | contains a count of arguments (argc == argument count). If we provided | ||
+ | argv[0] through argv[4], argc would contain a 5. | ||
+ | |||
+ | ===example=== | ||
+ | For example, if we were to execute the as follows: | ||
+ | |||
+ | < | ||
+ | lab46: | ||
+ | </ | ||
+ | |||
+ | We'd have: | ||
+ | |||
+ | * < | ||
+ | * < | ||
+ | * < | ||
+ | * < | ||
+ | * < | ||
+ | * < | ||
+ | |||
+ | and let's not forget: | ||
+ | |||
+ | * argc: 6 | ||
+ | |||
+ | With the conditionally optional arguments | ||
+ | for a valid execution of the program, argc could be a value anywhere from | ||
+ | 3 to 6. | ||
+ | |||
+ | ====Simple argument checks==== | ||
+ | While there are a number of checks | ||
+ | should be a check to see if the minimal number | ||
+ | provided: | ||
+ | |||
+ | <code c> | ||
+ | |||
+ | // if less than 3 arguments (program_name + quantity + argv[2] == 3) | ||
+ | // have been provided | ||
+ | // | ||
+ | if (argc < 3) | ||
+ | { | ||
+ | fprintf(stderr, | ||
+ | exit(1); | ||
+ | } | ||
+ | </ | ||
+ | |||
+ | Since argv[3] (lower | ||
+ | optional, it wouldn' | ||
+ | But we can and do still want to stategically utilize | ||
+ | determine if an argv[3] or argv[4] is present. | ||
+ | |||
+ | ====Grab and convert max==== | ||
+ | Finally, we need to put the argument representing the maximum quantity | ||
+ | into a variable. | ||
+ | |||
+ | I'd recommend declaring a variable of type **int**. | ||
+ | |||
+ | We will use the **atoi(3)** | ||
+ | arguments into **int** values: | ||
+ | |||
+ | <code c> | ||
+ | max = atoi (argv[1]); | ||
+ | </ | ||
+ | |||
+ | And now we can proceed with the rest of our prime implementation. | ||
+ | |||
+ | =====Timing===== | ||
+ | Often times, | ||
+ | measurement | ||
+ | processing takes. | ||
+ | |||
+ | In order to do that in our prime number programs, we are going to use C | ||
+ | library | ||
+ | stopwatch: we'll grab the time just before starting processing, and then | ||
+ | once more when done. The total time will then be the difference between | ||
+ | the two (end_time - start_time). | ||
+ | |||
+ | We are going to use the **gettimeofday(2)** function to aid us in this, | ||
+ | and to use it, we'll need to do the following: | ||
+ | |||
+ | ====header file==== | ||
+ | In order to use the **gettimeofday(2)** function in our program, we' | ||
+ | need to include the **sys/ | ||
+ | with the existing ones: | ||
+ | |||
+ | <code c> | ||
+ | #include < | ||
+ | #include < | ||
+ | #include < | ||
+ | </ | ||
+ | |||
+ | ====timeval variables==== | ||
+ | **gettimeofday(2)** uses a **struct timeval** data type, of which we' | ||
+ | need to declare | ||
+ | starting time, and the other for the ending time). | ||
+ | |||
+ | Please declare these with your other variables, up at the top of main() | ||
+ | (but still WITHIN main()-- you do not need to declare global variables). | ||
+ | |||
+ | <code c> | ||
+ | struct timeval time_start; // starting time | ||
+ | struct timeval time_end; | ||
+ | </ | ||
+ | |||
+ | ====Obtaining the time==== | ||
+ | To use **gettimeofday(2)**, | ||
+ | we wish to take the time. | ||
+ | |||
+ | For our prime number | ||
+ | **AFTER** you' | ||
+ | BEFORE** starting the driving loop doing the processing. | ||
+ | |||
+ | That call will look something like this: | ||
+ | |||
+ | <code c> | ||
+ | gettimeofday(& | ||
+ | </ | ||
+ | |||
+ | The ending | ||
+ | prime number output) is completed, and right before we display the timing | ||
+ | information to STDERR: | ||
+ | |||
+ | <code c> | ||
+ | gettimeofday(& | ||
+ | </ | ||
+ | |||
+ | ====Displaying the runtime==== | ||
+ | Once we have the starting and ending | ||
+ | **stderr** file pointer. You'll want this line: | ||
+ | |||
+ | <code c> | ||
+ | fprintf(stderr, | ||
+ | time_end.tv_sec-time_start.tv_sec+((time_end.tv_usec-time_start.tv_usec)/ | ||
+ | </ | ||
+ | |||
+ | For clarity | ||
+ | " | ||
+ | ' | ||
+ | |||
+ | And with that, we can compute | ||
+ | The timing won't necessarily be accurate down to that level of precision, | ||
+ | but it will be informative enough for our purposes. | ||
+ | |||
+ | =====Execution===== | ||
+ | |||
+ | ====specified quantity==== | ||
+ | Your program output should be as follows (given the specified quantity): | ||
+ | |||
+ | < | ||
+ | lab46: | ||
+ | 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 | ||
+ | 0.0001 | ||
+ | lab46: | ||
+ | </ | ||
+ | |||
+ | The execution of the programs is short and simple- | ||
+ | do the processing, produce the output, and then terminate. | ||
+ | |||
+ | ====invalid lower bound==== | ||
+ | Here's an example that should generate | ||
+ | project specifications): | ||
+ | |||
+ | < | ||
+ | lab46: | ||
+ | ./cnv3: invalid lower bound | ||
+ | lab46: | ||
+ | </ | ||
+ | |||
+ | In this case, the program logic should have detected an invalid condition | ||
+ | and bailed | ||
+ | displayed, because exiting should occur even prior to that. | ||
+ | |||
+ | ====upper bound overriding quantity==== | ||
+ | As indicated above, there is potential interplay with an active quantity | ||
+ | and upper bound values. Here is an example where upper bound overrides | ||
+ | quantity, resulting in an early termination (ie upper bound is hit before | ||
+ | quantity): | ||
+ | |||
+ | < | ||
+ | lab46: | ||
+ | 7 11 13 17 19 23 | ||
+ | 0.0001 | ||
+ | lab46: | ||
+ | </ | ||
+ | |||
+ | Also for fun, I set the lower bound to 7, so you' | ||
+ | starts at 7 (vs. the usual 2). | ||
+ | |||
+ | ====In general==== | ||
+ | Analyze | ||
+ | comparing the algorithm used and the quantity being processed? These are | ||
+ | related | ||
+ | we need to be increasingly | ||
+ | and implement | ||
+ | efficiency will be common themes in all we do. | ||
+ | |||
+ | =====Submission===== | ||
+ | To successfully | ||
+ | met: | ||
+ | |||
+ | * Code must compile cleanly (no warnings or errors) | ||
+ | * Output must be correct, and match that given in sample output above. | ||
+ | * Code must be nicely and consistently indented | ||
+ | * Code must utilize the algorithm and optimizations presented above. | ||
+ | * Code must be commented | ||
+ | * Output Formatting (including spacing) | ||
+ | provided output (see above). | ||
+ | |||
+ | * Track/ | ||
+ | * Submit a copy of your source code to me using the **submit** tool. | ||
- | < | ||