Recursive power(x,n) function

bbto · #1 27-Jan-2009, 01:01

hi every one
i'm new to C++
i get a assignment that i need to wirte a recursive function for exponential
i wrote a silpme one, and it works, then the teacher ask me to modify it
she wrote this:

"The "simple" algorithm does n-1 multiplications but it is possible to compute x^n for n=16 in 4 multiplications. Modify your program to output also the value of counter. For x=2.0 and n=16, the output would be

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

Hint: One way to calculate x8 is to calculate x · x · x · x · x · x · x · x which takes 7 multiplications.
But x · x · x · x · x · x · x · x = (x · x · x · x)^2 = ((x · x)^2)^2 which can be computed with 3 multiplications."

but i try a so many time, still dont get it.
i need some help for this.

here is my code The "simple" algorithm she said..

CPP / C++ / C Code:

#include <iostream>

using namespace std;
int cnt=0;

double power(double x, int n);
//this function computes X^n recursively in fewer than n-1 multiplications

int main(){
    
    double base;
    int expo;
    double answer;
    
    cout << "This function computes a exponential( X^n )." << endl;
    cout << "please enter the base number: " << endl;
    cin >> base;
    cout << "please enter the exponent: " << endl;
    cin >> expo;
    
    answer = power(base, expo);
    
    cout << "X = " << base << endl;
    cout<< "n = " << expo << endl;
    cout << "X^n = " << answer << endl;
    cout << "Mulitilication: "<< cnt << endl;
    system("PAUSE");
}

double power(double x, int n){
       
       if(n > 0){
            cnt++;
            return x * (power(x,n-1));
       }
       else{
           cnt--; 
           return 1;
       }
}

bbto · #2 27-Jan-2009, 03:15

i can't edit my post, so i reply my new update
i can now do the 2^8 in 3 muliti.
but still can't do 2^16 in 4 muliti..

here is the new code

CPP / C++ / C Code:

#include <iostream>

using namespace std;
int cnt=0;

double power(double x, int n);
//this function computes X^n recursively

int main(){
    
    double base;
    int expo;
    double answer;
    string ans;
    
    cout << "This function computes a exponential( X^n )." << endl;
    do{
       cnt = 0;
       cout << "please enter the base number: ";
       cin >> base;
       cout << "please enter the exponent: ";
       cin >> expo;
    
       answer = power(base, expo);
       
       //cout << endl;
       cout << "X = " << base << "\t";
       cout << "n = " << expo << "\t";
       cout << "X^n = " << answer << "\t";
       cout << "Mulitilication: "<< cnt << "\t" << endl;
       cout << "Do you want to perform it again?(y,n): ";
       cin >> ans;
    }while(ans == "y" ||ans == "Y");
}

double power(double x, int n){
       double result=x; 
       
       if(n > 0){             //positive exponent
            result *= x;
            cnt++;
            return result * (power(x,n-2));
       }
       else if (n ==0){       //when exponent is 0, then result will always 1
           cnt--; 
           return 1;
       }
       else{                  //negative exponent
            cnt++;
            return (1/x) * (power(x,n+1));
       }
}

Blake · #3 27-Jan-2009, 09:14

Here's a hint (I'm not going to give away the answer since it's a school assignment).

(Notation: By x^y, I mean x to the y power, not the bitwise XOR operator).

CPP / C++ / C Code:

double power(double x, int n)
{
  if (n < 0)
  {
    // negative exponent.  Use a recursive call to compute (1/x)^(-n) and return the result.
  }
  else if(n)
  {
    cnt++;
    // n > 0.  Two cases.
    // 1. n is even: Then x^n = (x^(n/2))^2, so compute x^(n/2) with a recursive call, and return the square of the result.
    // 2. n is odd: Then x^n = x*x^(n-1), so use a recursive call to compute x^(n-1), and return the result muliplied by x.
    // To test if x is odd, you can use the bitwise AND operator: 
    if (x & 1)
    {
      // odd case
    }
    else
    {
      // even case
    }
  }
  else
  {
    // n = 0
    return 1.0;
  }
}

Thread Tools	Search this Thread
Show Printable Version Email this Page	Search this Thread: Advanced Search
Rate This Thread
Rate This Thread:

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
run script command on ns2.26	newbie06	Computer Software Forum - Linux	65	19-Aug-2009 08:50
Flex and bison coding	lucky88star	C++ Forum	5	24-Dec-2007 12:57
Need Help with input files.	Efferus	C++ Forum	2	24-Nov-2007 17:19
recursive function for perfect numbers?	cancan	C Programming Language	6	19-Nov-2007 12:46
[Include] Doubly-linked List	dsmith	C Programming Language	6	14-Apr-2006 14:12

Recursive power(x,n) function

Re: recursive power(x,n) function

Re: Recursive power(x,n) function