GIDForums  

Go Back   GIDForums > Computer Programming Forums > C Programming Language
User Name
Password
Register FAQ Members List Calendar Search Today's Posts Mark Forums Read
 
 
Thread Tools Search this Thread Rate Thread
  #1  
Old 29-Oct-2011, 12:44
FluffBear FluffBear is offline
New Member
 
Join Date: Oct 2011
Posts: 5
FluffBear is on a distinguished road

Recursive pow(base,exponent) mini-program.


Hey everyone, i'm new to this forum so I wasn't sure how to format the code. (I read the how-to, but it was slightly confusing) Its very simple so I figured it was ok to leave it like this.

The object of my code (in the c programming language) is to basically to write a program that does what pow(x,n) does. The only difference is that I am using two different formulas. One for even exponents and one for odd exponents.

In this code I am only dealing with even exponents right now. The formula is:
(x^(n-2))^2. I am having trouble dealing with the last ^2. This should be the final value of total multiplied by itself. So x^4 * x^4 = x^16.

Lastly, should I be separating my main (program that calls pow) and my function into different programs.. even though my main is so small?



My Code:

CPP / C++ / C Code:
#include <stdio.h>

int main(void){

int pow(int x, int n){

int total = 0;

 if (n == 0){

return 1;

 } else {

if (n > 0){

return total = x * pow(x,(n - 2));

}
/*total = total * total;*/
}


int a, b, final;
scanf("%d%d", &a, &b);
final = pow(a,b);
printf("The final computation of x to the n power: %d\n", final);


}
  #2  
Old 29-Oct-2011, 14:33
davekw7x davekw7x is offline
Outstanding Member
 
Join Date: Feb 2004
Location: Left Coast, USA
Posts: 6,160
davekw7x is a splendid one to beholddavekw7x is a splendid one to beholddavekw7x is a splendid one to beholddavekw7x is a splendid one to beholddavekw7x is a splendid one to beholddavekw7x is a splendid one to beholddavekw7x is a splendid one to beholddavekw7x is a splendid one to behold

Re: Recursive pow(base,exponent) mini-program help


Quote:
Originally Posted by FluffBear
...

In this code I am only dealing with even exponents right now. The formula is:
(x^(n-2))^2.
Hmmm...

Actually you have implemented a function that returns x * pow(x, n-2), not pow(x, n-2) * pow(x, n-2) at each recursion for n > 0.

The important thing is that neither the function that you defined nor the function that you implemented can be applied recursively to obtain anything remotely related to pow(x, n) for n > 0 whether n is even or not. For either one, step through a couple of cases ("by hand," not on the computer) and see what you get for pow(2, 2), pow(2, 4), etc.

Wasn't the statement of the recursion somewhat like the following? (In addition to using a temporary variable to reduce the number of recursion calls to one at each step, I have renamed the function to foo, instead of using the name pow. I have my reasons, but don't ask...)

Code:
foo(x, n) IF n is equal to zero THEN RETURN 1 ELSE LET temp = foo(x, n/2) IF n IS ODD THEN RETURN temp*temp ELSE RETURN x*temp*temp END IF END IF

I mean, there may be other ways of defining a power function recursively (other than the obvious one of returning foo(x, n-1)) but this is the usual "fast power" function recursive definition. (See Footnote.)

Quote:
Originally Posted by FluffBear
..should I be separating my main (program that calls pow)

In C, you can't have functions embedded in other functions. So, they would be separate. Not necessarily in separate files, but separate functions.

I might do something like the following:
CPP / C++ / C Code:
#include <stdio.h>


int foo(int x, int n)
{
    /*
        Put your function implementation here.
    */
}

