proj1.cc File Reference

#include <iostream>

Include dependency graph for proj1.cc:

Functions
template<class T >
T	power1 (T x, unsigned int n, unsigned int &mults)
	Iterative function to compute a power xn. More...
template<class T >
T	power2 (T x, unsigned int n, unsigned int &mults)
	Naive recursive function to compute a power xn. More...
template<class T >
T	power3 (T x, unsigned int n, unsigned int &mults)
	Divide-and-conquer recursive function to compute a power xn. More...
template<class T >
void	printReport (T base, unsigned int pow, T result1, T result2, T result3, unsigned int mults1, unsigned int mults2, unsigned int mults3)
	Report the results of three different exponentiation calculations. More...
int	main ()
	The usual main function. More...

Function Documentation

int main

(

)

The usual main function.

It computes the powers 2ⁱ for i=0,1,2,..,32 via all three methods, reporting the number of multiplications needed for each method. (Note what happens for 2³².) It then does likewise for 0.5ⁱ, but now with i=0,1,2,...64

template<class T >

T power1	(	T	x,
		unsigned int	n,
		unsigned int &	mults
	)

Iterative function to compute a power xⁿ.

Parameters

x	the base
n	the exponent
mults	number of multiplications used, initially zero

Returns

xⁿ

Precondition

n >= 0

Postcondition

mults is the total number of multiplications used

template<class T >

T power2	(	T	x,
		unsigned int	n,
		unsigned int &	mults
	)

Naive recursive function to compute a power xⁿ.

Computes xⁿ as x*x^n-1.

Parameters

x	the base
n	the exponent
mults	total of multiplications used, which is assumed to have been correctly set by any previous recursive call

Returns

xⁿ

Precondition

n >= 0

Postcondition

mults is the new number of multiplications used

template<class T >

T power3	(	T	x,
		unsigned int	n,
		unsigned int &	mults
	)

Divide-and-conquer recursive function to compute a power xⁿ.

If the exponent is even, the result is simply the square of x^n/2; if the exponent is even, then the result is x, multiplied by the square of x^(n-1)/2.

Parameters

x	the base
n	the exponent
mults	total of multiplications used, which is assumed to have been correctly set by any previous recursive call

Returns

xⁿ

Precondition

n >= 0

Postcondition

mults is the new number of multiplications used

template<class T >

void printReport	(	T	base,
		unsigned int	pow,
		T	result1,
		T	result2,
		T	result3,
		unsigned int	mults1,
		unsigned int	mults2,
		unsigned int	mults3
	)

Report the results of three different exponentiation calculations.

If the three results differ, then all three are printed out, with a warning message. If all three results are the same, the result is printed, along with the number of multiplications used by each of the three algorithms.

Parameters

base	the number whose power we seek
pow	the power
result1	the result of using power1 to compute basepower
result2	the result of using power2 to compute basepower
result3	the result of using power3 to compute basepower
mults1	the number of multiplications used by power1
mults2	the number of multiplications used by power2
mults3	the number of multiplications used by power3

Precondition

pow>=0

result1, result2, result3 are as described in the parameter section

Postcondition

none