TP1 🥕 Calcul de racines

Explications

Une vidéo expliquant en détail le TP et fournissant quelques conseils est disponible en bas de page.

🧠 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 :

une méthode par dichotomie (réduction d'un intervalle)
une méthode chiffre par chiffre (par essais successifs)

Puis vous devrez :

comparer ces méthodes à la fonction standard math.sqrt() en termes de performance
étendre le calcul à une racine n-ième

🎯 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

Récupérer le projet

Pour faire ce TP, votre enseignant a créé un dépôt de code personnel pour chaque étudiant.
Ce dépôt vous est propre et n'est accessible que par vous. Vous devez le récupérer (le cloner).

Utilisez ce dépôt tout au long du TP; ne créez pas de nouveau projet ni de nouveau dépôt.
Effectuez vos commits régulièrement dans ce dépôt (voir la consigne sur les commits ci-dessous).

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, valeur retournée, exceptions possibles, etc.
Votre dépôt contient déjà tous les fichiers nécessaires à la réalisation de votre TP :

tp1/
├── .gitignore        # ce fichier vous est fourni et sert à exclure les fichiers à ne pas versionner
├── racine.py         # doit contenir vos 2 fonctions pour les 2 méthodes différentes du calcul de la racine carrée
├── performance.py    # doit contenir vos tests de performance des fonctions du module "racine.py"
└── autocorrection.py # ce fichier vous est fourni et sert à l'autocorrection de votre travail

Les fichiers racine.py et performance.py sont ceux que vous devrez compléter.
Votre dépôt de code ne doit contenir aucun autre fichier que les 4 fichiers fournis.

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

Dans le script racine.py, vous devez créer 2 fonctions, soit une pour chacune des 2 méthodes du calcul de la racine carrée d'un nombre.

➤ Méthode 1 : Dichotomie (avec arrêt basé sur l’arrondi)

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

On commence par déterminer l'intervalle initial :

\text{Si} \begin{cases} n \ge 1 : & \text{intervalle initial} = [0, n],\\[1em] 0 < n < 1 : & \text{intervalle initial} = [n, 1],\\[1em] n = 0 : & \text{racine} = 0,\\[1em] n < 0 : & \begin{aligned} & \text{non défini dans } \mathbb{R} : \\[-0.5em] & \text{on lève une exception}. \end{aligned} \end{cases}

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

On calcule le milieu :

\text{milieu} = \frac{\text{bas} + \text{haut}}{2}

Puis :

\text{Si} \begin{cases} \text{milieu}^2 < n : & \text{on déplace } \text{bas} = \text{milieu},\\ \text{milieu}^2 \ge n : & \text{on déplace } \text{haut} = \text{milieu}. \end{cases}

On répète l'opération de réduction de l'intervalle jusqu'à ce que le critère d’arrêt soit atteint (voir ci-dessous).

🔎 Critère d’arrêt

On arrête lorsque les deux bornes donnent le même résultat, une fois arrondi à la précision demandée.

Par exemple, si on veut $k$ décimales, on arrête lorsque :

\text{round}(\text{bas}, k) = \text{round}(\text{haut}, k)

et ce résultat arrondi est la racine approximée.

Exemple (racine de $8$ , avec $5$ décimales)

On poursuit les itérations jusqu'à ce que :

\text{round}(\text{bas}, 5) = \text{round}(\text{haut}, 5)

Supposons qu’on obtienne :

bas = 2.8284225463867188
haut= 2.82843017578125

Alors :

round(2.828422..., 5) = 2.82842
round(2.828430..., 5) = 2.82843

→ On continue.

Plus tard :

bas = 2.8284263610839844
haut= 2.82843017578125

Alors :

round(2.8284263..., 5) = 2.82843
round(2.8284301..., 5) = 2.82843

→ On peut donc arrêter.

Résultat retourné : $2.82843$ .

➤ Méthode 2 : Chiffre par chiffre

On construit le résultat décimale par décimale, en partant de la gauche vers la droite.

Supposons que nous cherchons la racine carrée de $8$ .

🌕 Partie entière

On commence par déterminer la partie entière (à gauche de la virgule) de la racine carrée.

On fait des essais successifs pour trouver le plus grand entier dont le carré est inférieur ou égal à $8$ :

$0^2 = 0$
$1^2 = 1$
$2^2 = 4$
$3^2 = 9$

Puisque $3^2 > 8$ , on retient $2$ .

👉 À cette étape, on sait que la racine est dans l’intervalle :

2 \quad \le \quad \sqrt{8} \quad < \quad 3

Donc, la racine de $8$ ressemble à $2$ point quelque chose (ex : $2.0..., 2.1..., ..., 2.9...$ ).

🔢 Décimales

On va maintenant ajouter les décimales une à la fois.

Première décimale

On teste les valeurs possibles :

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

Puisque $2.9^2 > 8$ , on retient $2.8$ .

👉 On a maintenant :

2.8 \quad \le \quad \sqrt{8} \quad < \quad 2.9

Deuxième décimale

Même principe :

$2.80^2 = 7.84$
$2.81^2 = 7.8961$
$2.82^2 = 7.9524$
$2.83^2 = 8.0089$

Puisque $2.83^2 > 8$ , on retient $2.82$ .

👉 On a maintenant :

2.82 \quad \le \quad \sqrt{8} \quad < \quad 2.83

On répète ce processus pour chaque décimale jusqu’à atteindre la précision souhaitée.

⚙️ Traduction en algorithme

À chaque position décimale :

On fixe les chiffres déjà trouvés
On teste les chiffres de 0 à 9
On garde le plus grand chiffre tel que :

(\text{approximation})^2 \le n

👉 Cela correspond directement à :

une boucle sur les positions
une boucle imbriquée sur les chiffres de 0 à 9

≅ Arrondi ou pas ?

On retourne simplement la borne inférieure, c’est-à-dire le plus grand nombre construit tel que :

(\text{approximation})^2 \le n

👉 On obtient donc une troncature à la précision demandée.

Par exemple, si la vraie valeur est :

\sqrt{8} \approx 2.828427...

Avec une précision de 5 décimales, on retourne :

2.82842

(et non $2.82843$ ).

LES PARAMÈTRES
Ces deux fonctions doivent recevoir les deux paramètres suivants :

Le nombre dont on souhaite calculer la racine
- Vous devez valider que ce nombre est supérieur ou égal à zéro.
La précision souhaitée (ex. : 4 pour obtenir un maximum de 4 décimales) :
- Ce paramètre doit être facultatif (en configurant une valeur par défaut).
- Vous devez valider que la précision est comprise entre 4 et 10 décimales.

VALEUR RETOURNÉE
Concernant les valeurs retournées par ces 2 fonctions :

Elles doivent retourner simplement le résultat en format numérique, comme le fait math.sqrt().
Les fonctions ne doivent pas appeler la fonction print.
Certaines racines n'ont pas de décimales ou en possèdent peu :
- Exemple : La racine carrée de 9 est 3.0, peu importe la valeur de votre précision souhaitée.
- Ne rajoutez pas de zéros inutiles à votre réponse.

GARDER LE MODULE RACINE PROPRE

Votre module racine doit contenir uniquement ces 2 fonctions et aucune instruction dans ce module ne doit être laissée à l'extérieur de ces 2 fonctions.

✅ Autocorrection

Vous devez exécuter fréquemment le script autocorrection.py. Votre enseignant va se servir de ce script pour valider le bon fonctionnement de vos 2 fonctions.

Le script nécessite au préalable l'installation du package requests (voir la procédure d'installation d'un package). Cette bibliothèque permet de télécharger des fichiers en ligne par programmation ; elle est utilisée ici pour vérifier si une nouvelle version du script est disponible et pour la télécharger automatiquement.

Limitations du script
Le script possède certaines limites et ne vérifie pas les points suivants :

La cohérence de vos docstrings ainsi que la qualité du français.
La présence de code inutile ou redondant à l'intérieur de vos fonctions.
Le respect de la consigne exigeant au moins cinq commits dans votre dépôt GitHub.
Le bon fonctionnement du script performance.py.

2 points 📈 Comparaison des performances

Dans le script performance.py, vous allez comparer vos 2 fonctions du module racine 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 pour les 100 000 appels (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 (dichotomie)          : Temps total = 50 ms, Temps moyen = 0.0005 ms
Méthode 2 (chiffre par chiffre) : Temps total = 150 ms, Temps moyen = 0.0015 ms
Méthode 3 (math.sqrt)           : Temps total = 10 ms, Temps moyen = 0.0001 ms

Votre format d'affichage devrait être identique.
Le script doit s'éxécuter en moins de 60 secondes.

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

Vous devez transformer vos deux fonctions du module racine afin qu'elles puissent calculer la racine n-ième d'un nombre.

Ajout d'un nouveau paramètre

Ajoutez, à vos deux fonctions, un paramètre degre correspondant à l’indice de la racine (2 pour une racine carrée, 3 pour une racine cubique, etc.).
Ce paramètre doit être optionnel et avoir la valeur 2 par défaut.
L'ordre des paramètres doit être exactement le suivant (sans quoi l'autocorrection ne fonctionnera pas) :
- le nombre
- le degré de la racine
- la précision

Règles de validation et logique

Nombres négatifs
- Le calcul de la racine d'un nombre négatif doit être possible uniquement si le degré est impair (ex. : la racine cubique de -27 est -3).
- Dans tous les autres cas, une exception doit être levée.
Validation du degré
- La valeur du paramètre degre ne doit pas être inférieure à 1.
- Vous devez valider la valeur passée en paramètre.

Vérification du bon fonctionnement

Le script autocorrection.py ajustera les tests en conséquence dès qu'il détectera le paramètre supplémentaire dans vos fonctions.

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 (un script qui plante lorsqu'on l'exécute) -1 point
Code illisible (ex : noms de variables incompréhensibles, difficulté à comprendre le code) -1 point
Information affichée incohérente -1 point
Autre cas...

❗🤖 👀 🚫

🔎 Critère d’arrêt​

Exemple (racine de 888, avec 555 décimales)​

🌕 Partie entière​

🔢 Décimales​

Première décimale​

Deuxième décimale​

⚙️ Traduction en algorithme​

≅ Arrondi ou pas ?​

Explications détaillées​