Differences

This shows you the differences between two versions of the page.

--- haas:spring2017:cprog:projects:pnc0 [2017/02/12 22:00] – [Calculating the primality of a number] wedge
+++ haas:spring2017:cprog:projects:pnc0 [2017/02/16 21:14] (current) – [brute force] wedge
@@ Line 11: / Line 11: @@
 To apply your skills in the implementation of prime number calculating algorithms.
-=====Prerequisites/Corequisites=====
-In addition to the new skills required on previous projects, to successfully accomplish/perform this project, the listed resources/experiences need to be consulted/achieved:
-  * ability to make decisions (if statement)
-  * ability to iterate sections of code (for/while statement)
-=====Algorithmic Complexity=====
-A concept in Computer Science curriculum is the notion of computational/algorithmic complexity.
-Basically, a solution to a problem exists on a spectrum of efficiency (typically constrained by time vs. space): if optimizing for time, the code size tends to grow.
-Additionally, if optimizing for time (specifically to reduce the amount of time taken), strategic approaches are taken to reduce unnecessary or redundant operations (yet still achieving the desired end results).
-This project will endeavor to introduce you to the notion that the algorithms and constructs you use in coding your solution can and do make a difference to the overall runtime of your code.
 =====Background=====
 In mathematics, a **prime** number is a value that is only evenly divisible by 1 and itself; it has no other factors. Numbers that have divisibility/factors are known as **composite** numbers.
@@ Line 35: / 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).
-This process incurs a considerable amount of processing overhead on the task, so much so that increasingly large values take increasing amounts of time. Often, approaches to prime number calculation involve various algorithms, which offer various benefits (less time) and drawback (more complex code).
+This process incurs a considerable amount of processing overhead on the task, so much so that increasingly large values take ever-expanding amounts of time. Often, approaches to prime number calculation involve various algorithms, which offer various benefits (less time) and drawback (more complex code).
-Your task for this project is to implement 3 prime number programs:
+Your task for this project is to implement a prime number program using the straightforward, unoptimized brute-force algorithm.
-  - brute force prime calculation (**primebrute**)
-  - slightly optimized version of brute force prime calculation (**primebruteopt**)
 ====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).
-To perform it, we simply attempt to evenly divide all the values between 1 and the number in question. If any one of them divides evenly, the number is **NOT** prime, but instead a composite value.
+To perform it, we simply attempt to evenly divide all the values between 2 and one less than the number in question. If any one of them divides evenly, the number is **NOT** prime, but instead a composite value.
 Checking the remainder of a division indicates whether or not a division was clean (having 0 remainder indicates such a state).
@@ Line 77: / Line 61: @@
 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, as once we have proven the non-primality of a number, the state is set: it is composite. So be sure to use a **break** statement to terminate the computation loop (will also be a nice boost to runtime).
