Projet : implémentation des algorithmes d'exponentiation

Prérequis

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 :

Prérequis

Structures

  1. créez un dossier nommé exponentiation où vous placerez vos fichiers
  2. créez un projet vscode dans ce dossier
  3. créez dans ce dossier les 3 fichiers de la trinité du code :
    • main.py
    • exponentiation.py
    • test_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.py et en vérifiant que pytest et vscode le trouvent)

Le code

Algorithme naif

  • dans le fichier exponentiation.py : implémentez l'algorithme naïf itératif dans une fonction nommée puissance_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 :

À retenir

Organisation des tests :

  • un fichier de test par fichier de code. Chaque fichier de test sea nommé : test_[nom du fichier de code].py où [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 assert par 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ée puissance_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 :

  1. Ajoutez le fichier mesure_temps.py au projet.
  2. Créez un fichier main_temps.py qui 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.