CODEWITHSUNDEEP
cmathruntime-error
Ayush
Ayush

Reputation: 2608

Runtime error in program to create your own power function

Ok so I was reading the program to create your own power function given here(Write a C program to calculate pow(x,n))

I read it's 1st method which it calculates power using this function: 

int power(int x, unsigned int y)
{
    if( y == 0)
        return 1;
    else if (y%2 == 0)
        return power(x, y/2)*power(x, y/2);
    else
        return x*power(x, y/2)*power(x, y/2);

}

I got the concept of this program and it gives correct results.

Now, here power(x, y/2)*power(x, y/2) is written so we are just calculating the square of power(x,y/2). So, if my power() function is correct so I can just change it to power(power(x,y/2),2) . That is, we are just calculating the square of power(x,y/2).

So, when I change my program to this:

int power(int x, unsigned int y)
{
    if( y == 0)
        return 1;
    else if (y%2 == 0)
        return power(power(x, y/2),2);   // Square of power(x,y/2)
    else
        return x*power(power(x, y/2),2);   // x*Square of power(x,y/2)

}
int main()
{
    int x = 2;
    unsigned int y = 3;

    printf("%d\n", power(x, y));
    return 0;
}

The above program gives run-time error.

What could be the reason for the run-time error I am not able to figure out. Can anyone help me please?

Upvotes: 1

Views: 274

Answers (1)

barak manos
barak manos

Reputation: 30126

You are calling function power from inside itself, passing 2 as the second argument.

This is essentially an infinite recursion, which eventually leads to a stack-overflow.

If your input arguments are non-negative integers, then you can implement it as follows:

Recursively:

unsigned long long power(unsigned long long x,unsigned int y)
{
    if (y == 0)
        return 1;
    return power(x,y/2)*power(x,y-y/2);
}

Iteratively:

unsigned long long power(unsigned long long x,unsigned int y)
{
    unsigned long long res = 1;
    while (y--)
        res *= x;
    return res;
}

Efficiently:

unsigned long long power(unsigned long long x,unsigned int y)
{
    unsigned long long res = 1;
    while (y > 0)
    {
        if (y & 1)
            res *= x;
        y >>= 1;
        x *= x;
    }
    return res;
}

Upvotes: 4

Related Questions