0

So I have recently made a simple calculator in c++ that, among other things, can calculate exponents, but it only works until 2^31. Here is the problem, my input/output is as follows:

I: 2^31
O: 131072

I: 2^32
O: 0

I: 13107*2
O: 262144

Basically it can't do 2^32 but it can do (2^31)*2, and I just can't understand why. If any one can help me and explain why I would really appreciate it. Here is the code that calculates exponents btw:

long exp(long x, int y) {
  int p;

  if (y % 2 == 0) {
      p = 1;
  }
  else {
      p = x;
  }

  while (y > 1) {
      x *= x;
      y /= 2;
  }
  return x*p;
}
ISEL_Student01
  • 25
  • 4
  • 5
    The answer you're getting for 2^31 is also wrong. – user2357112 Mar 29 '16 at 18:50
  • 3
    As far as my C++ skills go... there is no power operator. http://stackoverflow.com/questions/4843304/why-is-my-power-operator-not-working –  Mar 29 '16 at 18:51
  • Pretty cool, right? The key lies in understanding the representation of numbers on the computer. This behavior is finite by default and there will always be a number that you can't represent. There are libraries that can help you use arbitrarily large numbers but they're not typically the default behavior in most languages. Certainly never for c++. – Brian Cain Mar 29 '16 at 18:52
  • 1
    Sadly, your loop isn't doing what you think. There are plenty of tables of powers of 2 on the internet. Check there first to see if you're getting the right answer for 2^31 (hint: you're not) and fix that first. Then use the internet to look up fixed length word representations in computers. – davidbak Mar 29 '16 at 18:53
  • Is this supposed to be exponentiation by squaring? You have the squaring, but you seem to have misunderstood how the `y % 2 == 0` bit is supposed to fit into things. – user2357112 Mar 29 '16 at 18:53
  • 3
    I don't quite get what you're calculating. `2^31 != 131072` – PaulMcKenzie Mar 29 '16 at 18:53
  • 1
    _@ISEL_Student01_ Don't mark your question [SOLVED] in the title please. Accept an existing answer or write one yourself (what you have in your edit now). – πάντα ῥεῖ Mar 29 '16 at 19:00
  • 1
    Also don't mark as solved when the solution is still wrong. That'll put the question on the fast track to deletion. – user4581301 Mar 29 '16 at 19:01
  • `^` means bitwise XOR, not exponentiation. – AndyG Mar 29 '16 at 19:07
  • I don't see why all the downvotes are coming. The premise of the question might not be the best, but the question in itself is solid. Cut him some slack. – pingul Mar 29 '16 at 19:22
  • True. Downvote gone. That said, it took a half-dozen edits to get here. – user4581301 Mar 29 '16 at 21:10
  • what? 2^32 = 0? and `exp(x)` means `e^x` (the natural constant e to the power of x) in most situations. There is even an [`exp`](http://en.cppreference.com/w/c/numeric/math/exp) function in C and C++ already, so your function name is incorrect and will get you into a lot of trouble – phuclv Jun 22 '16 at 02:39

2 Answers2

3

Your function gives wrong results even for small numbers. Consider:

std::cout << exp(2,4); // 16
std::cout << exp(2,5); // 32
std::cout << exp(2,6); // 16 ???

First you need to fix the implementation of the function, second use greater type that is able to represent bigger numbers:

long long exp(long long x, int y)
{
    long long result = x;
    while(--y)
    {
        result*=x;
    }
    return result;

}

EDIT: note it only work for positive numbers. Also note that there is no built-in "power operator" in C++. Operator ^ is called XOR operator, which performs bitwise operation on two numbers. Note:

int x = 0b101'111; //47
int y = 0b110'010; //50
//x^y = 0b011'101
std::cout << (x^y); //outputs 29

Every single bit in result of XOR operator is set 1, if only one of a pair of bits is set, otherwise 0.

x:      0   1   0   1 
y:      0   0   1   1

result: 0   1   1   0
xinaiz
  • 7,744
  • 6
  • 34
  • 78
  • 1
    Worth adding a line explaining what the `^` operator really does or at least pointing readers to documentation on C++ operators. – user4581301 Mar 29 '16 at 18:59
  • While your implementation may be correct (I haven't tried it, but it looks like the trivial exponentiation algorithm), OP was clearly going for the exponentiation-by-squaring algorithm, where you square the base and halve the exponent. His implementation of it was incorrect indeed, though. – Jorge Israel Peña Mar 29 '16 at 19:03
  • Yeah, basically I was trying to make it more efficient and do less multiplications by doing something like: 2*2*2*2*2 = 4*4*2 = 8*2 = 16 Instead of 2*2*2*2*2=4*2*2*2=8*2*2=etc. But thanks. – ISEL_Student01 Mar 29 '16 at 19:03
  • 2
    @ISEL_Student01 P.S. 4*4*2=32 not 16 (4*4 is 16). – callyalater Mar 29 '16 at 19:05
  • How much is exp( 2, 0)? – zdf Mar 29 '16 at 21:50
0

By turning "long" into "long long" I managed to represent 2^32.

Another problem that people pointed out was 2^31 is wrong, that is because I didn't consider the fact that even if y starts even it can later become odd when dividing by 2, and then when you dive by 2 again, it will do one less cycle than it should.

EX: y=6 >> 6/2 = 3 >> 3/2 = 1

EDIT: I managed to fix it, if any one is interested here is how the code looks now:

long long exp(long long x, int y) {
  int p = 1;


  while (y > 1) {
      if (y % 2 != 0) {
          p *= x;
      }
      x *= x;
      y /= 2;
  }
  return x*p;
}

From what I've seen it seems to be working.

ISEL_Student01
  • 25
  • 4