This shows you the differences between two versions of the page.
Next revision | Previous revision | ||
haas:spring2017:sysprog:projects:pnc0 [2016/02/25 18:12] – external edit 127.0.0.1 | haas:spring2017:sysprog:projects:pnc0 [2017/03/21 13:10] (current) – wedge | ||
---|---|---|---|
Line 21: | Line 21: | ||
As of yet, there is no quick and direct way of determining the primality of a given number. Instead, we must perform a series of tests to determine if it fails primality (typically by proving it is composite). | As of yet, there is no quick and direct way of determining the primality of a given number. Instead, we must perform a series of tests to determine if it fails primality (typically by proving it is composite). | ||
- | This process incurs a considerable amount of processing overhead on the task, so much so that increasingly large values take increasing | + | This process incurs a considerable amount of processing overhead on the task, so much so that increasingly large values take ever-expanding |
- | Your task for this project is to implement | + | Your task for this project is to implement |
- | + | ||
- | - brute force prime calculation | + | |
- | | + | |
- | - a further optimized solution | + | |
====brute force==== | ====brute force==== | ||
The brute force approach is the simplest to implement (and likely also the worst-performing). We will use it as our baseline (it is nice to have something to compare against). | The brute force approach is the simplest to implement (and likely also the worst-performing). We will use it as our baseline (it is nice to have something to compare against). | ||
- | To perform it, we simply attempt to evenly divide all the values between | + | To perform it, we simply attempt to evenly divide all the values between |
Checking the remainder of a division indicates whether or not a division was clean (having 0 remainder indicates such a state). | Checking the remainder of a division indicates whether or not a division was clean (having 0 remainder indicates such a state). | ||
Line 65: | Line 61: | ||
Because 7 evenly divided into 119, it failed the test: 119 is **not** a prime, but instead a composite number. | Because 7 evenly divided into 119, it failed the test: 119 is **not** a prime, but instead a composite number. | ||
- | There is no further need to check the remaining values, | + | Even though you have identified |
- | ====square root==== | + | ===algorithm=== |
- | An optimization to the computation of prime numbers is the square root trick. Basically, if we've processed numbers up to the square root of the number we're testing, and none have proven | + | Some things |
- | The C library has a **sqrt()** function available through including | + | |
+ | | ||
+ | * you know the starting value and the terminating condition, so a clear starting and ending point. for() loops make the most sense. | ||
+ | | ||
+ | | ||
+ | | ||
+ | ====brute force optimization==== | ||
+ | The optimized version of brute force will make but one algorithmic change, and that takes place at the moment of identifying a number as composite. So, if we had our 119 example above, and discovered that 7 was a factor: | ||
- | To use **sqrt()**, we pass in the value we wish to obtain | + | There is no further need to check the remaining values, as once we have proven |
- | + | ||
- | <code c> | + | |
- | int x = 25; | + | |
- | int y = 0; | + | |
- | + | ||
- | y = sqrt(x); | + | |
- | + | ||
- | // y should be 5 as a result | + | |
- | </ | + | |
- | + | ||
- | For instance, the number 37 (using the square root optimization), | + | |
- | + | ||
- | < | + | |
- | 37 % 2 = 1 (2 is not a factor | + | |
- | 37 % 3 = 1 (3 is not a factor of 37) | + | |
- | 37 % 4 = 1 (4 is not a factor of 37) | + | |
- | 37 % 5 = 2 (5 is not a factor of 37) | + | |
- | 37 % 6 = 1 (6 is not a factor of 37) | + | |
- | </ | + | |
- | + | ||
- | Because none of these values evenly divides, we can give 37 a pass: **it is a prime** | + | |
- | + | ||
- | This will dramatically improve the runtime, and offers | + | |
- | + | ||
- | ====further optimization==== | + | |
- | There are many other methods, approaches, and tweaks that can be employed | + | |
- | + | ||
- | So I'd like you to explore other optimizations that can be made, be it using other prime number algorithms, further refining existing ones, or playing off patterns in numbers. | + | |
- | + | ||
- | One assumption I will allow you to make for your optimized solution is that the single-digit primes (2, 3, 5, 7) can be assumed prime, and just printed out if having them be calculated would otherwise break your algorithm (might be helpful to some people; I certainly found it useful in some of my solutions). | + | |
- | ===some optimization ideas=== | + | Make no other optimizations- this first project is to set up some important base line values that we can use for algorithmic comparison later on. |
- | * [[https:// | + | |
- | * [[https:// | + | |
- | * [[https:// | + | |
- | * [[https:// | + | |
=====Program===== | =====Program===== | ||
- | It is your task to write 3 separate | + | It is your task to write a brute-force |
- | - primebrute.c: | + | - **primebrute.c**: for your brute force implementation |
- | - primesqrt.c: for your square root-optimization of the brute force | + | - **primebruteopt.c**: for your slightly optimized |
- | - primeopt.c: for your optimized solution, be it basing off the existing ones, or taking a different approach | + | |
Your program should: | Your program should: | ||
- | * obtain | + | * obtain |
* argv[1]: maximum value to calculate to (your program should run from (approximately) 2 through that number (inclusive of that number) | * argv[1]: maximum value to calculate to (your program should run from (approximately) 2 through that number (inclusive of that number) | ||
- | * argv[2]: visibility. If a **1** is provided, print out the prime numbers in a space separated list; if a **0** is provided, run silent: only display the runtime information. | + | * this value should be a positive integer |
- | * these values | + | * do NO algorithmic optimizations of any sort (it is called brute-force for a reason). |
+ | * in the case of **primebruteopt**, | ||
+ | * please take note in differences in run-time, contemplating the impact the two algorithms have on performance. | ||
* start your stopwatch (see **timing** section below): | * start your stopwatch (see **timing** section below): | ||
* perform the correct algorithm against the input | * perform the correct algorithm against the input | ||
- | * if enabled, | + | * display |
- | * output the processing run-time to STDERR | + | * stop your stopwatch. Calculate the time that has transpired. |
+ | * output the processing run-time to STDERR | ||
* your output **MUST** be conformant to the example output in the **execution** section below. This is also a test to see how well you can implement to specifications. Basically: | * your output **MUST** be conformant to the example output in the **execution** section below. This is also a test to see how well you can implement to specifications. Basically: | ||
- | * if primes are being displayed, they are space-separated (first prime hugs the left margin), and when all said and done, a newline is issued. | + | * as primes are being displayed, they are space-separated (first prime hugs the left margin), and when all said and done, a newline is issued. |
* the timing information will be displayed in accordance to code I will provide (in the **timing** section). | * the timing information will be displayed in accordance to code I will provide (in the **timing** section). | ||
=====Command-Line Arguments===== | =====Command-Line Arguments===== | ||
- | To automate our comparisons, | + | To automate our comparisons, |
====header files==== | ====header files==== | ||
Line 153: | Line 124: | ||
* argv[0]: program invocation (path + program name) | * argv[0]: program invocation (path + program name) | ||
* argv[1]: our maximum / upper bound | * argv[1]: our maximum / upper bound | ||
- | * argv[2]: visibility (1 to show primes, 0 to be silent) | ||
====Simple argument checks==== | ====Simple argument checks==== | ||
Line 159: | Line 129: | ||
<code c> | <code c> | ||
- | if (argc < 3) // if less than 3 arguments have been provided | + | if (argc < 2) // if less than 2 arguments have been provided |
{ | { | ||
fprintf(stderr, | fprintf(stderr, | ||
Line 166: | Line 136: | ||
</ | </ | ||
- | ====Grab and convert max and visibility==== | + | ====Grab and convert max==== |
- | Finally, we need to put the arguments | + | Finally, we need to put the argument |
- | I'd recommend declaring | + | I'd recommend declaring |
We will use the **atoi(3)** function to quickly convert the command-line arguments into **int** values: | We will use the **atoi(3)** function to quickly convert the command-line arguments into **int** values: | ||
Line 175: | Line 145: | ||
<code c> | <code c> | ||
max = atoi(argv[1]); | max = atoi(argv[1]); | ||
- | show = atoi(argv[2]); | ||
</ | </ | ||
Line 224: | Line 193: | ||
====Displaying the runtime==== | ====Displaying the runtime==== | ||
- | Once we having | + | Once we have the starting and ending times, we can display this to STDERR. You'll want this line: |
<code c> | <code c> | ||
- | | + | fprintf(stderr, |
+ | time_end.tv_sec-time_start.tv_sec+((time_end.tv_usec-time_start.tv_usec)/ | ||
</ | </ | ||
- | For clarity sake, that format specifier is " | + | For clarity sake, that format specifier is " |
And with that, we can compute an approximate run-time of our programs. The timing won't necessarily be accurate down to that level of precision, but it will be informative enough for our purposes. | And with that, we can compute an approximate run-time of our programs. The timing won't necessarily be accurate down to that level of precision, but it will be informative enough for our purposes. | ||
- | =====Execution===== | ||
- | Several operating behaviors are shown as examples. | ||
- | Brute force showing primes: | + | =====Execution===== |
+ | Your program output should be as follows (given the specified range): | ||
<cli> | <cli> | ||
- | lab46: | + | 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 | 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.000088 | 0.000088 | ||
lab46: | lab46: | ||
</ | </ | ||
- | |||
- | Brute force not showing primes: | ||
- | |||
- | <cli> | ||
- | lab46: | ||
- | 0.000008 | ||
- | lab46: | ||
- | </ | ||
- | |||
- | Similarly, for the square root version (showing primes): | ||
- | |||
- | <cli> | ||
- | 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.000089 | ||
- | lab46: | ||
- | </ | ||
- | |||
- | And, without showing primes: | ||
- | |||
- | <cli> | ||
- | lab46: | ||
- | 0.000006 | ||
- | lab46: | ||
- | </ | ||
- | |||
- | Don't be alarmed by the visible square root actually seeming to take MORE time; we have to consider the range as well: 90 is barely anything, and there is overhead incurred from the **sqrt()** function call. The real savings will start to be seen once we get into the thousands (and beyond). | ||
- | |||
- | And that's another neat thing with algorithm comparison: a " | ||
- | |||
- | The same goes for your optimized solution (same parameters). | ||
The execution of the programs is short and simple- grab the parameters, do the processing, produce the output, and then terminate. | The execution of the programs is short and simple- grab the parameters, do the processing, produce the output, and then terminate. | ||
Line 281: | Line 219: | ||
If you'd like to compare your implementations, | If you'd like to compare your implementations, | ||
- | In order to work, you **MUST** be in the directory where your **primebrute**, **primesqrt**, | + | In order to work, you **MUST** be in the directory where your **primebrute** and **primebruteopt** binaries reside, and must be named as such. |
- | For instance (running on my implementations): | + | For instance (running on my implementation of prime brute and primebruteopt): |
<cli> | <cli> | ||
- | lab46: | + | lab46: |
- | ============================================ | + | =================================== |
- | | + | range brute bruteopt |
- | ============================================ | + | =================================== |
- | | + | |
- | | + | |
- | | + | |
- | | + | |
- | | + | |
- | | + | |
- | 512 0.000165 | + | |
- | | + | |
- | 2048 0.001761 | + | |
- | 4096 0.006115 | + | |
- | 8192 0.021259 | + | 131072 |
- | 16384 | + | 262144 |
- | | + | =================================== |
- | | + | |
- | | + | =================================== |
- | | + | lab46: |
- | 524288 | + | |
- | 1048576 | + | |
- | | + | |
- | 4194304 | + | |
- | | + | |
- | ============================================ | + | |
- | | + | |
- | ============================================ | + | |
- | lab46: | + | |
</ | </ | ||
Line 323: | Line 252: | ||
If you don't feel like waiting, simply hit **CTRL-c** and the script will terminate. | If you don't feel like waiting, simply hit **CTRL-c** and the script will terminate. | ||
- | In the example output above, my **primeopt** is playing with an implementation of the **6a+/-1** algorithm. | + | I also include a validation check- to ensure your prime programs are actually producing the correct list of prime numbers. If the check is successful, you will see " |
- | + | ||
- | I also include a validation check- to ensure your prime programs are actually producing the correct list of prime numbers. If the check is successful, you will see " | + | |
- | + | ||
- | If you'd like to experiment with other variations, the script also recognizes prime variants of the following names: | + | |
- | * primeopt0 (for an additional optimization) | + | |
- | * primeopt1 (and another) | + | |
- | * primeopt2 (if you'd like another entry for another optimization) | + | |
- | * primeopt3 (for yet another optimization) | + | |
- | * primeopt4 (and one more; hey, I want you to have nice things) | + | |
=====Submission===== | =====Submission===== | ||
To successfully complete this project, the following criteria must be met: | To successfully complete this project, the following criteria must be met: | ||
Line 341: | Line 261: | ||
* Code must utilize the algorithm(s) presented above: | * Code must utilize the algorithm(s) presented above: | ||
* **primebrute.c** must do the unoptimized brute force method | * **primebrute.c** must do the unoptimized brute force method | ||
- | * **primesqrt.c** must utilize | + | * **primebruteopt.c** must do the brute force with the composite loop **break** |
- | | + | |
* Code must be commented | * Code must be commented | ||
* have a properly filled-out comment banner at the top | * have a properly filled-out comment banner at the top | ||
Line 354: | Line 273: | ||
<cli> | <cli> | ||
- | $ submit sysprog pnc0 primebrute.c | + | $ submit sysprog pnc0 primebrute.c |
Submitting sysprog project " | Submitting sysprog project " | ||
-> primebrute.c(OK) | -> primebrute.c(OK) | ||
- | -> primesqrt.c(OK) | + | -> primebruteopt.c(OK) |
- | -> primeopt.c(OK) | + | |
SUCCESSFULLY SUBMITTED | SUCCESSFULLY SUBMITTED | ||
Line 364: | Line 282: | ||
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. | 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. | ||
+ | |||
+ | What I will be looking for: | ||
+ | |||
+ | < | ||
+ | 52: | ||
+ | *: | ||
+ | *: | ||
+ | *: | ||
+ | *: | ||
+ | *: | ||
+ | *: | ||
+ | *: | ||
+ | *: | ||
+ | *: | ||
+ | *: | ||
+ | *: | ||
+ | *: | ||
+ | </ |