Hi developers :)

Actually, I'd like to introduce myself first, I'm Mohd. *Computer Engineer* still student :/

Actually, I really like this community, and I think I'll be active in the C++ section as I like it xDD

back to my question :) Please can anyone help me doing this code?
"How to implement a good to use this method (x^8) = ( x^4 )^2, (x^4) = (x^2)^2 and x^2 = x * x.
how to improve the code to do this? instead of using the recursion"

Here's what I did! and then got stuck@@ actually I don't know how can I find the plan to start!!

this is my code for now:

``````#include <iostream>

using namespace std;

// Function definition
int findPower ( int, int );

// Begin function main
int main()
{
int n;
int x;

cout << "Enter an integer: ";
cin >> x;

cout << "\nEnter the power 'n' (example: x^n): ";
cin >> n;

cout << endl;

if( n%2 == 0 )
{
for( int i = 1; i <= n; i++ )

return 0; // to indicate successfully termination

} // end main``````

first of all, I just initiate the function definition, thought I'll use a function as what we did in recursion.

by the way, it is written in the question (Hint: A special case is needed for odd exponents).

5
Contributors
22
Replies
23
Views
9 Years
Discussion Span
Last Post by Q8iEnG

So you want to do this without using recursion

Yes, absolutely

I want to use the method *the way* I mentioned up..

like if the user want the power of X^8

the program should use this method:
X^8 = (X^4)^2, X^4 = (X^2)^2, X^2 = X * X

any help?

So you want to do this without using recursion

No, of course with recursion but in the method I displayed!!

- So now you want to use recursion?
- What would be the output for an odd exponent? Say x^7?

No, of course with recursion but in the method I displayed!!

If you are using recursion, don't use the for-loop. You'll just want a single call to the function from main. You mentioned even versus odd exponents, but actually do you need the exponent to be a power of 2? Looks like you want to keep squaring the base in this recursive function. Please elaborate.

Well, I guess you didn't understand my question, i'm sorry for the non-good explain

Here's the full question I found it in my book:
"The algorithms for both versions of the power function given in this chapter are rather simpleminded. Is it really necessary to make eight multiplications to compute (X^8)?
It can be observed that X^8 = (X^4)^2, X^4 = (X^2)^2, X^2 = X * X; that is, only three multiplications are needed to find the value of (X^8). Using this observation, improve both algorithms for computing x^n.
Hint: A special case is needed for odd exponents."

that's the whole question, it is in the book Data Structures and Algorithms in C++ by A.Drozdek

the chapter is the Recursion.

I hope that is clean enough x\$

Please, I really need to solve it, it might come in my exam tomorrow! :'[

Say x^7?

that really doesnot a pain .

x^7 = X^3 * x^4 = ... ... ...

Well, I guess you didn't understand my question, i'm sorry for the non-good explain

Here's the full question I found it in my book:
"The algorithms for both versions of the power function given in this chapter are rather simpleminded. Is it really necessary to make eight multiplications to compute (X^8)?
It can be observed that X^8 = (X^4)^2, X^4 = (X^2)^2, X^2 = X * X; that is, only three multiplications are needed to find the value of (X^8). Using this observation, improve both algorithms for computing x^n.
Hint: A special case is needed for odd exponents."

that's the whole question, it is in the book Data Structures and Algorithms in C++ by A.Drozdek

the chapter is the Recursion.

I hope that is clean enough x\$

Please, I really need to solve it, it might come in my exam tomorrow! :'[

A special case is also needed for exponents that are not odd, but are not a power of 2. The example you cited is the easiest example and is pretty straightforward. 8 is a power of two. More complicated, but certainly doable, is anything that is not a power of 2. You can handle this in your recursive function though by simply checking for oddness of the exponent. Any exponent that is not a power of 2 will at some point be odd in your recursive function. I would suggest that you chart this out on paper exactly what the mathematics are behind this before starting to code. Here's a start for your recursive function:

``````int power(int base, int exp)
{
if (exp == 0)
return 1;
if(exp == 1)
return base;
if(exp % 2 != 0) // odd exponent
// return something

// return something
}``````

A special case is also needed for exponents that are not odd, but are not a power of 2. The example you cited is the easiest example and is pretty straightforward. 8 is a power of two. More complicated, but certainly doable, is anything that is not a power of 2. You can handle this in your recursive function though by simply checking for oddness of the exponent. Any exponent that is not a power of 2 will at some point be odd in your recursive function. I would suggest that you chart this out on paper exactly what the mathematics are behind this before starting to code. Here's a start for your recursive function:

``````int power(int base, int exp)
{
if (exp == 0)
return 1;
if(exp == 1)
return base;
if(exp % 2 != 0) // odd exponent
// return something

// return something
}``````

thanks a lot really appreciated :), actually that's the part I know :\

I need the part of the code, how to implement that method!!

