Calculer x**n le plus rapidement possible#
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.
Enoncé#
Comme est entier, la façon la plus simple est de calculer mais existe-t-il plus rapide que cela ?
Solution#
L’idée de départ consiste à écrire . En extrapolant, on en déduit que si , alors le coût du calcul de consistera en itérations en on .
[1]:
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’est pas une puissance de 2, il suffit que le décomposer en écriture binaire. Si , avec , alors .
[2]:
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
[ ]: