Exponentiation modulaire très rapide

mr_demonicon 837 Messages postés dimanche 20 juillet 2014Date d'inscription 9 avril 2016 Dernière intervention - 9 avril 2016 à 18:52 - Dernière réponse : lespinx 96 Messages postés lundi 9 octobre 2006Date d'inscription 24 février 2018 Dernière intervention
- 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 

1 réponse

Répondre au sujet
lespinx 96 Messages postés lundi 9 octobre 2006Date d'inscription 24 février 2018 Dernière intervention - 11 avril 2016 à 11:31
0
Utile
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.