I have designed an O(logn) algorithm to raise an integer x to the power of n. How to implement this as a recursion in python?

Admin 1
Viewed 188

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.

Also, I am aware of the well-established log(n) algorithm that had been given in some of the answer already. Right now I am obsessed with implementing the version that I wrote above. Although I understand there is no significant advantage, but since I spend so much time on it, I just want to know what is the neat way of writing this out in a recursive python function.

Thanks for your help again.

recursion time-complexity algorithm python
3 Answers
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

user_66874450

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.

user_11965490

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)

Or this even more compact version (based on Yves' suggestion):

def pRaise(n,x):
    return (1,n)[x%2] * pRaise(n*n,x//2) if x else 1
user_52375600
Related