Also the stopwatch.hpp is what provides the timer and stuff; I dunno why it's .hpp -- was provided that way. Would provide but it won't compile on a windows machine anyway and I don't feel like uploading it. If you want it that bad, I can give it to you, but it still won't compile on a windows machine due to using linux includes. I provided main.cpp and run.bash (linux terminal script).
main.cpp
Click here to see the hidden message (It might contain spoilers)
Code: Select all
/******************************************************************************
Steven A. Wilson (Alex)
CS 315 - Algorithm design
sawils0@engr.uky.edu
19 Feb 2008
This program is designed to compare various algorithm implementations
for the algorithm
a(n) = a(n-2) + a(n-3)
Where a(0) = 3, a(1) = 0, a(2) = 2
Results:
Fastest - EXPONENTIATION, ITERATIVE, MEMOIZATION, RECURSIVE - slowest
The various implementations are recursive, memoization, iterative,
and fast exponentiation by squaring.
Usage: <iterative/recursive/memoized/exponentiation> <n> [NUMBER_OF_RUNS]
Usage: <iterative/recursive/memoized/exponentiation> <n> [NUMBER_OF_RUNS]
Where n is the nth # the program should find, and NUMBER_OF_RUNS is the number
of times the program should repeat. This program compiles multiple executables
represented in the < >'s. Run the appropriate filename to run the corresponding
algorithm.
This source uses conditional compiling. To choose which method to compile,
define
ALGORITHM_TYPE 1
to compile recursive
ALGORITHM_TYPE 2
to compile memoization
ALGORITHM_TYPE 3
to compile iterative
ALGORITHM_TYPE 4
to compile fast exponentiation
as a compile-time flag. Alternatively, modify this source file.
If no type is defined, ALGORITHM_TYPE defaults to 1.
This determines which version of algorithm(int a) is compiled.
This program terminates with EXIT_FAIL on a fail. On success, the program
ends with EXIT_SUCCESS, after outputting the results to "[type]_results".txt
The results file format is as follows:
<which number> <final value> <total calls> <average time> <theoretical time>
References:
Based off of http://www.cs.uky.edu/~jurek/cs315/cs315s08/pa/utilities/315-example/fib.cc
For additional, more up-to-date information, see README
******************************************************************************/
#include "stopwatch.hpp"
#include <cstdlib>
#include <iostream>
#include <iomanip>
using namespace std;
unsigned long int calls = 0;
//Default type is recursive
#ifndef ALGORITHM_TYPE
#define ALGORITHM_TYPE 1
#endif
//Algorithm: a(n) = a(n-2) + a(n-3)
// a(0) = 3, a(1) = 0, a(2) = 2
//Returns solution for a(n) using various implementations depending on
// preprocessor definitions.
unsigned long int algorithm(size_t n);
//Returns theoretical time for a(n) depending on preprocessor definition.
unsigned long int theoreticalTime(size_t n);
int main(int argc, const char* argv[] ) {
if (argc != 2 && argc != 3) {
cout << "Usage: " << argv[0] << " <number to find> [number of runs]" << endl;
return EXIT_FAILURE;
}
unsigned long int NUMBER_OF_RUNS = 1;
if (atoi(argv[1]) < 0) {
cout << "N must be greater than or equal to zero." << endl;
return EXIT_FAILURE;
}
unsigned long int n = atoi(argv[1]);
unsigned long int a;
//If a # of runs is specified and it's valid, set it.
if (argc == 3) {
if (atoi(argv[2]) <= 0) {
cout << "# of runs must be greater than zero." << endl;
return EXIT_FAILURE;
}
NUMBER_OF_RUNS = atoi(argv[2]);
} else {
if (n <= 20)
NUMBER_OF_RUNS = 1000; //Get some sort of actual processing time out of it.
}
//Time is the whole purpose here...
stopwatch_t timer;
timer.start();
for (unsigned long int i = 0;i < NUMBER_OF_RUNS;i++) {
a = algorithm(n);
}
timer.stop();
//Output
cout.setf(ios::scientific);
cout << setw(15) << n
<< setw(15) << a
<< setw(15) << calls/NUMBER_OF_RUNS //NUMBER_OF_RUNS is used as a scale
<< setw(15) << timer.userTime()/NUMBER_OF_RUNS
<< setw(15) << timer.userTime()/theoreticalTime(NUMBER_OF_RUNS)
<< endl;
return EXIT_SUCCESS;
}
#if ALGORITHM_TYPE == 1 //recursive
//Algorithm: a(n) = a(n-2) + a(n-3)
// a(0) = 3, a(1) = 0, a(2) = 2
//Solves for a(n) recursively.
//Precondition: ALGORITHM_TYPE defined as 1
//Postcondition: a(n) result is returned.
unsigned long int algorithm(size_t n) {
calls++;
//Base cases
if (n == 0)
return 3;
if (n == 1)
return 0;
if (n == 2)
return 2;
//Recursive case
return (algorithm(n-2) + algorithm(n-3));
}
//T(n) = T(n-2) + T(n-3) + 1
//size of first subproblem is n - 2, size of 2nd subproblem is n-3.
//therefore the running time of a problem of size n is the running time
//of the problem of size n-2 plus the problem of size n-3 plus the time
//for merge (one addition)
unsigned long int theoreticalTime(size_t n) {
if (n <= 2)
return 1;
return theoreticalTime(n-3) + theoreticalTime(n-2) + 1;
}
#elif ALGORITHM_TYPE == 2 //memoization
#include <vector>
vector<unsigned long int> results;
//Algorithm: a(n) = a(n-2) + a(n-3)
// a(0) = 3, a(1) = 0, a(2) = 2
//Solves for a(n) using memoization.
//PRE: ALGORITHM_TYPE is 2
//POST: Returns solution for a(n) through calculations & lookup (memoization)
unsigned long int algorithm(size_t n) {
calls++;
if (n == 0)
return 3;
if (n == 1)
return 0;
if (n == 2)
return 2;
if (results.size() < n+1)
results.resize(n+1);
if (results[n] == 0 && n != 1) //results[n] is not defined (also n == 1 is 0)...
results[n] = algorithm(n-2) + algorithm(n-3); //^ elements are initialized to 0 by definition
return results[n];
}
//The algorithm is solved n times only; each n solve has a lookup of n-3 and n-2
unsigned long int theoreticalTime(size_t n) {
if (n <= 2)
return 1;
return n-2 + n-3;
}
#elif ALGORITHM_TYPE == 3 //iterative
//Algorithm: a(n) = a(n-2) + a(n-3)
// a(0) = 3, a(1) = 0, a(2) = 2
//PRE: ALGORITHM_TYPE is defined as 3.
//POST: Solves a(n) through iteration.
unsigned long int algorithm(size_t n) {
calls++;
unsigned long int current = 3; //a(3) / a(n)
unsigned long int last1 = 2; //a(2) / a(n-1), unused in algorithm; temporary storage only
unsigned long int last2 = 0; //a(1) / a(n-2)
unsigned long int last3 = 3; //a(0) / a(n-3)
//Special cases (n == 3 is taken care of as it is returned as current)
if (n == 0)
return last3;
if (n == 1)
return last2;
if (n == 2)
return last1;
for (unsigned int i = 4;i <= n;++i) {
//Move everything down a notch
last3 = last2;
last2 = last1;
last1 = current;
current = last2 + last3; //(Algorithm implementation)
}
return current;
}
//the cost is n-3 additions + 3 reassignments
//Master theorem: (0 subproblems, n-3 + 3 work done outside)
//Returns theoretical time for iterative version of a(n).
unsigned long int theoreticalTime(size_t n) {
return (n-3) + 3;
}
#elif ALGORITHM_TYPE == 4 //fast exponentiation
//const int reduction = 10000; //used for mod operation to limit overflow
//Solves for a(n) using fast exponentiation
//PRE: ALGORITHM_TYPE is 4
//POST: result, a 3 high 1 wide array, contains the answer in
// midresult[2] (0-based).
//Matrix multiplication is based on
// http://www.devarticles.com/c/a/Cplusplus/Operator-Overloading-in-C-plus/4/
unsigned long int algorithm(size_t n) {
calls++;
unsigned long int a[3][3]; //height x width; values are given.
unsigned long int midresult[3][3];
unsigned long int p[3] = {2, 0, 3};
unsigned long int final[3] = {0, 0, 0};
//Set these to zero so that when we add with the += it comes out right
unsigned long int temp[3][3] = {{0, 0, 0}, {0, 0, 0}, {0, 0, 0}};
unsigned long int tempb[3][3] = {{0, 0, 0}, {0, 0, 0}, {0, 0, 0}};
//Initialize the a array per specification.
a[0][0] = 0; a[0][1] = 1; a[0][2] = 1;
a[1][0] = 1; a[1][1] = 0; a[1][2] = 0;
a[2][0] = 0; a[2][1] = 1; a[2][2] = 0;
//Create an midresult array to use pow with; intitialize to identity
midresult[0][0] = 1; midresult[0][1] = 0; midresult[0][2] = 0;
midresult[1][0] = 0; midresult[1][1] = 1; midresult[1][2] = 0;
midresult[2][0] = 0; midresult[2][1] = 0; midresult[2][2] = 1;
while (n) { //Raise A to the power of n
//Based off of http://en.wikipedia.org/wiki/Exponentiation_by_squaring
if (n & 1) { //Even/odd test
//Multiply result by A; store in temp to avoid overwriting
for (int r = 0;r < 3;r++)
for (int c = 0;c < 3;c++)
for (int i = 0;i < 3 ;i++)
temp[r][c] += (midresult[r][i] * a[i][c]);
//Transfer temp back to "midresult" (quicker w/o a loop, which involves additions)
midresult[0][0] = temp[0][0]; midresult[0][1] = temp[0][1]; midresult[0][2] = temp[0][2];
midresult[1][0] = temp[1][0]; midresult[1][1] = temp[1][1]; midresult[1][2] = temp[1][2];
midresult[2][0] = temp[2][0]; midresult[2][1] = temp[2][1]; midresult[2][2] = temp[2][2];
//Reset temp (quicker w/o a loop, which involves additions)
temp[0][0] = 0; temp[0][1] = 0; temp[0][2] = 0;
temp[1][0] = 0; temp[1][1] = 0; temp[1][2] = 0;
temp[2][0] = 0; temp[2][1] = 0; temp[2][2] = 0;
n--;
}
//Square "A"
for (int r = 0;r < 3;r++)
for (int c = 0;c < 3;c++)
for (int i = 0;i < 3 ;i++)
tempb[r][c] += (a[r][i] * a[i][c]);
//Transfer result back to "A" (quicker w/o a loop, which involves additions)
a[0][0] = tempb[0][0]; a[0][1] = tempb[0][1]; a[0][2] = tempb[0][2];
a[1][0] = tempb[1][0]; a[1][1] = tempb[1][1]; a[1][2] = tempb[1][2];
a[2][0] = tempb[2][0]; a[2][1] = tempb[2][1]; a[2][2] = tempb[2][2];
//Reset tempb (quicker w/o a loop, which involves additions)
tempb[0][0] = 0; tempb[0][1] = 0; tempb[0][2] = 0;
tempb[1][0] = 0; tempb[1][1] = 0; tempb[1][2] = 0;
tempb[2][0] = 0; tempb[2][1] = 0; tempb[2][2] = 0;
n = n/2;
}
//Create the final result by multiplying midresult (A^n) by p
for (int r = 0;r < 3;r++)
for (int i = 0;i < 3 ;i++)
final[r] += (midresult[r][i] * p[i]);
//The result is the final space in final matrix
return final[2];
}
//Returns the theoretical time for a(n) - logarithmic time
//Two subproblems, both of size n/2. 9 mults per subproblem. 9 adds per subproblem.
//Final Reassembly involves 3 mults and 3 adds.
unsigned long int theoreticalTime(size_t n) {
if (n <= 1)
return 2*(9 + 9); //Base subproblem involves 9 mults & 9 adds
return 2*theoreticalTime(n/2) + 6;
}
#endif //end algorithm_type====
run.bash
Click here to see the hidden message (It might contain spoilers)
Code: Select all
#!/usr/bin/env bash
# AUTHOR Steven A Wilson
# FOR CS 315, Program 1
# DUE 19 Feb 2008
# Slightly modified from sample on assignment 1 utilities webpage.
# Run gnuplot to generate a line graph from the specified file.
# The parameters are: file, title, y-axis label, using declaration.
# Produces a PS to standard output.
function gplot {
file=$1
title=$2
ylabel=$3
using=$4
gnuplot <<EOF
set terminal postscript color
set ylabel "${ylabel}"
set xlabel "n"
set autoscale
plot [:] [:] "${file}" using 1:(${using}) title "${title}" with lines
EOF
}
# Note that the first two arguments are positional parameters,
# while the fourth is a literal '$3'.
# To use a different column, change the fourth argument.
function gplot-calls {
gplot "$1" "$2" calls '$3'
}
function gplot-time {
gplot "$1" "$2" sec '$4'
}
function gplot-ratio {
gplot "$1" "$2" "sec/call" '$4/$3'
}
function gplot-theo {
gplot "$1" "$2" "time/theoretical" '$4/$5'
}
# Compile the program if necessary
make
echo "Running iterative"
(for ((i=0; i<40; i=i+8)); do ./iterative ${i}00000 5; done) > iterative.out
cat iterative.out
echo "Running recursive"
(for ((i=0; i<75; i=i+15)); do ./recursive ${i} 5; done) > recursive.out
cat recursive.out
echo "Running memoized"
(for ((i=0; i<10; i=i+2)); do ./memoized ${i}0000 5; done) > memoized.out
cat memoized.out
echo "Running exponentiation"
(for ((i=0; i<40; i=i+8)); do ./exponentiation ${i}00000 500; done) > exponentiation.out
cat exponentiation.out
for i in iterative recursive memoized exponentiation; do
gplot-calls "${i}.out" "${i} calls" > "${i}.calls.ps"
gplot-time "${i}.out" "${i} runtime" > "${i}.time.ps"
gplot-ratio "${i}.out" "${i} runtime per call" > "${i}.ratio.ps"
gplot-theo "${i}.out" "${i} runtime vs theoretical runtime" > "${i}.theo.ps"
done
Edit: I had the wrong run.bash version. Fixed.
Edit2: Added the following [(the called pstopdf executable is supplied by professor)]
topdf.bash
Click here to see the hidden message (It might contain spoilers)
Code: Select all
#!/usr/bin/env bash
# NAME Steven A Wilson (Alex)
# FOR CS 315 Program 1
# DUE 19 Feb 2008
# DESCRIPTION
# This makes pdf's out of ps files.
if [[ $1 == "help" ]]
then
echo "This program makes pdfs out of ps files."
echo "Usage: [] or [rm-ps] or [rm-pdf] or [rm-all]"
exit
fi
if [[ $1 = "rm-all" ]]
then
$0 rm-ps
$0 rm-pdf
exit
fi
if [[ $1 = "rm-ps" ]]
then
echo "Removing *.ps"
rm -rf *.ps
echo "All done!"
exit
fi
if [[ $1 = "rm-pdf" ]]
then
echo "Removing *.pdf"
rm -rf *.pdf
echo "All done!"
exit
fi
echo "Creating pdf's from .ps files."
for arg in *.ps
do
echo "Creating pdf for $arg"
pstopdf $arg
done
echo "All done! Use 'rm-ps' or 'rm-pdf' or 'rm-all' to rm appropriate filetypes."
Hardly anybody uses hpp, though, so yeah, dumb.