## Transcribed Text

Computing Powers
Suppose that we want to compute x" (where n is a non-negative integer). Let's also suppose that we want
to know the cost of doing so, with an eye towards minimizing the cost when n is large. To be definite, let's
suppose that we measure the cost of this computation by the number of multiplications that are performed.
There are (at least) three ways to approach this problem:
(1) You can use a simple iteration, which uses repeated multiplications, i.e.,
accurences of .
x^ r.x.x
We can refine this a bit: since x = 1 and 1.1 = x, you don't need to do any multiplications at all unless
n = 2. Then the cost of this algorithm is max[n - 1.0}.
(2) You can use a naive tail recursion:
1
if O,
x\
=
x
if 1.
x.xx-
otherwise (i.e., if n 2).
The cost of this algorithm is the same as that of the simple iteration in (1).
(3) You can use a divide and conquer strategy:
if O.
x
if 1.
x^
=
(x**/2)2
if is even,
x (1-0-1)/2)2 otherwise (i.e., if n 2 is odd).
For example, if you were to use this strategy when computing x1024. you would be doing 10 successive
squarings, so that the cost would be 10 multiplications, rather than the 1023 multiplications needed by
the first two algorithms. In general, the cost of this algorithm is roughly log2 n, which is exponentially
better than the cost of the first two algorithms.
Your task is to implement these three algorithms, as functions power1 (), power2 (), and powe :3 (),
respectively. The prototype of power () is
template
T power1 (T x, unsigned int n, unsigned inta mults);
Since a template is being used, this function can be used with any numerical type (int, double, and so
forth). This function will assume that n > Oas a precondition; the return value of this function will be x"
The parameter mult will count the number of multiplications that power? () uses when computing x":
the simplest way to dothis is to increment mult each time you doa multiplication
The prototypes of the recursive functions power2 () and power3 () are similar. Note that when
computing mults, you'll need touse the value returned from any recursive calls, which should be updated
in the same way as for power1 ()
This program should be written as a single file proj1 cc, within an appropriate subdirectory of your
private directory.
Once you are totally satisfied with your program (regarding its documentation, correctness, and style),
dothe following:
1. Make a clean photo-script, called typescript, consisting of the following commands and their
output:
cat projl.cc
g++-Wall -o projl proj1 CC
projl
2. Once you've created the photo-script, run the command
photo-clean typescript > proj1 out
to create a clean version of the photo-script. If you get an error message indicating that proj1 out
exists, you should delete said file and do this again. To play it safe, examine the file proj1 out
(say, with the more) command, to make sure it's what you really want to send me.

This material may consist of step-by-step explanations on how to solve a problem or examples of proper writing, including the use of citations, references, bibliographies, and formatting. This material is made available for the sole purpose of studying and learning - misuse is strictly forbidden.

#include <cstdlib>

#include <iostream>

using namespace std;

// Functions

/**

* Iterative function to compute a power x<sup><em>n</em></sup>.

* a simple iteration, which uses repeated multiplications

* @param x the base

* @param n the exponent

* @param mults number of multiplications used, initially zero

* @return x<sup><em>n</em></sup>

* @pre n >= 0

* @post mults is the total number of multiplications used

*/

template <class T>

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

T result = (T)1;

for(mults = 0; mults < n ;mults++){

result *= x;

}

return result;

};...