The function power(x,n) raises x to a positive integer power n. My algorithm is following: Write out n as a sum of power of 2. For example, 27 = 2^4 2^3 2^1 2^0

The essence of the algorithm is a recursive self-squaring one. So x^(2^4) is computed by recursively calling the self-squaring algorithm 4 times. Here comes the key part: memoizing the result in each recursion in a dictionary, so that x^2,x^4,x^8,x^16 are all in dictionary.

When computing 2^3, which involves self-squaring x three times, we can just look up the dictionary and no computation necessary. Same goes for x^2, and obviously 2^0 = 1

I can complete the code up to here. However, in the end we need to add everything up. I have no idea how to implement the addition part inside the recursive function, as it looks like once you implement the recursion, everything in the function will be recursively called. However we only need the addition once at the end.

Is this even possible to implement this idea as a recursion?

Thank you so much. ----------Adding my incomplete code below---------------------------------

def self_square(x,n,power_counter,past_result_dict): 

    if n in past_result_dict: 
        return past_result_dict[n],power_counter
     
    if n == power_counter:
        return x,power_counter

    if (n - power_counter) < power_counter:
        return x,power_counter
    ## This part will need more work for the algorithm to be complete!##
    ## e.g. When n - power_counter < power_counter, we need to set ##
    ## n = n - power_counter, and power_counter = 1, to recurse again##
    ## currently I am giving up and only returning the result up to the power_counter##
    ## so if n = 7, I can only compute up to n=4, and returning from here, instead of recursion on n = 3  ## 
        

    if (n - power_counter) >= power_counter:
        power_counter = power_counter * 2 
        x = x * x
        past_result_dict[power_counter] = x 
    
    return self_square(x,n,power_counter,past_result_dict)

## Trying to run the code with an example. 
x_initial = 3; n_initial = 7
past_result_dict_initial = {0:1, 1:x_initial}
self_square(x = x_initial, n = n_initial, power_counter = 1, past_result_dict = past_result_dict_initial)

Per my incomplete code above, if I currently run n_initial 7, it can compute only to the rounding down of 2's integer power, that is to the power of 4. I mean I can set up a for loop outside and rerun the function again on n = 3, and in that way I can easily add up the result. However that is ugly! I want to do it inside the one recursion function.

Thanks for your help again.

CodePudding user response：

class Solution {
    public double myPow(double x, int n) {
        
        if(n == 0){
            return 1;
        }
        
        double y = myPow(x, n/2);
        
        if(n > 0){
            if(n%2 == 0){
                return y * y;
            }else{
                return y * y * x;
            }
        }else{
            if(n%2 == 0){
                return y * y;
            }else{
                return y * y * 1/x;
            }
        }
    }
}

This is a Java solution to recursively find the power of any number. This works for positive and negative powers.

Time Complexity log(n)

This Wikipedia article talks more about it in depth: https://en.wikipedia.org/wiki/Exponentiation_by_squaring

CodePudding user response：

If n is even, let 2m, x^n = (x²)^m. If n is odd, let 2m 1, x^n = x (x²)^m.

def pow(x, n):
    if x < 3:
        # Low values handled directly
        if n == 2:
            return x * x
        elif n == 1:
            return x
        else:
            return 1

    m= n >> 1
    if n == m << 1:
        # Even power
        return pow(x * x, m)
    else:
        # Odd power
        return x * pow(x * x, m)

Personal note:

I always consider that is it a waste to use a power function for exponents 0, 1 and 2. So I would tend to avoid supporting the case n == 0 to spare a test; I could even skip 1 and 2 and hard-code directly for 3 and 4.

CodePudding user response：

Recurse with n x n^(x-1) when x is odd or (n^2)^(x//2) when it is even:

def pRaise(n,x):
    if x == 0: return 1
    return n*pRaise(n,x-1) if x%2 else pRaise(n*n,x//2)