Please explain the logic behind this program that uses recursion to calculate a^b (a raised to power b) [closed]

Question

It's really embarrassing!!I just fail to understand the working of the following little program that uses recursion to calculate the powers of a number "a" ("a" raised to a power "b").Kindly explain the logic used behind this function.I don't understand the use of the "x*x" parameter,the n/2 parameter and the "n modulo 2" part.Please dissect it for me.

    #include<stdio.h>

    int foo(int,int);

    int main() {
      int a,b;

      printf("Enter number a and its power b\n");
      scanf("%d%d",&a,&b);

      printf("a raised to b is %d", foo(a,b));
      return 0;
    }


    int foo ( int x , int n) {
      int val=1;

      if(n>0) {
        if (n%2 == 1) 
          val = val *x;
        val = val * foo(x*x , n/2);
      }

      return val;
    }

Answer 1

The idea behind this recursion is, that a^b = (a²)^b/2, and a^b = a(a²)^(b-1)/2.

Depending on whether b is odd or even (thats the n%2 == 1 part), you choose one of these formulas to ensure b/2 or (b-1)/2 is still an integer. Note here, that the n/2 in your code actually is (n-1)/2 for odd n, since integer division rounds down automatically.

This recursion terminates since the exponent grows smaller with each step.

Answer 2

This makes use of the fact that a power such as x^23 can be rewritten as x^16 * x^4 * x^2 * x^1

Now computing x^16 is fairly easy, because it's just (((x^2)^2)^2)^2 which is only 4 multiplications instead of computing x * x * x * ... 16 times ... * x.

Now notice that while computing x^16 you've also run across x^4 and x^2 which you needed to compute your number. So in the end, you've computed x^23 in only 7 multiplications instead of 22.

Now where the n % 2 and n / 2 come in to the picture is in deciding if the power of 2 is in n (in our example, is 8 in the binary representation of 23? no).

So you just iterate through the bits of n. You square x every time, and if there's a 1 in the current n bit you're looking at, you multiply the squared number into your result.

Update:

The trick to writing a number out this way is to look at n in binary. 23 is 10111₂, or we can write out the place values 23 = 1*16 + 0*8 + 1*4 + 1*2 + 1*1.

This means x^23 = x^(16 + 4 + 2 + 1) and thanks to the exponential laws, = x^16 * x^4 * x^2 * x^1 which is what we started with.

As another quick example: take x^44. We write it in binary as 101100₂ so we can say

44  =  1*32 + 0*16 + 1*8 + 1*4 + 0*2 + 0*1  =  32 + 8 + 4

so

x^44 = x^(32 + 8 + 4) = x^32 * x^8 * x^4

we then calculate the following

1:   x^2  = (x)^2                     (from the x we are given)
2:   x^4  = (x^2)^2                   (x^2 from step 1)
3:   x^8  = (x^4)^2                   (x^4 from step 2)
4:   x^16 = (x^8)^2                   (x^8 from step 3)
5:   x^32 = (x^16)^2                  (x^16 from step 4)
6:   x^44 = (x^32) * (x^8) * (x^4)    (using results of steps 2, 3, and 5)