CSE2383 Programming Assignment 1, version 1.2 Page 1

Algorithm Analysis

Objective

The objective of this programming assignment is to present the student with a C++ introduction assignment with a more challenging problem to solve than the basic practice tasks given in regular homework assignments. This assignment also attempts to illustrate the differences in running times for algorithms that perform the same task: finding prime numbers smaller than a given integer.

Instructions

Implement a program that asks the user for an integer n, which method (trial division or sieve of Eratosthenes) to use, and whether the prime numbers should be printed to the screen. The program should then find all of the prime numbers smaller than n using the selected method and print the time taken by the algorithm. There is a timer class and example program attached to this assignment. During testing of your program use the option to print the prime numbers found by the algorithms to the screen for verification.

Finding prime values by Trial Division

To decide if a number is prime using trial division, try dividing the number by all integers between 2 and the square root of the number. If there is a remainder from all of the division operations, the number is prime. You will test each integer less than n using this process to create a list of all the prime numbers less than n.

Finding prime values by Sieve of Eratosthenes

The following excerpt for finding prime numbers using the Sieve of Eratosthenes algorithm is from http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes (it is important that you view this page to get a better idea on what the algorithm does):

To find all the prime numbers less than or equal to a given integer n by Eratosthenes' method:

1. Create a list of consecutive integers from 2 to n: (2, 3, 4, ..., n).

2. Initially, let p equal 2, the first prime number.

3. Starting from p, count up in increments of p and mark each of these numbers greater than p itself in the list. These numbers will be 2p, 3p, 4p, etc.; note that some of them may have already been marked.

4. Find the first number greater than p in the list that is not marked; let p now equal this number (which is the next prime).

5. If there were no more unmarked numbers in the list, stop. Otherwise, repeat from step 3.

When the algorithm terminates, all the numbers in the list that are not marked are prime.

Run your program for different values of n (at least 10) and record the times taken for finding the prime numbers smaller than n. Recorded times should be distinct and non-zero. For the analysis questions below, use the timings of your program execution that does not print the prime values to the screen.

CSE2383 Programming Assignment 1, version 1.2 Page 2

Choose values of n such that valid timings (greater than 0 seconds) are found and choose an increment between the values of n such that your times for each n are not the same. You must report timings for 10 different values of n for each method of finding prime numbers.

NOTE: for the sake of debugging your code, choose trivial values of n (e.g. 25 to 32 or smaller) so that your code can finish its search quickly. For actual timing runs, choose larger values of n such that a difference in execution between the two algorithms can be observed. Be aware that some values of n may result in very long execution times (i.e., several minutes to hours). Therefore, it is important for you to complete writing the program in enough time to allow for adequate timing analysis runs.

Files and starter code

Below is a list of files and/or starter code that is provided with this assignment. If these files are not provided, notify your instructor immediately. The list below may also include a small description on what each files does (or provides); the list may elect to refer you to the comments provided within the file itself.

The following files are included in the compressed file, student_files.zip:

timer.h and testTimer.cpp

A timer class that you will use to perform your timing analysis. The file testTimer.cpp provides an example of how to include this file into you program, create an object of the timer class, and then use its timing methods to perform a timing analysis

prime.cpp

Starter code that includes the dynamic allocation of an array (using a pointer), and the signatures of the functions that will implement your two algorithms; the functions receive an array as an argument. You do not need to know the details on how to use dynamic memory, pointers, or how arrays are passed to functions to complete this assignment. See code comments for further details.

prime.cpp

#include

// the following directive allows you to use the user-defined class called Timer #include "timer.h"

using namespace std;

/*** Clarifying Comments ******************************************************* * The below two lines are the function signatures of the algorithms that you are * supposed to implement. The parameter array[] accepts an array as an argument * (see prime in the main function). Passing an array as an argument to a * function passes a reference (actually pointer) to the original array and * allows the function to modify the contents of the passed array; this is * similar to how lists are handled when passing them as arguments to a * function in Python. For example if you pass in prime as an argument to * sieveErat, and if you change the value array[4] inside of the sieveErat, * function the change will be made to prime[4] since array is constant pointer * to the first element in prime. * * parameter NUM is the number n you retrieved from the user * parameter SIZE is the size of the array. * * Note: both algorithms fill an array with all the found prime values. Since the * array[] parameter modifies the original passed argument you can use it to * store your found values into the prime array * * Note: the Trial Division algorithm will require you to find the square root of * a value. The C++ function that computes the square root of a number is sqrt() * look up the sqrt function and the library that should be included in the C++ * reference at http://en.cppreference.com/w/ * *******************************************************************************/ void trialDivision(int array[], const int NUM, const int SIZE); void sieveErat(int array[], const int NUM, const int SIZE);

