x^n function not working

[cooper1200]

one of the projects in my book asks me to write a recursive function that raises x to the power n. im given the formula that if the power is even x^n = (x^(n/2))^2 or if its odd x^n = x * x^(n-1)

here is the code

#include <stdio.h>
#include <stdlib.h>

int power(int x, int n);

int main()
{
    int x, n, answer;

    printf("Enter the value of x: ");
    scanf(" %d", &x);
    printf("Enter the value of n: ");
    scanf(" %d", &n);

    answer = power(x, n);
    printf("%d to the power %d is %d\n", x, n, answer);

    return 0;
}

int power(int x, int n)
{
    if (n == 0)
    {
        return 1;
    }
    else if (n % 2 == 0) //check to see if the power is even or odd
    {
        return x * x * power(x, n / 2);
    }
    else
    {
        return x * power(x, n - 1);
    }
}

if i enter 2 for x and 10 for n i get the answer 256 which is WRONG it should be 1024 if i enter 2 for x and 5 for n i get the answer 64 which again is WRONG it should be 32.

Obviously the function is wrong somewhere but i cant for the life of me see where.

many thanks
coop

[laserlight]

Consider power(2, 6). 6 % 2 == 0, so you compute 2 * 2 * power(2, 3) = 4 * 8 = 32. However, 2^6 = 64, not 32. The problem is that you should have computed power(2, 3) * power(2, 3) instead (though you would want to save the recursive call into a variable that you then multiply rather than having two recursive calls).

[gaxio]

Look carefully at the equation. You're doing x^n = x * (x^(n/2)) if even.

[cooper1200]

Look carefully at the equation. You're doing x^n = x * (x^(n/2)) if even.

i dont understand what you mean.