int main()
{
    int a, b, fooValue;

    /*
       Will continue the loop until the user enters
       a non-numeric value (or hits Ctrl-C or some
       such thing).
       Note that there is no checking of input values,
       so you can experiment with negative numbers and
       stuff like that.
    */
    printf("Enter two integers: ");
    while(scanf("%d %d", &a, &b) == 2) {
        printf("You entered %d and %d\n", a, b);
        fooValue = foo(a, b);
        printf("foo(%d,%d) = %d\n\n", a, b, fooValue);
        printf("Enter two integers: ");
    }

    printf("\nGoodbye for now.\n");
    return 0;
}

Then, if you do it right, a run could look like:
Code:
Enter two integers: 2 3 You entered 2 and 3 foo(2,3) = 8 Enter two integers: 9 5 You entered 9 and 5 foo(9,5) = 59049 Enter two integers: 2 30 You entered 2 and 30 foo(2,30) = 1073741824 Enter two integers: quit Goodbye for now.

If your function gives different (wrong) values, you might be able to see why if you put a print statement at the beginning of the function:
CPP / C++ / C Code:
int foo(int x, int n)
{
    printf("in foo: x = %d, n = %d\n", x, n);
    /*
        Put your function implementation here.
    */
}



Regards,

Dave

Footnote:
My pseudo-code implements the parts of the Exponention by squaring algorithm that hold for n >= 0.
__________________
Sometimes I just can't help myself...
Last edited by davekw7x : 29-Oct-2011 at 15:36.
  #3  
Old 29-Oct-2011, 21:48
FluffBear FluffBear is offline
New Member
 
Join Date: Oct 2011
Posts: 5
FluffBear is on a distinguished road

Re: Recursive pow(base,exponent) mini-program help


Ok, thanks a lot Dave! I have not been programming for very long and so recursion was something that was a little tougher to grasp. Your suggestion to write it down helped a lot as I was able to trace through the recursion calls much more easily than through my head. I have a much better understanding of recursion now which helped me to finish the question. Here's the code I wrote. It only applies to positive integers (base and exponent). I tried to brainstorm some other ways to write the algorithm but the algorithm is so short and simple that I couldn't figure it out anymore. (Please suggest! As I want to become as open-minded as possible.)

Also on a side note, I tried to check if the base and exponent value were negative in the first part of the code. However, it asks me to enter the values twice when I reach this case. I cannot see why.

p.s. My formatting is bad.


CPP / C++ / C Code:
#include <stdio.h>

/* Function which takes a positive integer base and a positive integer exponent and returns the result */
int exponent(int x, int n){
int c, d;

/* Test if the exponent or base value given is negative. If so exit. */
  while (n < 0 || x < 0){
printf("The value of the exponent or base value given is negative. Please re-enter only positive integers: \n");
scanf("%d%d\n", &c, &d);
x = c;
n = d;
  }

 if (n == 0){

return 1;

 } else {

if ((n % 2) == 0){

  /* Recursive calls which represent the formula x^n = (x^n-2)^2 for even exponent values */
return exponent(x, n/2) * exponent(x, n/2);

 } else{

 if((n % 2) == 1) {

   /* Recursive calls which represent the formula x^n = (x)x^(n-1) for odd exponent values */
return x * exponent(x, n/2) * exponent(x, n/2);

 }
 }
 }
}

/* Main function to test the use of the function exponent */
int main(){


int a, b, final;
scanf("%d%d", &a, &b);
final = exponent(a,b);
printf("The final computation of x to the n power is: %d\n", final);

return 0;
}
  #4  
Old 30-Oct-2011, 10:27
davekw7x davekw7x is offline
Outstanding Member
 
Join Date: Feb 2004
Location: Left Coast, USA
Posts: 6,160
davekw7x is a splendid one to beholddavekw7x is a splendid one to beholddavekw7x is a splendid one to beholddavekw7x is a splendid one to beholddavekw7x is a splendid one to beholddavekw7x is a splendid one to beholddavekw7x is a splendid one to beholddavekw7x is a splendid one to behold

Re: Recursive pow(base,exponent) mini-program help


Quote:
Originally Posted by FluffBear
...However, it asks me to enter the values twice when I reach this case. I cannot see why...
Try changing
CPP / C++ / C Code:
scanf("%d%d\n", &c, &d);