int main() { int *prime; // a pointer that will be used to create an array at run time int size = 0; // variable that would be used to set the size of the array Timer myTimer; // a Timer class object that you will use to time your algorithms

/*** Your Code ********************************************* * place your code that asks for user input here. you are * going to need this value to set the size of prime array * as well as the number n and selected algorithm * * Note: when setting the variable size, it should be * at least twice the value of the number n you received * from the user ***********************************************************/

/*** Clarifying Comments ***************************************************** * the following statement creates an array using dynamic memory allocation. * IT IS NOT NECESSARY FOR YOU TO KNOW EITHER POINTERS OR HOW TO CREATE AN * ARRAY USING DYNAMIC MEMORY ALLOCATION TO COMPLETE THIS ASSIGNMENT. The * array created is named "prime" and its capcity is set to the value of the * size variable. Make sure the value, received by the user, that is assigned * to size is a non-zero value. * * Note: regardless of how it is created, prime is an array and can be used like * a regular array, that is, you can assign values to prime using an index, * for example: * * prime[3] = 7; * * and you can also read from the array using an index: * * cout << prime[3]; * prime[2] = prime[1] + prime[0] * cout << prime[2]; *****************************************************************************/ prime = new int[size];

/*** Your Code ********************************************* * place your code that times the execution of the algorithms * implemented by trialDivision() and sieveErat() ***********************************************************/

/*** Clarifying Comments ***************************************************** * for all things created using dynamic memory, you should also free up the * that memory when done using it (see the following statement). *****************************************************************************/ delete [] prime; return 0; }

/*** Your Code ***************************************************************** * Here is where you can define the functions that implement the Trial Division * and Sieve of Eratosthenes algorithms. You may choose to give the signatures * above main() bodies, or leave the signatures in place and define the functions * here. *******************************************************************************/

timer.h

// Timer.h documents a simple, platform-independent interval timer // that measures CPU usage in (fractional) seconds. // // Author: Joel Adams, for Hands On C++. // Date: November 1997 // // Revision History // // Seconds() added - kvlinden, 5-Feb-98 // // ANSI compliance, interface improvements // - Adams, March, 1998. //

#ifndef TIMER #define TIMER

#include // ostream #include // C time library: clock_t, clock(), CLOCKS_PER_SEC using namespace std;

class Timer { public: Timer(); void Start(); void Stop(); void Reset(); double Clocks() const; double Seconds() const; void Print(ostream & out) const;

private: clock_t myStartTime; clock_t myRunTime; bool running; };

//*************************************************************** // Timer constructor. * // Postcondition: myStartTime == 0 && myRunTime == 0 && * // running == false. * //*************************************************************** inline Timer::Timer() { myStartTime = myRunTime = 0; running = false; }

//*************************************************************** // Start myself. * // Postcondition: myStartTime == the current clock value && * // running == true. * // Note: Start() while I'm running re-starts me. * //*************************************************************** inline void Timer::Start() { running = true; myStartTime = clock(); }

//*************************************************************** // Stop myself. * // Precondition: running == true. * // Postcondition: myRunTime has been updated with time interval * // since the Timer was started && * // running == false. * // Note: Stop() only has an effect when I'm running. * //*************************************************************** inline void Timer::Stop() { if (running) { myRunTime += clock() - myStartTime; running = false; } }

//*************************************************************** // Reset myself. * // Postcondition: myStartTime is the current clock value && * // myRunTime == 0. * // Note: Reset() while I'm running re-starts me. * //*************************************************************** inline void Timer::Reset() { myRunTime = 0; myStartTime = clock(); }

//*************************************************************** // My current time value (in clocks) * // Return: the elapsed time since I was started. * // Note: If I'm not running: * // repeated calls to Clocks() return the same value. * // Otherwise: * // repeated calls to Clocks() return different values. * //*************************************************************** inline double Timer::Clocks() const { if (running) return double(clock() - myStartTime); else return double(myRunTime); }

//*************************************************************** // My current time value (in seconds) * // Return: the elapsed time since I was started. * // Note: If I'm not running: * // repeated calls to Seconds() return the same value. * // Otherwise: * // repeated calls to Seconds() return different values. * //*************************************************************** inline double Timer::Seconds() const { if (running) return double(clock() - myStartTime) / double(CLOCKS_PER_SEC); else return double(myRunTime) / double(CLOCKS_PER_SEC); }

//*************************************************************** // Output myself (function member). * // Receive: out, an ostream. * // Output: the time since I was started. * // Passback: out, containing the Timer output. * // Note: If I'm not running: * // repeated calls to Print() display the same value. * // Otherwise: * // repeated calls to Print() display different values. * //*************************************************************** inline void Timer::Print(ostream & out) const { out << Seconds(); }

//*************************************************************** // Output a Timer (operator<<) * // Receive: out, an ostream, * // aTimer, a Timer. * // Output: the value of aTimer via out. * // Passback: out, containing the time since aTimer was started. * // Return: out, for output chaining. * // Note: If I'm not running: * // repeated calls to << display the same value. * // Otherwise: * // repeated calls to << display different values. * //*************************************************************** inline ostream & operator<< (ostream & out, const Timer & aTimer) { aTimer.Print(out); return out; }

#endif

timerTest.cpp

#include "timer.h" #include #include #include

using namespace std;

int main() { Timer myTimer;

cout << "How long does it take to print 10 thousand numbers?" << endl; myTimer.Start();

for (int i=0; i<10000; i++) cout << i << " "; myTimer.Stop();

cout << endl << endl; cout << "That took " << myTimer.Clocks() << " clock ticks. " << endl; cout << "That took " << setprecision(10) << myTimer.Seconds() << " seconds. " << endl;

system("pause"); return EXIT_SUCCESS; }