CODEWITHSUNDEEP
c++algorithm
user2994219
user2994219

Reputation: 115

What’s wrong with my implementation of the power function?

I wrote a code for a simple problem in leetcode. It asks to implement pow(x,n); It tells me that "run time error", Last executed input: 1.00000, -2147483648. I changed to another method, that works. But I just want to know what I am doing wrong in the following code. Thanks very much!!

class Solution {
public:
    double pow(double x, int n) {
        // IMPORTANT: Please reset any member data you declared, as
        // the same Solution instance will be reused for each test case.
        if(n==0 && x==0) return 1.0;
        if(x==0) return 0;
        if(n==0) return 1.0;
        if(n<0) return 1/pow(x,-n);
        if(n==1) return x;

        double y=pow(x,n/2);
        if(n%2==1) return y*y*x;
        else return y*y;

}

};

Upvotes: 1

Views: 166

Answers (2)

Matt
Matt

Reputation: 20786

Assuming int is 32 bits in length, -2147483648 is the one unique value, other than 0, in which its negation is equal to itself. So the line:

if(n<0) return 1/pow(x,-n);

is calling itself with the same parameters, and does so until there is a stack overflow.

In greater detail, the binary representation of -2147483648 is:

10000000000000000000000000000000

That's 1 followed by 31 0s. Taking the negation according to two's complement is a two step process. 1) Change all 0s to 1 and vice-versa:

01111111111111111111111111111111

then 2) add 1:

10000000000000000000000000000000

So we get back the same value. Hence the infinite recursion.

If you MUST handle this case, here is one idea. Insert this just before the n<0 test:

if (n==-2147483648) return 1/(x*pow(x,2147483647));

Obviously this is a hack for this one case. Ultimately your problem domain will determine the most elegant/general solution.

Upvotes: 6

Philip Sheard
Philip Sheard

Reputation: 5825

-2147483648 is hex 80000000 is the largest negative number, and one more than the largest positive one. So when n = -2147483648, there is no -n. The code will fail at the line

if(n<0) return 1/pow(x,-n);

This of course is a special case.

Upvotes: 2

Related Questions