Projet : implémentation des algorithmes d'exponentiation
On vérifie expérimentalement que nos calculs théoriques sont validés expérimentalement. On codera et testera nos algorithmes, donc vérifiez que vous avez les prérequis.
Mise en place
On va utiliser les méthodes d'écriture de code déjà vues. Pour une piqûre de rappel :
Structures
- créez un dossier nommé
exponentiationoù vous placerez vos fichiers - créez un projet vscode dans ce dossier
- créez dans ce dossier les 3 fichiers de la trinité du code :
main.pyexponentiation.pytest_exponentiation.py
Vérifications
- on vérifie que python est OK avec le terminal et avec vscode
- on vérifie que le linter est actif dans vscode
- on vérifie que les tests fonctionnent (en créant un test bidon dans
tests_exponentiation.pyet en vérifiant quepytestet vscode le trouvent)
Le code
Algorithme naif
- dans le fichier
exponentiation.py: implémentez l'algorithme naïf itératif dans une fonction nomméepuissance_naif(utilisez des noms explicites). - dans le fichier
test_exponentiation.py: implémentez les tests de l'algorithme naïf itératif :- vérifiez que les cas simples avec nombre et/ou exposant à 1 fonctionnent
- vérifiez qu'un cas général est correct (comme $2^3$ par exemple)
Vérifier que vos tests se lancent bien dans le terminal.
Pour les tests, on utilisera les règles suivantes :
Organisation des tests :
- un fichier de test par fichier de code. Chaque fichier de test sea nommé :
test_[nom du fichier de code].pyoù [nom du fichier de code] sera le nom du fichier (ne mettez pas les []) - chaque test sera nommé en 3 parties :
test_[nom de la fonction_testée]_[ce que l'on teste]où[nom de la fonction_testée]est le nom de la fonction testée (ne mettez pas les[]) et[ce que l'on teste]une description succincte (en 1 ou 2 mots max) de ce que l'on teste. - un test doit tester une unique chose. On peut se permettre d'avoir plusieurs
assertpar fonction de test du moment que ce qu'on test peut être qualifié par un nom précis (la partie[ce que l'on teste]du nom de la fonction de test)
Terminons cette partie en utilisant le débogueur :
Dans le programme principal, calculez l'exponentiation d'un entier par un autre (ces entiers pourront être issus de deux variables ou demandées à l'utilisateur), puis rendez la.
En utilisant le débogueur, vérifiez l'invariant de boucle (pour pourrez utiliser un espion et un log breakpoint).
Algorithme rapide
- dans le fichier
exponentiation.py: implémentez l'algorithme rapide dans une fonction nomméepuissance_rapide - dans le fichier
test_exponentiation.py: implémentez les tests de l'algorithme rapide en faisant les mêmes tests que pour l'algorithme naïf.
Vérifier que vos tests se lancent bien dans le terminal.
Terminons cette partie en utilisant le débogueur :
Dans le programme principal, calculez l'exponentiation d'un entier par un autre (ces entiers pourront être issue de variables ou demandés à l'utilisateur), puis rendez la issue du calcul rapide.
En utilisant le débogueur, vérifiez que l'invariant de boucle est vérifié (pour pourrez utiliser un espion et un log breakpoint).
Programme principal
Créer un programme principal (dans le fichier main.py) qui demande à l'utilisateur un exposant $n$. Ce programme donne ensuite résultat et le temps mis (utilisez le chronomètre time.perf_counter_ns pour mesurer le temps avant et après exécution du code) pour exécuter $3^n$ avec l'algorithme naïf et avec l'algorithme rapide.
Mesure de complexité
On va utiliser ce que l'on a fait lorsque l'on a appris à mesurer des complexités :
Commençons par ajouter nos méthodes de mesures :
- Ajoutez le fichier
mesure_temps.pyau projet. - Créez un fichier
main_temps.pyqui va contenir notre code de mesure.
Temps de calcul
Dans le fichier main_temps.py déterminez l'exposant max pour calculer $3^n$ en 0.1 secondes.
Je trouve N_max = 6553 sur mon ordinateur.
On peut maintenant représenter les courbes de complexité :
Dans le fichier main_temps.py, procédez comme dans le cours pour afficher la courbe de complexité de l'algorithme naïf (faites 10 mesures).
Je trouve N_max = 6553 sur mon ordinateur.
La courbe devrait être linéaire alors qu'elle ne l'est pas. On a déjà vu ce phénomène, corrigeons le :
Dans le fichier exponentiation.py, commentez la ligne effectuant la multiplication et refaite le graphique.
Comme les multiplication de nombres gigantesques seront aussi effectués par l'exponentiation rapide et que l'on veut que notre algorithme calcule bien ce qu'il doit faire :
Dé-commentez la ligne effectuant la multiplication et assurez vous que les tests passent.
On peut maintenant voir le temps mis pour l'exponentiation rapide :
En gardant le N_max déterminé en utilisant l'algorithme naïf, procédez comme dans le cours pour afficher la courbe de complexité de l'exponentiation indienne (faites 10 mesures).
Maintenant que l'on a les deux graphiques séparé, on peut rassembler les deux graphiques :
Mettez les mesures pour l'algorithme naïf et rapide sur le même graphique
Le temps mis par l'exponentiation rapide est très inférieur à celui effectué par l'algorithme d'exponentiation naif, on ne le voit pratiquement pas (la courbe semble toute plate).
Utilisez le code de ce lien pour utiliser ax.twinx qui permet de partager l'axe des abscisse en ayant deux axes des ordonnées et permettre de voir les 2 courbes,chacune ayant son axe des ordonnées.
Vous pourrez également changer la couleur d'un des dessins en ajoutant le paramètre color="orange" d'un des 2 plot par pour dessiner en orange.