to
CPP / C++ / C Code:
scanf("%d%d", &c, &d);
Quote:
Originally Posted by FluffBear
...My formatting is bad...

So: Fix it. Get into the habit of entering code the way that you want it to look.

What editor are you using? "Real" programming editors have "auto-indent" functionality that might help.


For starters here are a couple of suggestions:

Begin with lines starting at the left-hand margin.

For each function put the opening '{' brace on a separate line after the function header definition, and indent the following lines four spaces.

Then...

In the code, whenever you have a '{' brace, indent the following lines four spaces.

Whenever you have a '}' brace, unindent (outdent?) four spaces before intering the '}' brace.

Besides making it look neater (and easier for us mere humans to follow your organization) it can help you spot unbalanced pairs, since each function begins and ends with lines starting at the left margin.


Regards,

Dave

Footnote: If you go back to the main() function that I showed in my example and if you eliminate the testing that you added to your exponent function, what happens if you use a negative base and a positive exponent value? Does it work? Why would it not work? Do you really need to guard against negative base values?
__________________
Sometimes I just can't help myself...
  #5  
Old 30-Oct-2011, 12:29
FluffBear FluffBear is offline
New Member
 
Join Date: Oct 2011
Posts: 5
FluffBear is on a distinguished road

Re: Recursive pow(base,exponent) mini-program help


Understood. I will start to program in a more organized manner.

The programming editor I am using is EMACS. I am using the editor within a unix terminal that connects to my school network. I have no graphical interface on my labtop. I usually sketch out my algorithms in notepad / java eclipse (for indentation / formatting) and then finish it in EMACS.

CPP / C++ / C Code:
scanf("%d%d\n", &c, &d);

- Getting rid of the \n eliminated the problem. Thanks.


With regards to your main function. Testing it out, negative numbers still work for the base simply because multiplying the bases together eventually cancels the negatives out. Negatives do not work for the exponents. The main reason being that we use n == 0 as our base case. As well, our recursive calls use n as well. Starting off with a negative exponent, changes the recursive calls and therefore the final value we receive.
  #6  
Old 30-Oct-2011, 12:49
davekw7x davekw7x is offline
Outstanding Member
 
Join Date: Feb 2004
Location: Left Coast, USA
Posts: 6,160
davekw7x is a splendid one to beholddavekw7x is a splendid one to beholddavekw7x is a splendid one to beholddavekw7x is a splendid one to beholddavekw7x is a splendid one to beholddavekw7x is a splendid one to beholddavekw7x is a splendid one to beholddavekw7x is a splendid one to behold

Re: Recursive pow(base,exponent) mini-program help


Quote:
Originally Posted by FluffBear
...
With regards to your main function. Testing it out, negative numbers still work for the base simply because multiplying the bases together eventually cancels the negatives out. Negatives do not work for the exponents.

Well, here's my take on it:

