from jyquickhelper import add_notebook_menu
add_notebook_menu()

"""
Explanation: Calculer x**n le plus rapidement possible
End of explanation
"""


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 ) ) )

"""
Explanation: Enoncé
Comme $n$ est entier, la façon la plus simple est de calculer $xx...*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$.
End of explanation
"""


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 ) ) )

"""
Explanation: 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}$.
End of explanation
"""


