0

I need to make a function power(x, n) that calculates x^n in n/2 steps.

I've made a recursive function that can calculate the power in n steps:

def simple_recursive_power(x, n):
    if n == 0:
        return 1
    return x * simple_recursive_power(x, n-1)

However, I need to halve the amount of steps needed (to be n/2). I think I need to use 'fast powering' but I have no idea how to implement that using recursion.

Thanks for any help.

2 Answers2

4

you can split number based on the even or odd, when split to two parts when even:

def simple_recursive_power(x, n):
    if n == 0:
        return 1

    if n % 2:
        return x * simple_recursive_power(x, n - 1)
    else:
        m = simple_recursive_power(x, n // 2)
        return m * m
recnac
  • 3,744
  • 6
  • 24
  • 46
0

I put my first answer at the end, my first answer is pointless. I have worked on renac's answer which is best recursive for doing this. And I don't figure it out why using recursion :

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


start = time.time()
a =simple_recursive_power(11, 5000000)
end = time.time()
print((end - start), ' s')


def simple_recursive_power(x, n):
    if n == 0:
        return 1
    if n % 4:
        return x * simple_recursive_power(x, n - 1)
    else:
        m = simple_recursive_power(x, n // 4)
        return m * m * m * m

start = time.time()
b = simple_recursive_power(11, 5000000)
end = time.time()
print((end - start), ' s')

start = time.time()
c = 11**5000000
end = time.time()
print((end - start), ' s')

the results are :

  • 3.190255641937256 s
  • 5.789834022521973 s
  • 3.141327142715454 s

11**5000000 is easier to understand, is as fast than recursive, why not use it ?

Is it because some processor architectures work well with recursive ?

The only way must be for multiprocessing, or for threading !!

My first answer:

I don't understand the point but.. this should work :

def simple_recursive_power(x, n):
    if n == 0:
        return 1
    elif n == 1:
        return x
    return x * x * simple_recursive_power(x, n - 2)

edit : n/3 steps :

def simple_recursive_power(x, n):
    if n == 0:
        return 1
    elif n == 1:
        return x
    elif n == 2:
        return x * x
    return x * x * x simple_recursive_power(x, n - 3)