+Even though you have identified the number as a composite, you MUST **CONTINUE** evaluating the remainder of the values (up to 119-1). It might seem pointless (and it is for a production program), but I want you to see the performance implications this creates.
-====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 to be evenly divisible, we can also assume primality and bail out.
+Some things to keep in mind on your implementation:
-The C library has a **sqrt()** function available through including the **math.h** header file, and linking against the math library at compile time (add **-lm** to your gcc line).
+  * loops, you will want to use loops for this. Especially these two brute force algorithms.
+  * a nested loop makes the most sense.
+  * you know the starting value and the terminating condition, so a clear starting and ending point. for() loops make the most sense.
+  * let the loops drive the overall process. Identify prime/composite status separate from loop terminating conditions.
+    * and remember, the baseline brute force algorithm may well identify a value as composite, but won't terminate the loop. The optimized brute force will act on the identification of a composite value by terminating the processing of additional values.
+  * your timing should start before the loop, and terminate immediately following the terminating newline outside the loops.
+====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 the square root of, and assign the result to an **int**:
+There is no further need to check the remaining values, as once we have proven the non-primality of a number, the state is set: it is composite. So be sure to use a **break** statement to terminate the computation loop (will also be a nice boost to runtime).
-<code c>
-int x = 25;
-int y = 0;
-y = sqrt(x);
-// y should be 5 as a result
-</code>
-For instance, the number 37 (using the square root optimization), we find the square root (whole number) of 37 is 6, so we only need to check 2-6:
-<code>
-% 2 = 1 (2 is not a factor of 37)
-% 3 = 1 (3 is not a factor of 37)
-% 4 = 1 (4 is not a factor of 37)
-% 5 = 2 (5 is not a factor of 37)
-% 6 = 1 (6 is not a factor of 37)
-</code>
-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 a nice comparison against our brute force baseline.
-====further optimization====
-There are many other methods, approaches, and tweaks that can be employed to further improve runtime (while maintaining accuracy-- all your solutions must match: the same prime numbers should be identified no matter which program is run).
-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===
-  * [[https://primes.utm.edu/notes/faq/six.html|Prime patterns of 6]]
-  * [[https://lab46.g7n.org/~wedge/php/web.php?width=800&height=600&div=6&max=145&prime=1&factor=0&spiral=0|Visualization of Primes in a web of 6 divisions]]
-  * [[https://lab46.g7n.org/~wedge/php/web.php?width=800&height=600&div=12&max=145&prime=1&factor=0&spiral=0|Visualization of Primes in a web of 12 divisions]]
-  * [[https://en.wikipedia.org/wiki/Ulam_spiral|Ulam spiral]]
-  * [[https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes|Sieve of Eratosthenes]]
-Of particular note: the sieve algorithms take advantage of a increased storage space, where others (like brute force) are predominantly time-based. The sieve is also more detailed... even if you don't decide to implement a sieve, take a look and compare the algorithm to what you've done to see the differences in approaches.
+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.
 =====Program=====
-It is your task to write 3 separate prime number calculating programs:
+It is your task to write a brute-force prime number calculating program:
   - **primebrute.c**: for your brute force implementation
-  - **primesqrt.c**: for your square root-optimization of the brute force
+  - **primebruteopt.c**: for your slightly optimized brute force implementation
-  - **primeopt.c**: for your optimized solution, be it basing off the existing ones, or taking a different approach
 Your program should:
-  * obtain 2 parameters from the command-line (see **command-line arguments** section below):
+  * obtain 1 parameter from the command-line (see **command-line arguments** section below):
     * 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 value; you can make the assumption that the user will always do the right thing.
-    * these values should be positive integer values; you can make the assumption that the user will always do the right thing.
+  * do NO algorithmic optimizations of any sort (it is called brute-force for a reason).
+  * in the case of **primebruteopt**, perform only the short circuit optimization described above.
+    * please take note in differences in run-time, contemplating the impact the two algorithms have on performance.
   * start your stopwatch (see **timing** section below):
-  * perform the algorithm against the value
+  * perform the correct algorithm against the input
-  * if enabled, display the prime numbers found in the range
+  * display (to STDOUT) the prime numbers found in the range
-  * output the processing run-time to STDERR (do this always).
+  * 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:
-    * 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).
-====Other considerations====
-All your programs MUST perform the calculations to determine primality- you may not always be printing it out (depending on argv[2]), but work must be done to ensure the value is identified as a prime/composite value.
-For example:
-<code>
-if (show == 1)
-{
-	work to determine if it is prime
-	if prime
-		print number
-}
-</code>
-will actually skip the core processing, and you’ll see some amazing runtimes as a result. They may be amazing, but they’re not real, because you’re not actually doing anything.
-What you want instead:
-<code>
-work to determine if it is prime
-if (show == 1)
-{
-	if prime
-		print number
-}
-</code>
-there are many ways to express the above, through compound if statements and other arrangements, but notice how nothing is holding back “work to determine if it is prime”.
-That also isn’t to say you can’t avoid doing a work run if you’re able to determine its non-primality with a simple pretest (even value, factor of 3, etc.), but that’s actually considered more of the core “work”, so it is more than okay (and encouraged in the primeopt).
 =====Command-Line Arguments=====
-To automate our comparisons, we will be making use of command-line arguments in our programs. As we have yet to really get into arrays, I will provide you same code that you can use that will allow you to utilize them for the purposes of this project.
+To automate our comparisons, we will be making use of command-line arguments in our programs. As we have yet to really get into arrays, I will provide you some code that you can use that will allow you to utilize them for the purposes of this project.
 ====header files====
@@ Line 198: / Line 124: @@
   * argv[0]: program invocation (path + program name)
   * argv[1]: our maximum / upper bound
-  * argv[2]: visibility (1 to show primes, 0 to be silent)
-There are ways to do flexible argument parsing, and even to have dashed options as we have on various commands. But such things are beyond the scope of our current endeavors, so we will stick to this basic functionality for now.
 ====Simple argument checks====
-Although I'm not going to require extensive argument checking for this project, here's how we would check to see if the minimal number of arguments has been provided:
+Although I'm not going to require extensive argument parsing or checking for this project, we should check to see if the minimal number of arguments has been provided:
 <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, "Not enough arguments!\n");
@@ Line 213: / Line 136: @@
 </code>
-If you're wondering, "why 3? I thought we only had 2.", C includes the program's name as the first argument, so we want program + max + visibility, or 3.
+====Grab and convert max====
+Finally, we need to put the argument representing the maximum value into a variable.
-====Grab and convert max and visibility====
-Finally, we need to put the arguments representing the maximum value and visibility settings into variables.
-I'd recommend declaring two variables of type **int**.
+I'd recommend declaring a variable of type **int**.
 We will use the **atoi(3)** function to quickly convert the command-line arguments into **int** values:
@@ Line 224: / Line 145: @@
 <code c>
     max  = atoi(argv[1]);
-    show = atoi(argv[2]);
 </code>
@@ Line 273: / Line 193: @@
 ====Displaying the runtime====
-Once we having the starting and ending times, we can display this to STDERR. You'll want this line:
+Once we have the starting and ending times, we can display this to STDERR. You'll want this line:
 <code c>
-    fprintf(stderr, "%10.6lf\n", time_end.tv_sec - time_start.tv_sec + ((time_end.tv_usec - time_start.tv_usec) / 1000000.0));
+fprintf(stderr, "%10.6lf\n",
+time_end.tv_sec-time_start.tv_sec+((time_end.tv_usec-time_start.tv_usec)/1000000.0));
 </code>
-For clarity sake, that format specifier is "%10.6lf", where the "lf" is "long float", that is **NOT** a number one but a lowercase letter 'ell'.
+For clarity sake, that format specifier is "%10.6lf", where the "lf" is "long float", that is **NOT** a number 'one' but a lowercase letter 'ell'.
 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>
-lab46:~/src/cprog/pnc0$ ./primebrute 90 1
+lab46:~/src/cprog/pnc0$ ./primebrute 90
 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89
 .000088
 lab46:~/src/cprog/pnc0$
 </cli>
-Brute force not showing primes:
-<cli>
-lab46:~/src/cprog/pnc0$ ./primebrute 90 0
-.000008
-lab46:~/src/cprog/pnc0$
-</cli>
-Similarly, for the square root version (showing primes):
-<cli>
-lab46:~/src/cprog/pnc0$ ./primesqrt 90 1
-3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89
-.000089
-lab46:~/src/cprog/pnc0$
-</cli>
-And, without showing primes:
-<cli>
-lab46:~/src/cprog/pnc0$ ./primesqrt 90 0
-.000006
-lab46:~/src/cprog/pnc0$
-</cli>
-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 "better" algorithm may have a sweet spot or power band: they may actually perform worse until (especially at the beginning).
-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.
@@ Line 330: / Line 219: @@
 If you'd like to compare your implementations, I rigged up a script called **primerun** which you can run.
-In order to work, you **MUST** be in the directory where your **primebrute**, **primesqrt**, and **primeopt** binaries reside, and they must be named as such.
+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>
 lab46:~/src/cprog/pnc0$ primerun
-============================================
+===================================
-   range       brute        sqrt         opt
+    range        brute     bruteopt
-============================================
+===================================
-    0.000002    0.000002    0.000002
+     0.000177     0.000127
-    0.000002    0.000002    0.000002
+     0.000389     0.000159
-    0.000003    0.000004    0.000002
+     0.001526     0.000358
-    0.000005    0.000020    0.000003
+     0.005399     0.000964
-    0.000012    0.000023    0.000003
+     0.019101     0.002809
-    0.000037    0.000029    0.000006
+     0.070738     0.009380
-    0.000165    0.000036    0.000014
+     0.271477     0.032237
-    0.000540    0.000080    0.000033
+     1.067010     0.117134
-    0.001761    0.000187    0.000078
+     4.193584     0.424562
-    0.006115    0.000438    0.000189
+   ----------     1.573066
-    0.021259    0.001036    0.000458
+   ----------     7.753300
-    0.077184    0.002520    0.001153
+   ----------   ----------
-    0.281958    0.006156    0.002826
+===================================
-    1.046501    0.015234    0.007135
+ verify:       OK           OK
-    5.160141    0.045482    0.021810
+===================================
-    --------    0.119042    0.057520
-    --------    0.301531    0.146561
- 1048576    --------    0.758027    0.370700
- 2097152    --------    1.921014    0.943986
- 4194304    --------    4.914725    2.423202
- 8388608    --------    --------    --------
-============================================
- verify:       OK          OK          OK
-============================================
 lab46:~/src/cprog/pnc0$
 </cli>
@@ Line 372: / Line 252: @@
 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 "OK" displayed beneath in the appropriate column; if unsuccessful, you will see "MISMATCH".
-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 "OK" displayed beneath in the appropriate column; if unsuccessful, you will be "MISMATCH".
-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)
-=====Bonus Points=====
-There will be an additional bonus point opportunity with this project, based on processing run-time of your optimized solution.
 =====Submission=====
 To successfully complete this project, the following criteria must be met:
@@ Line 393: / Line 261: @@
   * Code must utilize the algorithm(s) presented above:
     * **primebrute.c** must do the unoptimized brute force method
-    * **primesqrt.c** must utilize the brute force method along with the square root trick (no other tricks)
+    * **primebruteopt.c** must do the brute force with the composite loop **break**
-    * **primeopt.c** is your attempt at optimizing the code, using whatever additional tricks (or enhancements to tricks) to further improve runtime.
   * Code must be commented
     * have a properly filled-out comment banner at the top
@@ Line 406: / Line 273: @@
 <cli>
-$ submit cprog pnc0 primebrute.c primesqrt.c primeopt.c
+$ submit cprog pnc0 primebrute.c primebruteopt.c
 Submitting cprog project "pnc0":
     -> primebrute.c(OK)
-    -> primesqrt.c(OK)
+    -> primebruteopt.c(OK)
-    -> primeopt.c(OK)
 SUCCESSFULLY SUBMITTED
@@ Line 416: / 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.
+What I will be looking for:
+<code>
+:pnc0:final tally of results (52/52)
+*:pnc0:primebrute.c submitted with submit tool [2/2]
+*:pnc0:primebrute.c no negative compiler messages [4/4]
+*:pnc0:primebrute.c implements only specified algorithm [6/6]
+*:pnc0:primebrute.c adequate indentation and comments [4/4]
+*:pnc0:primebrute.c output conforms to specifications [4/4]
+*:pnc0:primebrute.c primerun runtime tests succeed [6/6]
+*:pnc0:primebruteopt.c submitted with submit tool [2/2]
+*:pnc0:primebruteopt.c no negative compiler messages [4/4]
+*:pnc0:primebruteopt.c implements only specified algorithm [6/6]
+*:pnc0:primebruteopt.c adequate indentation and comments [4/4]
+*:pnc0:primebruteopt.c output conforms to specifications [4/4]
+*:pnc0:primebruteopt.c primerun runtime tests succeed [6/6]
+</code>

Lab46 Wiki

User Tools

Site Tools

Differences

Page Tools