Elysian Shadows

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

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

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