

In [ ]:

    
%%HTML
<style>
.container { width:100% } 
</style>

Efficient Computation of Powers

The function power takes two natural numbers $m$ and $n$ and computes $m^n$. Our first implementation is inefficient and takes $n-1$ multiplication to compute $m^n$.



In [ ]:

    
def power(m, n):
    r = 1
    for i in range(n):
        r *= m
    return r



In [ ]:

    
power(2, 3), power(3, 2)



In [ ]:

    
%%time
power(3, 10000)

Next, we try a recursive implementation that is based on the following formula: $$m^n = \left\{\begin{array}{ll} m^{n/2} \cdot m^{n/2} & \mbox{if $n$ is even}; \\ m^{n/2} \cdot m^{n/2} \cdot m & \mbox{if $n$ is odd}. \end{array} \right. $$



In [ ]:

    
def power(m, n):
    if n == 0:
        return 1
    p = power(m, n // 2)
    if n % 2 == 0:
        return p * p
    else:
        return p * p * m



In [ ]:

    
%%time
power(3, 10000)