The function could be midified so that the value of anything raised to a negative exponent would be calculated as 1/foo(x,-n). (Since, if n is negative, then -n is positive, and that's how the power function would work.)

The main problem (if you want to call it a problem) is that the negative integer power of any non-zero base value other than 1 will be have a fractional value (less than 1).

So, for example, pow(2, 3) is 8 but pow(2, -3) is 1/8. This is zero if you stick with integer arithmetic, but is 0.125 if you were doing floating point arithmetic.

However...the whole point (I think) is to do everything with integer arithmetic, so things like foo(2, -3) should give zero as its value (or maybe in main(), users would be forbidden to enter negative values for the exponent).



Regards,

Dave
__________________
Sometimes I just can't help myself...
  #7  
Old 30-Oct-2011, 14:42
FluffBear FluffBear is offline
New Member
 
Join Date: Oct 2011
Posts: 5
FluffBear is on a distinguished road

Re: Recursive pow(base,exponent) mini-program help


O, ok. One last thing. Is it possible for you or some moderator to remove my code in my second post? (For various reasons) I am unable to edit it anymore. Once again, thanks for your input / advice. It helped a lot.
  #8  
Old 31-Oct-2011, 02:05
admin's Avatar
admin admin is offline
Administrator
 
Join Date: Sep 2002
Posts: 1,043
admin will become famous soon enough

Re: Recursive pow(base,exponent) mini-program help


Quote:
Originally Posted by FluffBear
O, ok. One last thing. Is it possible for you or some moderator to remove my code in my second post? (For various reasons) I am unable to edit it anymore. Once again, thanks for your input / advice. It helped a lot.

Please read this.
__________________
Custom BB codes you can use here:
[HTML] | [C++] | [CSS] | [JAVA] | [PY] | [VB]
  #9  
Old 31-Oct-2011, 07:12
FluffBear FluffBear is offline
New Member
 
Join Date: Oct 2011
Posts: 5
FluffBear is on a distinguished road

Re: Recursive pow(base,exponent) mini-program help


Quote:
Originally Posted by FluffBear
Ok, thanks a lot Dave! I have not been programming for very long and so recursion was something that was a little tougher to grasp. Your suggestion to write it down helped a lot as I was able to trace through the recursion calls much more easily than through my head. I have a much better understanding of recursion now which helped me to finish the question. Here's the code I wrote. It only applies to positive integers (base and exponent). I tried to brainstorm some other ways to write the algorithm but the algorithm is so short and simple that I couldn't figure it out anymore. (Please suggest! As I want to become as open-minded as possible.)

Also on a side note, I tried to check if the base and exponent value were negative in the first part of the code. However, it asks me to enter the values twice when I reach this case. I cannot see why.

p.s. My formatting is bad.


CPP / C++ / C Code:
#include <stdio.h>

/* Function which takes a positive integer base and a positive integer exponent and returns the result */
int exponent(int x, int n){
int c, d;

/* Test if the exponent or base value given is negative. If so exit. */
  while (n < 0 || x < 0){
printf("The value of the exponent or base value given is negative. Please re-enter only positive integers: \n");
scanf("%d%d\n", &c, &d);
x = c;
n = d;
  }

 if (n == 0){

return 1;

 } else {

if ((n % 2) == 0){

  /* Recursive calls which represent the formula x^n = (x^n-2)^2 for even exponent values */
return exponent(x, n/2) * exponent(x, n/2);

 } else{

 if((n % 2) == 1) {

   /* Recursive calls which represent the formula x^n = (x)x^(n-1) for odd exponent values */
return x * exponent(x, n/2) * exponent(x, n/2);

 }
 }
 }
}

/* Main function to test the use of the function exponent */
int main(){


int a, b, final;
scanf("%d%d", &a, &b);
final = exponent(a,b);
printf("The final computation of x to the n power is: %d\n", final);

return 0;
}


O ok, can I request to have this post removed then please Thanks admin.
  #10  
Old 31-Oct-2011, 23:45
admin's Avatar
admin admin is offline
Administrator
 
Join Date: Sep 2002
Posts: 1,043
admin will become famous soon enough

Re: Recursive pow(base,exponent) mini-program help


I'm sorry, that's not how it works. You have to write in explaining your reasons for the request to delete.

If others have replied or helped in even a small way here, it is very likely that nothing will be deleted.
__________________
Custom BB codes you can use here:
[HTML] | [C++] | [CSS] | [JAVA] | [PY] | [VB]
 


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
Binary Tree recursive Functions 90fmm C++ Forum 3 27-Apr-2011 18:37
NetBeans - Inventory Program biglez123 Java Forum 1 23-Jan-2011 20:48
[TUTORIAL] Calling an external program in C (Linux) dsmith C Programming Language 4 22-Apr-2005 13:30
Need help with a C program (Long) McFury C Programming Language 3 29-Apr-2004 20:06

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

All times are GMT -6. The time now is 00:09.


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