TP1 🥕 Calcul de racines

🎯 Objectifs pédagogiques

À la fin de ce travail, vous serez capable de :

• Utiliser des variables, types de base, opérateurs et fonctions
• Utiliser des structures conditionnelles et expressions logiques
• Utiliser des structures répétitives
• Décomposer un algorithme en fonctions réutilisables
• Évaluer la performance d’un algorithme avec des mesures de temps
• Appliquer la logique pour résoudre un problème numérique complexe sans bibliothèque
• Valider le fonctionnement de vos algorithmes à l'aide de jeux d'essais

🧠 Contexte

Un ordinateur, c’est très rapide, mais pas très intelligent. On va en profiter pour lui faire calculer la racine carrée… de façon très bête.

Vous devez implémenter deux méthodes de calcul « brutales » d’une racine carrée :

1. Une méthode chiffre par chiffre, par essais successifs
2. Une méthode par dichotomie (recherche binaire)

Puis vous devrez :

• Comparer ces méthodes à la fonction standard math.sqrt
• Étendre le calcul à une racine n-ième

Créer le projet

Pour faire ce TP, vous devez créer un nouveau projet PyCharm et utiliser un répertoire GitHub dès le début.

• Si votre enseignant utilise GitHub Classroom, utilisez le répertoire créé par votre enseignant.
• Si votre enseignant n'utilise pas GitHub Classroom, créez votre propre répertoire et partagez-lui l'accès en lecture.

Plagiat

