Write a C++ function power(x,n) that computes x n recursively in fewer than n-1

Question

Write a C++ function power(x,n) that computesxn recursively in fewer thann-1 multiplications. Your program should read as input thevalue of x and n from standard input and it should print out thevalues of x, n, and xn.. For example,for input x=2.0, n=5 the output could be

   x = 2    n = 5   x^n =32

Test your function for x=2.0 and x=-2.0, n=5,6,7,8,9,10.

The function declaration (function prototype) to your C++ functionshould look like this:

double power(double x, int n);

The function power that you define must berecursive.

Once your function is working, use a global variablemultiplications to count the number of multiplications that yourfunction power does. The "simple" algorithm does n-1 multiplications but it is possible to computexn for n=16 in 4 multiplications. Modify your program tooutput also the value of multiplications. For x=2.0 andn=16, the output would be

   x = 2    n = 16    x^n = 65536      multiplications =4

Hint: One way to calculate x8is to calculate x · x · x · x· x · x · x · x which takes7 multiplications.
But x · x · x · x · x· x · x · x = (x · x · x· x)2 = ((x ·x)2)2 which can becomputed with 3 multiplications.

Explanation / Answer

#include<iostream.h> #include<conio.h> double power(double x, int n); int main() { double x; int n; cout<<"Enter the value of X="; cin>>x; cout<<" Enter the value of N="; cin>>n; double result=power(x,n); cout<<"="<<x<<" n="<<n<<"x^n="<<result; getch(); return 0; } double power(double x,int n) { if(n==1) return x; else { double val=x*power(x,n-1); return val; } }
for counting how many timesmultiplied
#include<iostream.h> #include<conio.h> double power(double x, int n); int multiply=0; int main() { double x; int n; cout<<"Enter the value of X="; cin>>x; cout<<" Enter the value of N="; cin>>n; double result=power(x,n); cout<<"="<<x<<" n="<<n<<"x^n="<<result<<"Multiplication="<<multiply; getch(); return 0; } double power(double x,int n) { multiply++; if(n==1) return x; else { double val=x*power(x,n-1); return val; } }

#include<iostream.h> #include<conio.h> double power(double x, int n); int multiply=0; int main() { double x; int n; cout<<"Enter the value of X="; cin>>x; cout<<" Enter the value of N="; cin>>n; double result=power(x,n); cout<<"="<<x<<" n="<<n<<"x^n="<<result<<"Multiplication="<<multiply; getch(); return 0; } double power(double x,int n) { multiply++; if(n==1) return x; else { double val=x*power(x,n-1); return val; } }

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.