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,