QuestionQuestion

Transcribed TextTranscribed 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.

Solution PreviewSolution Preview

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;
};...
$25.00 for this solution

PayPal, G Pay, ApplePay, Amazon Pay, and all major credit cards accepted.

Find A Tutor

View available C-Family Programming Tutors

Get College Homework Help.

Are you sure you don't want to upload any files?

Fast tutor response requires as much info as possible.

Decision:
Upload a file
Continue without uploading

SUBMIT YOUR HOMEWORK
We couldn't find that subject.
Please select the best match from the list below.

We'll send you an email right away. If it's not in your inbox, check your spam folder.

  • 1
  • 2
  • 3
Live Chats