Exponentiation modulaire très rapide

Messages postés
837
Date d'inscription
dimanche 20 juillet 2014
Dernière intervention
9 avril 2016
- - Dernière réponse : lespinx
Messages postés
97
Date d'inscription
lundi 9 octobre 2006
Dernière intervention
7 décembre 2018
- 11 avril 2016 à 11:31
Bonjour,
Savez vous comment cette algorithme fonctionne réellement?
Je cherche a savoir comment ça se fait que après que la fonction puis soit appelé jusqu'à k=1 alors elle arrive a revenir en arrière et retrouver son chemin pour donner la bonne solution (je cherche donc des caractéristiques propres a python sur les fonctions récursives)
Si quelqu'un peut m'expliquer le principe de cette pile d'éxécution (si c'est bien cela), j'en serait ravi.

Voici le code:
import time
a=int(input())
k=int(input())
n=int(input())
hey=time.time() #rajouter pour obtenir le temps
def puis(a,k,n):
if k==0:
return 1
b=puis(a,(k//2),n)
if k%2==0:
return ((b*b)%n)
return ((b*b*a)%n)
print(puis(a,k,n))
ho=time.time()
print(ho-hey)


Merci d'avance
Afficher la suite 

Votre réponse

1 réponse

Messages postés
97
Date d'inscription
lundi 9 octobre 2006
Dernière intervention
7 décembre 2018
0
Merci
Bonjour,

A chaque exécution de la boucle récursive il y a sauvegarde du contexte à cet instant (variables, pointeurs, etc) il y a donc un empilement de zones mémoire.
Il faut qu'il y ai dans le programme une condition de sortie sinon le nombre d'appels récursifs est limité par un paramètre Python et aussi bien sur par la quantité de mémoire disponible.

Voir http://igm.univ-mlv.fr/~rispal/W3bis/src/python/cours2/CM_5.pdf
Commenter la réponse de lespinx

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.