CODEWITHSUNDEEP
c++algorithmmath
Martingale
Martingale

Reputation: 83

Implement pow(x, n)

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"; }

Upvotes: 5

Views: 1280

Answers (5)

Mansur Kurtov
Mansur Kurtov

Reputation: 772

C# Simple solution:

    class Program
        {
    
            private static void Main(string[] args)
            {
                var result = MyPow(-1.00000, -2147483648);
            }
            public static double MyPow(double x, int n)
            {
                return Math.Pow(x, n);
            }
        }

after running this code, variable "result"'s value will equal to 1

Upvotes: 0

Purva
Purva

Reputation: 411

/*Java Solution */

class Solution {

public double myPow(double x, int n) {

if(n == 0) return 1;

if(Math.abs(x-0.0)<0.0000001) return 0.0;

if(Math.abs(x-1.0)<0.0000001) return 1.0;

if(n < 0) x = 1.0/x;

return Power(x, Math.abs(n));

}

double Power(double x, int n){

if(n == 0) return 1;

if(n == 1) return x;

return ((n&0x1) == 1) ? x*Power(x*x, n/2) : Power(x*x, n/2); 
}

}

Upvotes: 0

mazhar islam
mazhar islam

Reputation: 5619

Note that Primitive data type ranges are:

short int and int: −32,768 to 32,767 

unsigned short int and unsigned int: 0 to 65,535 

long int: −2,147,483,648 to 2,147,483,647 

unsigned long int: 0 to 4,294,967,295 

long long int: −9,223,372,036,854,775,808 to 9,223,372,036,854,775,807

Reference: MSDN and The GNU C Reference

As you can see, the minimum value an integer can hold is −2,147,483,648, so when you perform -(−2,147,483,648) an integer overflow occurred.

So use long long int instead of int to handle with big signed number.

The following code:

#include <vector>
#include <string>
#include <iostream>
using namespace std;

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

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

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

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

int main () {
    cout << myPow(-1.00000, -2147483648);
}

Give me output:

1

Upvotes: 3

Michael Anderson
Michael Anderson

Reputation: 73440

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

xn = xn+1 / 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.

Upvotes: 3

samgak
samgak

Reputation: 24417

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.

Upvotes: 5

Related Questions