Discussion :

[blaidddrwg]

Bonsoir,

Pour m'exercer, j'ai programmé une exponentiation modulaire qui est très efficace ( https://fr.wikipedia.org/wiki/Exponentiation_modulaire , dernière méthode exposée).
Pour résumer, il faut convertir l'exposant en binaire et en partant de la droite, faire certaines opérations si on rencontre un 0 ou 1.
Mon code semble fonctionnel (je compare le résultat avec la fonction powmod de gmpy2), cela fonctionne.
Mais cela déraille avec de plus grands nombres, mais parfois aussi avec de plus petits nombres.

Ma question est : ai-je fait une erreur quelque part ou alors c'est la conversion en binaire sur des grands nombres qui ne se fait pas correctement ?

Voici le code :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
 
import time
import gmpy2
from gmpy2 import mpz
a=215
b=54
c=10485
 
exposant=bin(b)[2:]
exposant=list(exposant)
base=a
result=1
start=time.time()
 
for i in range(int(len(exposant))-1,0,-1):
    if int(exposant[i])==0:
        base=pow(base,2) % c
    else:
 
        result = (base*result) % c
        base = pow(base, 2) % c
end=time.time()
print("Méhode 4 : ",end-start," ",result)
 
start=time.time()
nombreb=gmpy2.powmod(a,b,c)
end=time.time()
print("Méthode 3 : ",end-start," ",nombreb)

Si quelqu'un pouvait m'éclairer, merci par avance !

[Invité]

Salut !

int(len(exposant)) pas besoin de mettre un int(), len() renvoie déjà un entier.

Question concernant la ligne 15 :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
for i in range(5,0,-1):
    i
 
 
5
4
3
2
1

Est-ce que c'est ce que tu souhaites ?
Ou plutôt :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
for i in range(5,-1,-1):
    i
 
 
5
4
3
2
1
0

[Sve@r]

Bonjour

Est-ce que c'est ce que tu souhaites ?
Ou plutôt :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
for i in range(5,-1,-1):
    i
 
 
5
4
3
2
1
0

Bien vu
Sauf qu'en réalité ça ne sert à rien du tout. Wikipedia donne un algo présenté comme étant le plus rapide, suffit de l'appliquer sans se poser de questions

Code python :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
def expo(b, e, m):
	res=1
	while e > 0:
		if e&1: res=(res * b) % m
		e>>=1
		b=b**2 % m
	# while
	return res
# expo()

Même pas besoin de convertir l'exposant en binaire, la conversion se fait implicitement lors de l'évaluation de e&1 puis sa division par 2.
Je l'ai testé sur les nombres de l'exemple (b=4, e=13, m=497) et ça donne le résultat attendu (445).

Pour m'exercer, j'ai programmé une exponentiation modulaire qui est très efficace ( https://fr.wikipedia.org/wiki/Exponentiation_modulaire , dernière méthode exposée).

Ben ton code ne ressemblait pas vraiment à ladite dernière méthode exposée...

En dehors du fait qu'il est vraiment vraiment pas performant, il contient au minimum deux inutilités

• exposant=list(exposant) totalement inutile, exposant étant une string, on peut parfaitement itérer dessus sans le transformer en liste. Mais si vraiment tu y tiens, alors autant le mettre en tuple qui est plus léger

• Code python :

  Sélectionner tout - Visualiser dans une fenêtre à part

  1
  2
  3
  4
  5
  if int(exposant[i])==0:
  	base=pow(base,2) % c
  else:
   	result = (base*result) % c
  	base = pow(base, 2) % c

  Répéter deux instructions identiques dans le "if" et dans le "else" (avec valeurs de variables identiques elles aussi) c'est une fois de trop...

[Invité]

& et >>= ça fait quoi ?

Je trouve la "Méthode utilisant moins de mémoire" plus explicite :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
def expo(b, e, m, r = 1):
    for i in range(0, e):
        r = (b*r)%m
    return r

[Sve@r]

& et >>= ça fait quoi ?

Oh non!!! Comment peux-tu ignorer cela??????
"&" est un opérateur bit à bit. Il produit un "et" entre chaque bit des opérandes demandés (on place les opérandes écrits en binaire l'un au dessus de l'autre et on fait le "&" sur les bits de chaque colonne). 6&3 donnera 2 (parce que 6 c'est 110 et 3 c'est 011 donc 1&0 fait 0; 1&1 fait 1 et 0&1 fait 0 ce qui donne 010 soit 2).
Dans le cas présent, il sert à détecter la valeur 0 ou 1 du dernier bit de "e"

">>n" (parce que ">>=n" c'est comme "+=n" c'est ">>n" avec affectation) produit un décalage vers la droite de n bits.
Et un décalage vers la droite de n c'est équivalent à une division par 2^n (exemple 14 c'est 1110 ; si je le décale vers la droite de 1 ça donne 0111 soit 7, qui est aussi égal à 14/2)

Donc au résultat, on teste le dernier bit de "e" puis on décale vers la droite ce qui supprime ce dernier bit et place le suivant à sa place. Or tester la valeur binaire du dernier bit puis décaler et supprimer ce dernier bit en le remplaçant par celui placé à sa gauche c'est exactement l'opération qu'on fait quand on convertit un décimal en binaire.

Je trouve la "Méthode utilisant moins de mémoire" plus explicite :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
def expo(b, e, m, r = 1):
    for i in range(0, e):
        r = (b*r)%m
    return r

Oui, plus explicite parce que plus simpliste. C'est celle qui utilise le principe que (b*b)%m est égal à ((b%m) * (b%m))%m. Mais mettre le résultat renvoyé en tant que paramètre entrant...
Accessoirement on doit pouvoir mettre la boucle et les opérations dans un reduce() mais j'ai pas encore trouvé comment...

[Invité]

Oh non!!! Comment peux-tu ignorer cela??????

Je ne manipule jamais des bits...

Mais mettre le résultat renvoyé en tant que paramètre entrant...

Ca faisait une ligne en moins, c'est original, n'est-ce pas ? ^^

Accessoirement on doit pouvoir mettre la boucle et les opérations dans un reduce()...

Ca ferait des lignes en moins !

[Sve@r]

Ca faisait une ligne en moins, c'est original, n'est-ce pas ? ^^

Ca ferait des lignes en moins !

Code python :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
from functools import reduce
def expo(b, e, m):
	return reduce(lambda b, r: (b*r)%m, (b,) * e, 1)

Un grand merci à la factorielle de tyrtamos, celle qui utilise reduce(), qui m'a beaucoup aidé. J'ai un peu de mal avec cette fonction.

En tout cas, plus je regarde la dernière méthode plus je suis impressionné. En divisant à chaque fois e par 2, ça transforme la complexité O(n) en O(log(n)). Si e vaut 1 267 650 600 228 229 401 496 703 205 376 (2**100), ça ne fera que 100 itérations...

[blaidddrwg]

Salut !

int(len(exposant)) pas besoin de mettre un int(), len() renvoie déjà un entier.

Question concernant la ligne 15 :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
for i in range(5,0,-1):
    i
 
 
5
4
3
2
1

Est-ce que c'est ce que tu souhaites ?
Ou plutôt :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
for i in range(5,-1,-1):
    i
 
 
5
4
3
2
1
0

Bonjour,

Oui c'est cela, j'ai fini par trouver de mon côté, merci pour vos réponses ainsi que pour l'optimisation

Bonne journée,