.. _exercicexnrst: =================================================== 1A.algo - Calculer x**n le plus rapidement possible =================================================== .. only:: html **Links:** :download:`notebook `, :downloadlink:`html `, :download:`python `, :downloadlink:`slides `, :githublink:`GitHub|_doc/notebooks/1a/exercice_xn.ipynb|*` C’est un exercice courant lors des entretiens d’embauche. Il faut savoir ce qu’est la dichotomie et la notation binaire d’un nombre. .. code:: ipython3 from jyquickhelper import add_notebook_menu add_notebook_menu() .. contents:: :local: Enoncé ~~~~~~ Comme :math:`n` est entier, la façon la plus simple est de calculer :math:`x \times x \times ... \times x` mais existe-t-il plus rapide que cela ? Solution ~~~~~~~~ L’idée de départ consiste à écrire :math:`x^{2n}=(x^n)^2`. En extrapolant, on en déduit que si :math:`n=2^k`, alors le coût du calcul de :math:`x^n` consistera en :math:`k` itérations en on :math:`2^k`. .. code:: ipython3 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 ) ) ) .. parsed-literal:: 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 :math:`n` n’est pas une puissance de 2, il suffit que le décomposer en écriture binaire. Si :math:`n = \sum_k a_k 2^k`, avec :math:`a_k \in \{0,1\}`, alors :math:`x^n = \prod_k x^{a_k 2^k}`. .. code:: ipython3 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))) .. parsed-literal:: 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