I really need it,, thanks again you did really helped me in your words :)

waiting for the help! :]

``````#include <cstdlib>
#include <iostream>

using namespace std;

int main( )
{
int pow ( int, int ) ;
return EXIT_SUCCESS;
}

int pow ( int base, int power )
{
if ( power )
{
if ( power % 2 ) return base * pow( base, power-1 ) ;
return pow ( base * base, power/2 );
}
return 1 ;
}``````

This is a code I came up with. I must admit that I did not test it. I dont know if it will work with all cases ( 5 ^ -2 ). I am confident though that it will work with positive numbers unless ofcourse you give big values to crash the program. Hope you can build on this code to deal with all cases:)

It won't work!!
I used this code

``````#include <iostream>

using namespace std;

// Function definition
int pow( int, int );

// Begin function main
int main()
{
int n;
int x;
int get;

cout << "Enter an integer: ";
cin >> x;

cout << "\nEnter the power 'n' (example: x^n): ";
cin >> n;

get = pow( x, n );

cout << endl << get;

cout << endl;

return 0; // to indicate successfully termination

} // end main

int pow ( int base, int power )
{
if ( power >= 0 )
{
if ( power % 2 ) return base * pow( base, power-1 ) ;
return pow ( base * base, power/2 );
}

return 1 ;
}``````

when I execute it, and when I reach the step to write the power then click enter, it do nothing and the messege (click to continue) appears!!

Sorry, there's a little mistakes in the code up!!

I did corrected it, but I get wrong values!!
this is the new code

``````#include <iostream>

using namespace std;

// Function definition
int pow( int, int );

// Begin function main
int main()
{
int n;
int x;

cout << "Enter an integer: ";
cin >> x;

cout << "\nEnter the power 'n' (example: x^n): ";
cin >> n;

cout << pow( x, n );

cout << endl;

return 0; // to indicate successfully termination

} // end main

int pow ( int base, int power )
{
if ( power >= 0 )
{
if ( power % 2 == 0 )
return base * pow( base, power-1 ) ;

return pow ( base * base, power/2 );
}

return 1 ;
}``````

any suggestions?

if ( power > 0 ) is what i meant not >= 0. Now that you said it, I'll get rid of my laziness & check my code I shall reply soon if there is a change.

one more
if ( power % 2 != 0) & not power % 2 == 0

The code is working good for positive numbers as I thought.

``````int pow ( int base, int power )
{
if ( power )                                                          // if not 0
{
if ( power % 2 ) // if odd then 5^7 say == 5*5^6
return base * pow( base, power-1 ) ;
return pow ( base * base, power/2 ); // else if even, then the shortcut your book said
}
return 1 ;   // if 0 then return 1 since any^0 = 1 ;
}``````

Now, have I made myself clear?

Well, I did some mix codes between Prabakar's one and VernonDozeir's one
and it does work

``````#include <iostream>

using namespace std;

// Function definition
int pow( int, int );

// Begin function main
int main()
{
int n;
int x;

cout << "Enter an integer: ";
cin >> x;

cout << "\nEnter the power 'n' (example: x^n): ";
cin >> n;

cout << pow( x, n );

cout << endl;

return 0; // to indicate successfully termination

} // end main

int pow ( int base, int power )
{
if( power == 0 )
return 1;

if( power == 1 )
return base;

if( power % 2 == 0 )
return pow( base * base, power/2 );

return base * pow( base, power-1 );
}``````

but I just want to make sure that if it is as the same way the question want?

thanks :)

Thanks Prabakar :)

can you check the last code I inserted is it ok?

let me know, sorry for taking from your time :)

ya its right.

power == 1 will be handled by
return base * pow( base, power-1 );
so 2nd if though right, its not needed

I've edited the previous post have a look at it

curiously, Is it a must to use recursion for this problem?
I ask because, my poor usage of recursion makes me run out of stack memory many times, so i tend to avoid it completely.

Thanks a lot for the explain, I'm really so thankful for you :)

I'll use the code of yours :)

Pray for me to do well in my exam hehe xDD

by the way, guys I'm a web designer, if anyone needs help in Design I'll be happy to assist, just PM me (as a gift for helping me) ;)

curiously, Is it a must to use recursion for this problem?
I ask because, my poor usage of recursion makes me run out of stack memory many times, so i tend to avoid it completely.

Yeah it should be in recursion, for me I hate recursion lol xDD

When i first learned it. It was fun.

Recursion makes things simple for you. Programs like towers of honai, Infix to postfix, tree traversals are very much easy when we use recursion.

The problem with me is that I DONT know where to use it & where not to. thats why I choose the loops. But no way I would hate it, for my inability.

So, try to love it:)

Hahaha xDD, well I don't hate it from the deepest point in my heart, well sometimes I love it, sometimes I hate it *moody* hahaha xDD

thanks a lot my friend :)