Si votre travail est suspecté de plagiat (code copié d'un(e) autre étudiant(e), code généré par IA, notions non abordées en classe, etc.), deux choses peuvent se produire :

• Le plagiat est prouvé par nos outils : note de 0, automatiquement.
• Le plagiat est plutôt évident, mais une validation est requise : vous serez convoqué(e) au bureau de votre enseignant(e). Vous devrez répondre à certaines questions pour prouver que vous comprenez et maîtrisez le code qui a été utilisé. Si vous ne réussissez pas à répondre à certaines questions, vous aurez la note de 0 (si vous ne comprenez pas votre propre code, c'est que vous avez plagié, d'une manière ou d'une autre).

1 point Répertoire Git et documentation des fonctions

• Au moins 5 commits de tailles comparables (il n'y a pas un commit avec tout dedans et les autres vides)
• Les commits décrivent l'avancement du projet dans un français sans faute (voir instructions)
• Chaque fonction doit être documentée à l'aide d'un docstring dans un français sans faute : description de la fonction, paramètres, limites et exceptions possibles.

6 points 🔧 Calculer la racine carrée « à la main »

Voici 2 méthodes brutes pour calculer la racine carrée d'un nombre.
Pour les décrire, supposons que nous cherchons la racine carrée de 8.

➤ Méthode 1 : Chiffre par chiffre

On construit le résultat décimale par décimale, en commençant par la plus grande.

Pour 8, on commence donc par l'unité :

• 0² = 0
• 1² = 1
• 2² = 4
• 3² = 9

Comme 8 est entre 4 et 9, on sait que la racine de 8 est entre 2 et 3, car 3² est plus grand que 8. Donc, la racine de 8 ressemble à 2 point quelque chose (ex : 2.0..., 2.1..., ..., 2.9...).

On passe à la première décimale :

• 2.0² = 4
• 2.1² = 4.41
• 2.2² = 4.84
• 2.3² = 5.29
• 2.4² = 5.76
• 2.5² = 6.25
• 2.6² = 6.76
• 2.7² = 7.29
• 2.8² = 7.84
• 2.9² = 8.41

La racine de 8 ressemble donc à 2.8...., car 2.9² est plus grand que 8.

Et on fait ainsi de suite pour les décimales suivantes. On fait des essais successifs pour chaque décimale jusqu’à la précision désirée.

➤ Méthode 2 : Dichotomie

On cherche la racine dans un intervalle [bas, haut] qui se réduit de moitié à chaque étape.

On commence par déterminer l'intervalle initial :

• Si n ≥ 1 : intervalle initial = [0, n]
• Si 0 < n < 1 : intervalle initial = [n, 1]
• Si n = 0 : la racine est 0
• Si n < 0 : la racine n'existe pas dans les réels (on lève une exception)

Par la suite, on va réduire l'intervalle de moitié de la manière suivante :

• On calcule le milieu = (bas + haut) / 2
• Si milieu² est plus petit que n, on déplace bas = milieu
• Si milieu² est plus grand ou égal à n, on déplace haut = milieu

On répète l'opération de réduction de l'intervalle jusqu'à ce que la largeur de l’intervalle (haut - bas) soit inférieure à la précision souhaitée. Dans ce cas, la racine est approximée par (bas + haut) / 2.

Exemple (racine de 8, 3 décimales de précision) On arrête quand la largeur de l’intervalle < 0.001 :

• [0, 8] → largeur = 8 > 0.001 → on continue
• [0, 4] → largeur = 4 > 0.001 → on continue
• [2, 4] → largeur = 2 > 0.001 → on continue …
• [2.828125, 2.8291015625] → largeur = 0.0009765625 < 0.001 → on arrête

Résultat ≈ (2.828125 + 2.8291015625) / 2 = 2.82861328125 ≈ 2.829 (arrondi à 3 décimales).

Pour chacune des deux méthodes, vous devez créer une fonction qui prend un nombre en paramètre et qui retourne sa racine carrée en utilisant cette méthode.

La précision doit être entre 4 et 14 décimales à votre discrétion.
Supérieur à 14 décimales, le calcul prend trop de temps et le programme peut arrêter de fonctionner.

✅ Tests attendus

Tester vos 2 fonctions à l'aide d'appel de fonction similaire à ci-dessous.
Lorsque vous obtenez des résultats similaires, retirez ces tests de votre code.

Remarque : les dernières décimales peuvent varier selon le niveau de précision codée dans vos fonctions. Les résultats affichés sont les résultats de math.sqrt()

print(nom_de_la_fonction(0))    # 0.0
print(nom_de_la_fonction(0.1))  # 0.31622776601683794
print(nom_de_la_fonction(0.2))  # 0.4472135954999579
print(nom_de_la_fonction(0.9))  # 0.9486832980505138
print(nom_de_la_fonction(8))    # 2.8284271247461903
print(nom_de_la_fonction(9))    # 3.0
print(nom_de_la_fonction(81))   # 9.0
print(nom_de_la_fonction(123))  # 11.090536506409418
print(nom_de_la_fonction(999))  # 31.606961258558215
print(nom_de_la_fonction(-3))   # Doit lever une exception

2 points 📈 Comparaison des performances

Vous allez comparer vos 2 fonctions avec la fonction math.sqrt pour comparer leurs performances.

Pour chacune des 3 méthodes (fonction 1, fonction 2, math.sqrt) vous devez :

• À l'aide d'une boucle, appeler la fonction 100 000 fois avec un nombre flottant aléatoire
  • Utilisez un nombre flottant aléatoire différent à chaque appel
  • Les nombres flottants générés doivent être compris entre 10 et 10 000
• Calculer le temps total nécessaire pour réaliser les 100 000 appels (en ms)
• Afficher :
  • Le temps de calcul total (en millisecondes)
  • Le temps moyen par appel de la fonction

Exemple d'affichage attendu (les valeurs sont fictives) :

Résultats des performances :
Méthode 1 (chiffre par chiffre) : Temps total = 150 ms, Temps moyen = 0.0015 ms
Méthode 2 (dichotomie)          : Temps total = 50 ms, Temps moyen = 0.0005 ms
Méthode 3 (math.sqrt)           : Temps total = 10 ms, Temps moyen = 0.0001 ms

1 point 🌱 Généraliser à une racine n-ième

Pour chacune de vos 2 fonctions, faites-en une copie, nommez-la différemment, et généralisez-la pour qu'elle calcule la racine n-ième d'un nombre.

Pour cela, vous devez ajouter un paramètre base à vos nouvelles fonctions (ex. : 2 pour racine carrée, 3 pour racine cubique, etc.).
Il suffit ensuite de faire un changement minime aux 2 algorithmes pour calculer n'importe quelle racine n-ième.

Appelez chacune de ces 2 nouvelles fonctions et affichez les résultats pour la racine carrée, cubique et quatrième de 8, 9, 81 et 123.

Fonctionnement global 2 points négatifs

Le projet fonctionne sans plantage et correctement, et le code est clair et facile à lire. Ce pointage fonctionne en négatif. Si le projet fonctionne correctement en tout temps, vous conservez votre note. Dans le cas contraire, vous perdez des points avec un maximum de 2.

• Plantage -1 point
• Code illisible -1 point
• Information affichée incohérente -1 point
• Autre cas...