Implement pow(x, n)

Question

Why does this function give the wrong answer -1 rather than the right answer 1 when I try this? myPow(-1.00000, -2147483648)

double QuickPower(double x, int n) 
{
    if(n==0){
        return 1;
    }

    if(n==1){
        return x;
    }

    if(n>=2){
        int res=n%2;
        double half=QuickPower(x,n/2);
        return res? Half*half*x: half*half;
    }
}

double myPow(double x, int n) {
    return n>=0? QuickPower(x,n):(1/QuickPower(x,-n));
}

I just try to run the code below. "Hello World" is printed out. Here I did't specify data type but it still pass if statement. Why?
if (-1 > 2147483648) { cout << "Hello World"; }

Answer 1

The error is a result of an integer overflow.

Inside myPow you negate n when n is negative.

Negating -2147483648 gives 2147483648, which is 1 more than the maximum positive signed 32 bit integer value, which is 2147483647. Use a larger integer data type to fix the bug.

Answer 2

Your problem is due to integer overflow when calculating -n. On your system (and my local one) INT_MIN=-2147483648 and INT_MAX=2147483647.

So the problem is that -(INT_MIN) is not representable as an integer. However you can avoid this issue without going to a higher precision integer type:

Since

xⁿ = xⁿ⁺¹ / x = (1/x) / x^-(n+1)

we can rewrite the myPow as

double myPow(double x, int n) {
    return n>=0? QuickPower(x,n):(1/x)/QuickPower(x,-(n+1));
}

This function is OK since -(INT_MIN+1)=INT_MAX.

It's worth noting that this will have myPow(0,-k) return either +/- Infinity (n=-1) or NaN (n<-1). If you need that case to be consistent then a little more work is required. In general the handling of infinite / nan values is tricky for pow (and not "correct" in this, or the original implementation) - it is worth the man page for the C pow function to get all the edge cases.