Take the 2-minute tour ×

what did I do wrong in this functions. I am pretty sure the problem is at base = exp(base, pwr /= 2) * exp(base, pwr /= 2); but I cannot think of a logical reason. is there a possible way to write a parameter like that? thanks in advance. (p.s my output of this function is a 2 which is wrong)

#include <iostream>
using namespace std;

unsigned long& exp(unsigned long& base, unsigned long& pwr)
    if(pwr == 0)
      base = 1;
    else if(pwr == 1)
      base = base;
    return base;

int main()
    unsigned long n=2, m = 4;
    cout << exp(n,m) << endl;
    return 0;
share|improve this question
Have you tried stepping through this in a debugger? –  Oli Charlesworth Nov 21 '11 at 16:10
What is the function supposed to do and what is expected output? –  Laurynas Tretjakovas Nov 21 '11 at 16:10
Because you're using references everywhere, every manipulation you make to base or pwr affects all the current calls to the function. Remove all the references in your code and try again; if it still doesn't work at least it will be about 100x easier to debug. –  tenfour Nov 21 '11 at 16:11
You are right, your algorithm is plain wrong, but it feels like homework, so giving out the answer doesn't seem right. You should step through the code with a debugger or printf the value of base with each iteration to better understand what your code is doing. (And maybe go back to the drawing board to figure out what the correct code is) –  madd0 Nov 21 '11 at 16:13
The change you mention works because you're only dividing pwr by 2 once per round; in the above example, you're dividing twice. Because pwr is passed-by-ref, /= affects every instance of pwr. Handling variables by reference means all instances of pwr point to the same location in memory. Any assignment operation will be reflected in all of them. –  matthias Nov 21 '11 at 16:27
show 3 more comments

closed as too localized by Oli Charlesworth, tenfour, NPE, Justin Ethier, Paŭlo Ebermann Nov 22 '11 at 18:00


5 Answers

up vote 2 down vote accepted

Here are five things to note about this line:

  1. As noted in a comment above, base is passed by reference, not value, so there is only one copy of it and you're changing its value. This is a bad idea.
  2. pwr is also passed by reference and you're changing its value when you use /= instead of just /. There are two /= statements in this line, so after this line runs, pwr now has one fourth its original value.
  3. The exp function will get run twice each time you run this line. It would make more sense to store the value and then square it.
  4. /2 is integer division, so it will round down. So if you give it a number like 3 as an exponent, it will not work correctly because 3/2 is 1. If you correct the other mistakes and the call it with an exponent of 7, it will end up only doing exp(2,7) = exp(2,3)*exp(2,3) = exp(2,1)*exp(2,1)*exp(2,1)*exp(2,1) = 16 when obviously the correct answer is 128. This function, as designed, will only work correctly when the exponent is a power of 2.
  5. Good thing that number 4 is true because if you did get exp(2,1.5) you'd never terminate since it wouldn't match your base cases. You should probably rethink your algorithm generally.
share|improve this answer
ahh, thanks it explains. –  ihm Nov 21 '11 at 16:33
6. Assigning a variable twice within the same line. Your /=ing pwr by 2 twice, which might work, or cause a large variety of bugs. –  zennehoy Nov 21 '11 at 16:38
That was actually part of the point of 2. I noted that it was being a fourth of its original value. I'll edit it to make it more clear, though. –  Keith Irwin Nov 21 '11 at 16:39
add comment

The first problem that I can see is that you pass base and pwr by reference. When you do this, their global value gets modified every time yo call exp, so the output you are getting should be expected based on the code you wrote.

To get a correct result I would replace



exp(base, pwr/2) * exp(base, pwr/2);

because your exp(2, 4) = exp(2, 2) * exp(2, 1) is not really correct..

share|improve this answer
also as pepsi says, this won't work with exponents not being a power of 2... –  l.moretto Nov 21 '11 at 16:28
add comment

Since you claim this isn't homework:

  1. As others have mentioned, the references don't belong here. Each recursive call needs the values for that particular point in the calculation.

  2. exp(base, pwr /= 2) * exp(base, pwr /= 2);

    This won't work as expected when your exponent is not a multiple of 2. After you fix the reference thing, if you still really want to do it this way, try:

    exp(base, pwr/2) * exp(base, (pwr/2 + pwr%2));

share|improve this answer
I am still thinking. I understand that it doesn't work if it's not a multiple of 2. –  ihm Nov 21 '11 at 16:28
add comment

We can step through this fairly easily, the first time through exp base is 2 and pwr is 4 so we call with exp (2, 1) * exp (2, 0) (remember you are setting pwr = pwr / 2). So the first one evaluates to 2 and the second evaluates to 1 so you are returning the result of 2 * 1 which is 2. I think you're code means to return the result of exp (2, 1) * exp (2,1) instead.

share|improve this answer
add comment

That is very odd. Your code, to me, reads logically and syntactically correct. I would agree with you on where the problem is. Short of me debugging it myself, I would suggest you try the simple numbers for the program (n=1, m=1 ; n=4, m=1 ; n=2, m=1 ; n=2, m=0). If that's all fine then it very well seems to be that the problem lies exactly where you've pointed out.

I know that doesn't solve your problem but it's a start (if you haven't done it already). I would, because I'm insane, also try

else {
  power = power-1;
  base = base * exp(base, power);

I'm not sure if that'll help (it'll definitely be slower), but perhaps worth the try? I would also remove a lot of the references.

share|improve this answer
I'm sorry I don't have a C-Plus-Plus program/compiler on here. Stupid macbooks. (just kidding, I love them) –  victoroux Nov 21 '11 at 16:21
yeah, I know the problem is there. but I don't get the logic why it's wrong. I could write the codes like else {pwr /= 2; base = exp(base, pwr) * exp(base, pwr);} and get the right answer. but i am trying to figure out what's wrong with this expresssion. –  ihm Nov 21 '11 at 16:23
Then use various numebrs and compute it yourself. You'll find out easily, haha. Old paper and pen does the trick... –  victoroux Nov 21 '11 at 16:25
@victoroux g++ is included with every Apple computer. You can run files from Terminal using g++ FILENAME then seeing the output with ./a.out –  Chris Nov 21 '11 at 16:25
@victoroux you know you can download dev tools for free for any mac, right? If you're running Lion, just download XCode 4 from the app store, else download XCode 3 from apple.com. –  matthias Nov 21 '11 at 16:29
show 1 more comment
