CODEWITHSUNDEEP
c++recursion
zach
zach

Reputation: 95

Recursive function for finding power returns zero for large exponents

The function bellow works fine for small positive exponents and base. If the exponent is large then memory wouldn't be enough and the program should be terminated. Instead, if that function is called for large exponents, zero is returned.Why? One guess is that a multiplication with zero occurred but there is no such case.

One example where zero is returned is power(2,64) .

unsigned long long int power(unsigned long long int base,int exp){

    if (exp == 0 && base != 0)
        return 1;

    return base*power(base,exp-1);
}

Upvotes: 0

Views: 224

Answers (3)

underscore_d
underscore_d

Reputation: 6795

Aside from filling memory, you should also worry about overflowing the result. 2^64 is 1<<64, which is 1 bit above the size of a 64-bit integer, so due to unsigned modulo arithmetic, that bit ceases to exist, and you end up with 0.

Not relevant in your case, as you shift by smaller amounts, but left-shifting by a number of places equal to or greater than the width of the (promoted) left operand is undefined behaviour, for either signed or unsigned (see e.g. this link and these comments). This contrasts from overflow due to smaller shifts (or other arithmetic ops), which is well-defined as performing modulo for unsigned types but invokes UB for signed.

Upvotes: 3

Mestkon
Mestkon

Reputation: 4061

pow(2ULL, 64) is equal to (1ULL << 64) (if (1ULL << 64) were defined).

It is trivial to see that if you bitshift 1ULL 64 bits to the left there is no data left in a 64 bit unsigned long long. This is called overflow.

Upvotes: 1

darune
darune

Reputation: 11150

You are seeing and that happends to hit zero at some point.

Upvotes: 1

Related Questions