Calculer x**n le plus rapidement possible

Links: notebook, html ., PDF, python, slides ., GitHub

C’est un exercice courant lors des entretiens d’embauche.

from jyquickhelper import add_notebook_menu
add_notebook_menu()
Plan
run previous cell, wait for 2 seconds

Enoncé

Comme n est entier, la façon la plus simple est de calculer x \times x \times ... \times x mais existe-t-il plus rapide que cela ?

Solution

L’idée de départ consiste à écrire x^{2n}=(x^n)^2. En extrapolant, on en déduit que si n=2^k, alors le coût du calcul de x^n consistera en k itérations en on 2^k.

def puissance2k(x,k):
    while k > 0 :
        x *= x
        k -= 1
    return x

for i in range(0,4) :
    print ( "2^(2^{0})=2^{1}={2}".format( i, 2**i, puissance2k ( 2, i ) ) )
2^(2^0)=2^1=2
2^(2^1)=2^2=4
2^(2^2)=2^4=16
2^(2^3)=2^8=256

Lorsque n n’est pas une puissance de 2, il suffit que le décomposer en écriture binaire. Si n = \sum_k a_k 2^k, avec a_k \in \{0,1\}, alors x^n = \prod_k x^{a_k 2^k}.

def puissance(x,n):
    r = 1
    while n > 0 :
        if n % 2 == 1 : r *= x
        x *= x
        n //= 2
    return r

for i in range(0,9) :
    print("2^{0}={1}".format(i, puissance( 2, i)))
2^0=1
2^1=2
2^2=4
2^3=8
2^4=16
2^5=32
2^6=64
2^7=128
2^8=256