GIDForums  

Go Back   GIDForums > Computer Programming Forums > C++ Forum
User Name
Password
Register FAQ Members List Calendar Search Today's Posts Mark Forums Read
 
 
Thread Tools Search this Thread Rate Thread
  #1  
Old 27-Jan-2009, 00:01
bbto bbto is offline
New Member
 
Join Date: Jan 2009
Posts: 2
bbto is on a distinguished road

Recursive power(x,n) function


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;
       }
}
  #2  
Old 27-Jan-2009, 02:15
bbto bbto is offline
New Member
 
Join Date: Jan 2009
Posts: 2
bbto is on a distinguished road

Re: recursive power(x,n) function


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));
       }
}
  #3  
Old 27-Jan-2009, 08:14
Blake's Avatar
Blake Blake is offline
Regular Member
 
Join Date: Nov 2005
Posts: 376
Blake is a jewel in the roughBlake is a jewel in the roughBlake is a jewel in the rough

Re: Recursive power(x,n) function


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;
  }
}
__________________
www.blake-foster.com
 


Thread Tools Search this Thread
Search this Thread:

Advanced Search
Rate This Thread
Rate This Thread:

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

vB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Forum Jump

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

Network Sites: GIDNetwork · GIDApp · GIDBlog · Learning Journal by J de Silva, The

All times are GMT -6. The time now is 10:37.


vBulletin, Copyright © 2000 - 2014, Jelsoft Enterprises Ltd.