here is my logic if n %2 == 0 its even so return x * x * power(x, n/2 so how am i only multiplying by 1 x??

[flp1969]

i dont understand what you mean.

here is my logic if n %2 == 0 its even so return x * x * power(x, n/2 so how am i only multiplying by 1 x??

It's worse... x = √x⁵, if x is even, in the first call...

Suppose x = 5405 and n = 2. You'll get an overflow.

[gaxio]

i dont understand what you mean.

here is my logic if n %2 == 0 its even so return x * x * power(x, n/2 so how am i only multiplying by 1 x??

You're right, but that makes it x^2 * x^(n/2), not (x^(n/2))^2. You want to return x^(n/2) * x^(n/2), or power(x, n/2) * power(x, n/2).

[cooper1200]

im completely confused here the purpose of the program is to reduce the number of multiplications. 2^6 takes 5 goes... so how does calling power from power twice in one return statement make it less multiplication im obviously not understanding the fundamental issue here

[laserlight]

You call it once since the result from the calls would be the same. Refer to my post #2.

EDIT:
Incidentally, you can do something similiar for odd powers, e.g., given x^7, instead of computing x * x^6, you can compute x * x^3 * x^3, where the x^3 correspond to a single recursive call with a result saved into a variable.

[gaxio]

There is no way to reduce the number of multiplications. I'm not a mathematician, so maybe there's some math trick, but just using the basic operations here it'll always take N-1 multiplications. Just start expanding the function calls to power. Every time there's a function call to power, expand it with what it returns.

power(x,5);
x * power(x,4);
x * power(x,2) * power(x,2);
x * x * power(x,1) * x * power(x,1);
x * x * x * power(x,0) * x * x * power(x,0);
x * x * x * 1 * x * x * 1;

As you can see, it actually produces 2 more multiplications than it needs to. If you add an extra case where n==1 it just returns x, you can get rid of those, but even then you're left with the same number of multiplications as if you'd done it by hand. That's because this is not an optimization, this is an exercise to teach you how to write a recursive function. You could have just as easily done it like this.

int power(int x, int n) {
  if(n == 0) return 1;
  if(n == 1) return x;
  else return x * power(x, n-1);
}

Expand that the way I did and you'll see how it is equivalent to doing it manually or in a loop.

[laserlight]

There is no way to reduce the number of multiplications. I'm not a mathematician, so maybe there's some math trick, but just using the basic operations here it'll always take N-1 multiplications.

That's because you're looking at too small an N. Consider N=16:
x^16 = x^8 * x^8
x^8 = x^4 * x^4
x^4 = x^2 * x^2
x^2 = x * x
Hence, you only need 4 multiplications to compute x^16, not 15 multiplications.

EDIT:
Oh, and it looks like you're making the same mistake of not saving the result of the recursive call into a variable, but instead needlessly doing the same recursion twice at each step. Consider N=5, as in your example, using cooper1200's extra recursive step:
x^5 = x * x^4
x^4 = x^2 * x^2
x^2 = x * x
Hence, contrary to your claim that 4 multiplications are needed, only 3 multiplications are needed.

[gaxio]

That's because you're looking at too small an N. Consider N=16:
x^16 = x^8 * x^8
x^8 = x^4 * x^4
x^4 = x^2 * x^2
x^2 = x * x
Hence, you only need 4 multiplications to compute x^16, not 15 multiplications.

Um... no. If you expand that, you get... (are you really making me type this out?)

power(x, 16);
power(x, 8) * power(x, 8);
power(x, 4) * power(x, 4) * power(x, 4) * power(x, 4); 
power(x, 2) * power(x, 2) * power(x, 2) * power(x, 2) * power(x, 2) * power(x, 2) * power(x, 2) * power(x, 2);
x * x * x * x * x * x * x * x * x * x * x * x * x * x * x * x;

There are no fewer multiplications than if done manually.

[laserlight]

Um... no. If you expand that, you get... (are you really making me type this out?)

You're making yourself type it out

You expand each recursive call exactly once. That is, you won't write:

return power(x, n / 2) * power(x, n / 2);

Rather, you will write:

int result = power(x, n / 2);
return result * result;

This means that each recursive call other than the base case only leads to one recursive call. Hence, the number of multiplications is proportional to the number of recursive calls, which in turn is proportional to log N since N is roughly halved at each step.

Therefore, for N > 3, it is not true that "there are no fewer multiplications than if done manually".

I should add that this isn't some new algorithm that cooper1200's instructor invented. Maybe a decade ago when I was still an undergraduate, I did a complexity analysis of an algorithm on the whiteboard, and my prof casually went something like "perfect, except that this term (points to x^n or something similiar as an integer power) takes log n time rather than constant time". As you can tell from my anecdote, it's uncontested in the literature.

[cooper1200]

ok i think i have finally got it now i need to make each return statement the same as the original statement

for example if x=2 and n is 6 since 6 is even return has to be x^3 * x^3 = x^3+3 = x^6 or if an odd power ie 5 x^1 * x^4 = x^1+4 = x^5

sorry to be so thick
coop

[laserlight]

You might want to express that as code to be sure. Anyway, don't worry about not getting it right the first time: you can see from our exchange that gaxio too was under the mistaken impression that the algorithm must take linear time, and you can see from other posts that gaxio is an experienced programmer. If you search through my posts you can see where I have made my fair share of incorrect analyses.

[flp1969]

Here's one consideration: pow() functions usualy don't do multiple multiplications they are implemented as:

double pow( double x, double y )
{ return exp( y * log(x) ); }

This way, don't matter the base or the expoent, it takes, more or less, the same quantify of cycles (specially if you are dealing with f87 code). Here's a simple test for x86-64:

#include <stdint.h>
#include <inttypes.h>
#include <stdio.h>
#include <math.h>

static uint64_t local_tsc__;

#define BEGIN_TSC(...) do { \
    uint32_t a, d; \
    \
    __asm__ __volatile__ ( \
                           "xorl %%eax,%%eax\n\t" \
                           "cpuid\n\t" \
                           "rdtsc" \
                           : "=a" (a), "=d" (d) :: "%rbx", "%rcx" \
                         ); \
    \
    local_tsc__ = ((uint64_t)d << 32) | a; \
  } while (0)

// rdtscp is available on all Haswell architectures.
#define END_TSC(c) do { \
    uint32_t a, d; \
    \
    __asm__ __volatile__ ( \
                           "rdtscp" \
                           : "=a" (a), "=d" (d) :: "%rcx" \
                         ); \
    \
    (c) = (((uint64_t)d << 32) | a) - local_tsc__; \
  } while (0)

int main ( void )
{
  int x, y;
  double z;
  uint64_t c;

  scanf ( "%d %d", &x, &y );

  BEGIN_TSC();
  z = pow ( x, y );
  END_TSC ( c );

  printf ( "x^y = %g (%" PRIu64 " cycles)\n",
           z, c );

  return 0;
}

Compiling and linking (and running):

$ cc -O2 -o test test.c -lm
$ ./test <<< '50 10'
x^y = 9.76562e+16 (73704 cycles)
$ ./test <<< '500 100'
x^y = 7.88861e+269 (79402 cycles)
$  ./test <<< '5 300'
x1^y1 = 4.90909e+209 (62106 cycles)
$ ./test <<< '5000 1000'
x^y = inf (59896 cycles)

The variations of cycles are due to cache, interrupts, page faults and other issues, notice I am calculating with expoent 10, 100, 300 and 1000 and getting, more or less, the same time of calculation...

So, calling pow() n times will slow down your code n times...

PS: I know the equation is not correct for x < 0 and y fractionary... there are other tests made by pow() implementation.