Recursive approach for pow(x,n) for finding 2^(37) with less than 10 multiplications

Question

The regular recursive approach for pow(x,n) is as follows:

pow (x,n):

     = 1 ...n=0

     = 0 ...x=0

     = x ...n=1

     = x * pow (x, n-1) ...n>0

With this approach 2^(37) will require 37 multiplications. How do I modify this to reduces the number of multiplications to less than 10? I think this could be done only if the function is not excessive.

Answer 1

With this approach you can compute 2^(37) with only 7 multiplications.

pow(x,n):

    = 1 ... n=0

    = 0 ... x=0

    = x ... n=1

    = pow(x,n/2) * pow (x,n/2) ... n = even

    = x * pow(x,n/2) * pow(x,n.2) ... n = odd

Now lets calculate 2^(37) with this approach -

2^(37) =

     = 2 * 2^(18) * 2^(18)

     =              2^(9) * 2^(9)

     =                      2 * 2^(4) * 2^(4)

     =                                  2^(2) * 2^(2)

     =                                          2 * 2

This function is not excessive and hence it reuses the values once calculated. Thus only 7 multiplications are required to calculate 2^(37).

Answer 2

You can calculate the power of a number in logN time instead of linear time.

int cnt = 0;

// calculate a^b
int pow(int a, int b){
    if(b==0) return 1;
    if(b%2==0){
        int v = pow(a, b/2);
        cnt += 1;
        return v*v;
    }else{
        int v = pow(a, b/2);
        cnt += 2;
        return v*v*a;        
    }
}

Number of multiplications will be 9 for the above code as verified by this program.

Answer 3

Doing it slightly differently than invin did, I come up with 8 multiplications. Here's a Ruby implementation. Be aware that Ruby methods return the result of the last expression evaluated. With that understanding, it reads pretty much like pseudo-code except you can actually run it:

$count = 0

def pow(a, b)
  if b > 0
    $count += 1    # note only one multiplication in both of the following cases
    if b.even?
      x = pow(a, b/2)
      x * x
    else
      a * pow(a, b-1)
    end
  else             # no multiplication for the base case
    1
  end
end

p pow(2, 37)       # 137438953472
p $count           # 8

Note that the sequence of powers with which the method gets invoked is

37 -> 36 -> 18 -> 9 -> 8 -> 4 -> 2 -> 1 -> 0

and that each arrow represents one multiplication. Calculating the zero^th power always yields 1, with no multiplication, and there are 8 arrows.

Since xⁿ = (x^n/2)² = (x²)^n/2 for even values of n, we can derive this subtly different implementation:

$count = 0

def pow(a, b)
  if b > 1
    if b.even?
      $count += 1
      pow(a * a, b/2)
    else
      $count += 2
      a * pow(a * a, b/2)
    end
  elsif b > 0
    a
  else
    1
  end
end

p pow(2, 37)       # 137438953472
p $count           # 7

This version includes all of the base cases in the original question, it's easy to run and confirm that it calculates 2^37 in 7 multiplications, and doesn't require any allocation of local variables. For production use you would, of course, comment out or remove the references to $count.