Lab46 Wiki

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
<WRAP centeralign round box>
<WRAP><color red><fs 200%>Corning Community College</fs></color></WRAP>
<WRAP><fs 150%>CSCS2730 Systems Programming</fs></WRAP>
</WRAP>

~~TOC~~

======Project: ALGORITHMS - PRIME NUMBER CALCULATION (pnc0)======

=====Objective=====
To apply your skills in the implementation of prime number calculating algorithms.

=====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.

The number **6** is a **composite** value, as in addition to 1 and 6, it also has the factors of 2 and 3.

The number **17** is a **prime** number, as no numbers other than 1 and 17 can be evenly divided.

=====Calculating the primality of a number=====
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 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 a prime number program using the straightforward, unoptimized brute-force algorithm.

====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 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).

For example, the number 11:

<code>
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)
</code>

Because none of the values 2-10 evenly divided into 11, we can say it passed the test: **11 is a prime number**

On the other hand, take 119:

<code>
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)
</code>

Because 7 evenly divided into 119, it failed the test: 119 is **not** a prime, but instead a composite number.

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.

===algorithm===
Some things to keep in mind on your implementation:

  * 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:

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).

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 a brute-force prime number calculating program:

  - **primebrute.c**: for your brute force implementation
  - **primebruteopt.c**: for your slightly optimized brute force implementation

Your program should:
  * 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)
    * this value should be a positive integer value; 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 correct algorithm against the input
  * display (to STDOUT) the prime numbers found in the range
  * 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:
    * 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).

=====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 some code that you can use that will allow you to utilize them for the purposes of this project.

====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 turn the command-line parameter into an integer, and that header file is **stdlib.h**, so be sure to include it with the others:

<code c>
#include <stdio.h>
#include <stdlib.h>
</code>

====setting up main()====
To accept (or rather, to gain access) to arguments given to your program at runtime, we need to specify two parameters to the main() function. While the names don't matter, the types do.. I like the traditional **argc** and **argv** names, although it is also common to see them abbreviated as **ac** and **av**.

Please declare your main() function as follows:

<code c>
int main(int argc, char **argv)
</code>

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

====Simple argument checks====
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 < 2)  // if less than 2 arguments have been provided
    {
        fprintf(stderr, "Not enough arguments!\n");
        exit(1);
    }
</code>

====Grab and convert max====
Finally, we need to put the argument representing the maximum value into a variable.

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:

<code c>
    max  = atoi(argv[1]);
</code>

And now we can proceed with the rest of our prime implementation.

=====Timing=====
Often times, when checking the efficiency of a solution, a good measurement (especially for comparison), is to time how long the processing takes.

In order to do that in our prime number programs, we are going to use C library functions that obtain the current time, and use it as a 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'll need to include the **sys/time.h** header file, so be sure to add it in with the existing ones:

<code c>
#include <stdio.h>
#include <stdlib.h>
#include <sys/time.h>
</code>

====timeval variables====
**gettimeofday(2)** uses a **struct timeval** data type, of which we'll need to declare two variables in our programs (one for storing the 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;   // ending time
</code>

====Obtaining the time====
To use **gettimeofday(2)**, we merely place it at the point in our code we wish to take the time.

For our prime number programs, you'll want to grab the start time **AFTER** you've declared variables and processed arguments, but **JUST BEFORE** starting the driving loop doing the processing.

That call will look something like this:

<code c>
    gettimeofday(&time_start, 0);
</code>

The ending time should be taken immediately after all processing (and prime number output) is completed, and right before we display the timing information to STDERR:

<code c>
    gettimeofday(&time_end, 0);
</code>

====Displaying the runtime====
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));
</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'.

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=====
Your program output should be as follows (given the specified range):

<cli>
lab46:~/src/sysprog/pnc0$ ./primebrute 90
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
lab46:~/src/sysprog/pnc0$ 
</cli>

The execution of the programs is short and simple- grab the parameters, do the processing, produce the output, and then terminate.

=====Check Results=====
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** and **primebruteopt** binaries reside, and must be named as such.

For instance (running on my implementation of prime brute and primebruteopt):

<cli>
lab46:~/src/sysprog/pnc0$ primerun
===================================
    range        brute     bruteopt
===================================
      128     0.000177     0.000127
      256     0.000389     0.000159
      512     0.001526     0.000358
     1024     0.005399     0.000964
     2048     0.019101     0.002809
     4096     0.070738     0.009380
     8192     0.271477     0.032237
    16384     1.067010     0.117134
    32768     4.193584     0.424562
    65536   ----------     1.573066
   131072   ----------     7.753300
   262144   ----------   ----------
===================================
 verify:       OK           OK
===================================
lab46:~/src/sysprog/pnc0$ 
</cli>

For evaluation, each test is run 4 times, and the resulting time is averaged. During development, I have it set to only run each test once.

If the runtime of a particular prime variant exceeds an upper threshold (likely to be set at 2 seconds), it will be omitted from further tests, and a series of dashes will instead appear in the output.

If you don't feel like waiting, simply hit **CTRL-c** and the script will terminate.

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".
=====Submission=====
To successfully complete this project, the following criteria must be met:

  * Code must compile cleanly (no warnings or errors)
  * Output must be correct, and match the form given in the sample output above.
  * Code must be nicely and consistently indented (you may use the **indent** tool)
  * Code must utilize the algorithm(s) presented above:
    * **primebrute.c** must do the unoptimized brute force method
    * **primebruteopt.c** must do the brute force with the composite loop **break** 
  * Code must be commented
    * have a properly filled-out comment banner at the top
      * be sure to include any compiling instructions
    * have at least 20% of your program consist of **<nowiki>//</nowiki>**-style descriptive comments
  * Output Formatting (including spacing) of program must conform to the provided output (see above).
  * Track/version the source code in a repository
  * Submit a copy of your source code to me using the **submit** tool.

To submit this program to me using the **submit** tool, run the following command at your lab46 prompt:

<cli>
$ submit sysprog pnc0 primebrute.c primebruteopt.c
Submitting sysprog project "pnc0":
    -> primebrute.c(OK)
    -> primebruteopt.c(OK)

SUCCESSFULLY SUBMITTED
</cli>

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>
52: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

Page Tools
