0

I had to make a recursive function that use only multiplication operation to get the answer of X in power of N.

I wrote this:

#include <stdio.h>

int power(int x, int n);

int main()
{
    int x, n;
    printf("Enter base and exponent:\n");
    scanf("%d%d", &x, &n);
    printf("%d\n", power(x, n));
    return 0;
}

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

So its works good for small number, like if the input x=3, n=2 the output will be 9 which is good. But when I input bigger numbers, for example: x=362, n=123 the output will be -79249792 which its wrong.

Can someone help me understand what's wrong?

(Im using Online C Compliler {OnlineGBD})

Alfa Hores
  • 347
  • 2
  • 10
  • 2
    Typical `int` can store only upto `2147483648` (`(1 << 31) - 1`). `362 ** 123` will be 315-digit number in decimal, so you will have to implement multiple-precision arithmetics. – MikeCAT Jul 13 '22 at 16:29
  • 1
    Your recursion is wrong. `x^n = (x ^ (n/2))^2 `. You will need to handle odd and even powers separately. – Eugene Sh. Jul 13 '22 at 16:30
  • 1
    Also: `n*0.5` will give you non-integers if `n` is odd. When you pass it as an `int` argument in the recuresive call it will be truncated. – wohlstad Jul 13 '22 at 16:34
  • Maybe you can use the following simpler recursive formula: x^n = x * x ^(n-1). – wohlstad Jul 13 '22 at 16:39
  • @wohlstad I need to make the recursive function only by multiply numbers. (I see now that my recursion not really work) – Alfa Hores Jul 13 '22 at 16:40
  • Then see @EugeneSh.'s comment above for the right formula (^ 2 can be implemented by multiplying a value by itself). – wohlstad Jul 13 '22 at 16:41
  • 1
    @wohlstad That would be equivalent to loop (O(n)), while the other approach is O(log n) – Eugene Sh. Jul 13 '22 at 16:41
  • I changed the `x*power(x, n*0.5)` to `x*power(x, n*0.9999)`, its like dividing by 1, u think its ok? – Alfa Hores Jul 13 '22 at 16:42
  • 1
    @AlfaHores This change does not make any sense. – Eugene Sh. Jul 13 '22 at 16:43
  • @EugeneSh. you are right. But if is was valid it could be a simpler initial approach for this excercise (I don't think complexity is a concern when you start to practice recursion). – wohlstad Jul 13 '22 at 16:43
  • @EugeneSh. Why not? if for example I multiply 10 by 0.9999 I get 9.9999 and will make it 9 becouse its int. (I'm sorry if I sounds dumb but I just started to learn..) – Alfa Hores Jul 13 '22 at 16:47
  • 1
    @AlfaHores First of all, an `int` can't have a value of `9.9999`, second - what it has to do with power calculation? You were given two valid recursive approaches in the comments already, try understanding and implementing at least one of them. – Eugene Sh. Jul 13 '22 at 16:49
  • @EugeneSh. I wanted to implement this ` x^n = x * x ^(n-1).` , but I'm not allowed to use `-` in my answer so I wanted to make a trick to solve this. I will see the other approach now. – Alfa Hores Jul 13 '22 at 16:52
  • 1
    It's very inefficient and might break the stack, for example with 1¹¹¹¹¹¹¹¹¹. Consider using **exponentiation**. See [The most efficient way to implement an integer based power function pow(int, int)](https://stackoverflow.com/questions/101439/the-most-efficient-way-to-implement-an-integer-based-power-function-powint-int) – Weather Vane Jul 13 '22 at 17:01

2 Answers2

2

First, the recursion you implemented shouldn't work for small numbers too, since as others have pointed out, x^n = (x^(n/2))^2 and not x*(x^(n/2)), and for odd values of n, n/2 will get truncated since the function takes integer arguments. Try 2^3, your code gives answer 4. A simple way to fix this is via using the following recursion : x^n = x*(x^(n-1)), or if you want to make the code more efficient, use this algorithm.

But this still doesn't address negative numbers showing up. The problem is max size of int is 2^31-1 = 2,14,74,83,647. This is due the way it is stored in memory, occupying 32 bits. What happens when you cross this limit? It overflows, and becomes -2^31. So you won't be able to get correct answers for big numbers. Generally this is handled by calculating the answer modulo some prime number, or creating arbitrary precision data structures. Check out this and this.

ParadigmShift
  • 231
  • 2
  • 4
2

First of all, please remove this:

printf("Enter base and exponent:\n");
scanf("%d%d", &x, &n);
printf("%d\n", power(x, n));

and write a simple, easy to run test harness that doesn't involve thinking and typing input into the console, with clear output of expected/actual values on failure:

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

int power(int base, int exponent) {
    return 1;
}

int main(void) {
    for (int base = 0; base < 5; base++) {
        for (int exponent = 0; exponent < 5; exponent++) {
            int expected = (int)pow(base, exponent);
            int actual = power(base, exponent);

            if (expected != actual) {
                printf("[FAIL] power(%d, %d) was: %d\n"
                       "              expected: %d\n\n",
                       base, exponent, actual, expected);
            }
        }
    }

    return 0;
}

Notice the clearer parameter names on the power function and usage of the built-in pow to ensure correct logic.

Now let's test your algorithm:

[FAIL] power(2, 3) was: 4
              expected: 8

[FAIL] power(2, 4) was: 8
              expected: 16

[FAIL] power(3, 3) was: 9
              expected: 27

[FAIL] power(3, 4) was: 27
              expected: 81

[FAIL] power(4, 3) was: 16
              expected: 64

[FAIL] power(4, 4) was: 64
              expected: 256

It appears that n*0.5 isn't giving the correct reduction factor.

Taking a step back, exponentiation by multiplication is done by repeatedly multiplying base by itself exponent times and accumulating onto a result initialized to 1:

int power(int base, int exponent) {
    int result = 1;

    for (int i = 0; i < exponent; i++) {
        result *= base;
    }

    return result;
}

Since we're forced to use recursion, the problem reduces to simulating the classic counting loop above with recursion.

This can be done by subtracting 1 from the exponent per call until we reach 0 (<= 0 is a safer base case than == 0, avoiding blowing the stack on negative input).

As for the return value, you're correct in returning 1 for n == 0 and multiplying base on each frame by the child's value, which is the same as the *= operation in the iterative version.

Here's the fixed code:

int power(int base, int exponent) {
    if (exponent <= 0) {
        return 1;
    }

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

Finally, x=362, n=123 fails because of integer overflow. 362**123 has 315 digits, but 4 byte numbers like int only hold 10-ish. You'll need a big integer library to handle that massive an input.

Note that I haven't attempted to handle negative numbers here. I assume that's out of scope. Making the parameters unsigned would help enforce this contract.

ggorlen
  • 44,755
  • 7
  • 76
  • 106