Table of Contents

Corning Community College

CSCS2330 Discrete Structures

~~TOC~~

Project: OPTIMIZING ALGORITHMS - PRIME NUMBER CALCULATION (pnc1)

Objective

To apply your skills in algorithmic optimization through the implementation of improved prime number calculating programs.

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.

Optimizing the prime number calculation

We should be fairly familiar with the process of computing primes by now, which is an essential beginning step to accomplish before pursuing optimization. Following will be some optimizations I'd like you to implement (as separate programs) so we can analyze the differences in approaches, and how they influence runtimes.

odds (primeodds)

Some optimizations can be the result of sheer common sense observations. For instance, with the exception of 2, all primes are odd numbers.

So does it make sense to check an even number for primality? No, it doesn't.

And can we predict even numbers? Yes, we can: they occur every other number.

Therefore, we can start our number checking at 3, and skip 2 values each time (3, 5, 7, 9, 11, etc.).

To make our output correct, we would simply display the “2” outright. We know it is prime, and will make that assumption with this program.

This program should be an optimization based on your primebruteopt program from pnc0.

square root (primesqrt)

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.

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

To use sqrt(), we pass in the value we wish to obtain the square root of, and assign the result to an int:

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), we find the square root (whole number) of 37 is 6, so we only need to check 2-6:

37 % 2 = 1 (2 is not a factor of 37)
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 a nice comparison against our brute force baseline.

NOTE: You will be reverting to checking all numbers (both even and odd) with this program.

This program should be an optimization based on your primebruteopt program from pnc0.

sqrt() odds (primesqrtodds)

In the previous program we used sqrt() against all the values, even or odd.

This program will eliminate the even values, checking only the odds.

This program should be an optimization of your primesqrt program.

sqrt()-less square root (primesqrtopt)

An optimization to the previous process, which used sqrt(), this variation will do the exact same thing, but without using the sqrt() function. It will approximate the square root.

We know that a square root (especially a whole numbered square root), is when we have whole number factors that are squared. For instance:

9*9 == 81, the square root of 81 is 9.

If we were checking 81 to be prime, we'd only have to check up to 9.

We don't need a sqrt() function to tell us this, we can determine the approximate square root point ourselves- simply square the current factor being tested, and so long as it hasn't exceeded the value we're checking, we know to continue.

There are some important lessons at play here:

NOTE: Again, for comparison sake, check ALL numbers (even and odd) for this variant.

This program should be an optimization of your primesqrt program.

sqrt()-less odds (primesqrtoptodds)

And, to round out our analysis, enhance the optimized sqrt variant to only check odd values.

This program should be an optimization of your primesqrtopt program.

Program

It is your task to write some optimized prime number calculating programs:

  1. primeodds.c: checking only odd values
  2. primesqrt.c: for your sqrt()-based implementation
  3. primesqrtodds.c: sqrt()-based implementation only checking odds
  4. primesqrtopt.c: for your sqrt()-less square root approximated implementation
  5. primesqrtoptodds.c: sqrt()-less square root only checking odds

Your program should:

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.

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:

#include <stdio.h>
#include <stdlib.h>

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:

int main(int argc, char **argv)

The arguments are accessible via the argv array, in the order they were specified:

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:

    if (argc < 2)  // if less than 2 arguments have been provided
    {
        fprintf(stderr, "Not enough arguments!\n");
        exit(1);
    }

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:

    max  = atoi(argv[1]);

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:

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

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

    struct timeval time_start; // starting time
    struct timeval time_end;   // ending time

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:

    gettimeofday(&time_start, 0);

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:

    gettimeofday(&time_end, 0);

Displaying the runtime

Once we having the starting and ending times, we can display this to STDERR. You'll want this line:

    fprintf(stderr, "%10.6lf\n", time_end.tv_sec - time_start.tv_sec + ((time_end.tv_usec - time_start.tv_usec) / 1000000.0));

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

lab46:~/src/sysprog/pnc1$ ./primesqrt 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/pnc1$ 

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 primesqrt, primesqrtopt and primemap binaries reside, and must be named as such. You'll also want to copy in your primebrute and primebruteopt binaries to truly get the full picture.

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

lab46:~/src/discrete/pnc1$ primerun
====================================================================================================
    range        brute     bruteopt         odds         sqrt     sqrtodds      sqrtopt  sqrtoptodds
====================================================================================================
      128     0.000097     0.000061     0.000075     0.000074     0.000074     0.000071     0.000052
      256     0.000238     0.000105     0.000094     0.000096     0.000093     0.000061     0.000059
      512     0.001000     0.000246     0.000165     0.000137     0.000096     0.000102     0.000070
     1024     0.003545     0.000623     0.000333     0.000262     0.000183     0.000129     0.000124
     2048     0.012749     0.001880     0.000994     0.000592     0.000324     0.000249     0.000181
     4096     0.047120     0.006206     0.003176     0.001352     0.000733     0.000493     0.000302
     8192     0.180497     0.021454     0.010806     0.003317     0.001723     0.001093     0.000636
    16384     0.705101     0.077583     0.038932     0.008163     0.004174     0.002539     0.001438
    32768     2.786815     0.282426     0.141502     0.020472     0.010376     0.005936     0.003327
    65536   ----------     1.047397     0.524213     0.052126     0.026311     0.014934     0.008014
   131072   ----------     5.159748     2.580796     0.140917     0.070404     0.044539     0.023510
   262144   ----------   ----------   ----------     0.368282     0.183205     0.117075     0.060993
   524288   ----------   ----------   ----------     0.961903     0.488336     0.295707     0.152570
  1048576   ----------   ----------   ----------     2.487897     1.235418     0.745615     0.382472
  2097152   ----------   ----------   ----------   ----------     3.232523     1.893893     0.967266
  4194304   ----------   ----------   ----------   ----------   ----------     4.856079     2.472582
  8388608   ----------   ----------   ----------   ----------   ----------   ----------   ----------
====================================================================================================
 verify:       OK           OK           OK           OK           OK           OK           OK
====================================================================================================
lab46:~/src/discrete/pnc1$ 

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:

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

$ submit discrete pnc1 primeodds.c primesqrt.c primesqrtodds.c primesqrtopt.c primesqrtoptodds.c
Submitting discrete project "pnc1":
    -> primeodds.c(OK)
    -> primesqrt.c(OK)
    -> primesqrtodds.c(OK)
    -> primesqrtopt.c(OK)
    -> primesqrtoptodds.c(OK)

SUCCESSFULLY SUBMITTED

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.