Algorithmique et racine carrée en seconde, compléments publié le 03/03/2020  - mis à jour le 19/03/2020

Parcours sur les algorithmes d'approximation de racines carrées

Un peu de nostalgie : l’algorithme de la potence

Cette partie n’a pas été abordée en classe, elle figure dans cet article à titre de complément culturel

L’algorithme de la potence, qui tient son nom de la disposition des calculs organisée autour d’une potence comme une division, est un algorithme qui était utilisé jusqu’au milieu du vingtième siècle pour extraire des racines carrées à la main.

Le principe est le suivant : on sépare les chiffres du nombre par paires en commençant à partir de la virgule. On place le nombre dont on veut extraire la racine en haut, de la même façon que lorsqu’on effectue une division selon la méthode classique ; la racine carrée sera inscrite à la place réservée normalement au diviseur dans une division posée classique.
On commence par abaisser la première tranche $t_0$ et on cherche le plus grand nombre $x$ tel que $x^2\leqslant t_0$. Ce nombre $x$ est le premier chiffre de la racine (à partir de la gauche) et on le note $r$. On soustrait ensuite $x^2$ à $t_0$ de sorte que l’on ait un premier reste.
À chaque étape :

  • on abaisse la paire de chiffres suivante et on la place au côté d’un reste éventuel de l’étape précédente (initialement nul) ;
  • soit $r$ le résultat intermédiaire de la racine carrée obtenu précédemment (égal à zéro au début). On cherche le plus grand chiffre $x$ tel que le nombre $y=(20r + x)x$ ne dépasse pas le reste courant ;
  • on complète $r$ en plaçant la décimale $x$ à sa droite, pour former le nouveau résultat intermédiaire ;
  • on soustrait $y$ de la valeur courante pour former le nouveau reste ;
  • si le reste est nul et qu’il n’y a plus de chiffre à abaisser alors l’algorithme se termine sinon on recommence.

Exemple : Extraction de $\sqrt{238}$ au millième

  • étape 1 : écrire le nombre dont on veut extraire la racine comme le dividende d’une division.
  • étape 2 : séparer en tranches de deux chiffres à partir de la droite ; la dernière tranche à gauche peut
    n’avoir qu’un chiffre
  • étape 3 : extraire la racine carrée de la première tranche, c’est-à-dire trouver le plus grand nombre $x$ tel que $x^2\leqslant 2$. Ici c’est 1. L’écrire au diviseur.
  • étape 4 : soustraire le carré de ce nombre à la tranche et abaisser la tranche suivante. On a 138
  • étape 5 : prendre le double du chiffre du diviseur,
  • étape 6 : chercher le chiffre qui donne le produit le plus proche, en restant inférieur
    au nombre abaissé : par exemple ici on doit faire $2\ldots \times \ldots\leqslant 138$, on essaie avec $21\times 1$, $22\times 2$, $23\times 3$,... et on obtient $25\times 5=125$. Le deuxième chiffre de la racine est 5
  • étape 7 : écrire le chiffre obtenu au diviseur et soustraire le produit obtenu, 125, au nombre abaissé
  • étape 8 : abaisser la tranche suivante : si on est au bout du nombre entier et que l’on veut poursuivre l’extraction,
    on abaisse une paire de zéros et on met une virgule au diviseur.
  • étape 9 et 10 : poursuivre le processus jusqu’à la précision demandée, chaque tranche de deux chiffres abaissée produisant un chiffre supplémentaire dans l’écriture de la racine .
Illustration de l'algorithme de la potence

Cette figure illustre le fonctionnement de l’algorithme de la potence utilisé pour extraire des racines carrées à la main

Pour des exemples de mise en œuvre et une justification théorique de la méthode, vous pouvez visualiser la vidéo de la chaîne YouTube Hans Samble - Maths au lycée, qui propose par ailleurs de très nombreuses vidéos mathématiques de qualité :

Calcul d'une racine carrée à la main Exemples et explications

L’implémentation en Python s’appuie sur les chaînes de caractères, un nombre entier pouvant être convertie en une chaine de caractères qui sera ensuite découpée en tranches de longueur 2. Le programme ci-dessous s’applique à des entiers car l’algorithme de la potence ne tient pas compte de la virgule : un nombre décimal est considéré sans sa virgule et celle-ci peut être indiquée dans la racine mais non prise en compte dans le processus de calcul.

Il faut au préalable construire une fonction de tranchage qui tronçonne la chaine formée par le nombre en chaînes de deux chiffres (voir exécution en ligne) :

Bloc de code informatique : voir l'article sur le site.
  
  1. def decoupage_tranches(nombre):
  2.     """découpe un entier en blocs de 2 chiffres en partant de la droite"""
  3.     chaine_nombre = str(nombre)
  4.     liste_tranches = []
  5.     while len(chaine_nombre) >= 2 :
  6.         tranche = chaine_nombre[-2]+ chaine_nombre[-1] # extraction de la tranche la plus à droite
  7.         liste_tranches = [tranche] + liste_tranches # ajout de la tranche en tête de liste
  8.         chaine_nombre = chaine_nombre[:-2] # on prend la liste tronquée de ses deux derniers éléments
  9.     if chaine_nombre != '': # on rajoute un éventuel reste si le nombre de chiffres est impair
  10.         liste_tranches = [chaine_nombre] + liste_tranches
  11.     return liste_tranches

l’appel de cette fonction donne une liste de chaînes de deux caractères, sauf éventuellement pour la dernière :

Bloc de code informatique : voir l'article sur le site.
  
  1. >>> decoupage_tranches(670012000)
  2. ['6', '70', '01', '20', '00']

Cette fonction est ensuite utilisée pour mettre en œuvre l’algorithme de la potence (voir exécution en ligne) :

Bloc de code informatique : voir l'article sur le site.
  
  1. def racine_potence(nombre,nb_decimales):
  2.     """renvoie la racine carrée d'un nombre entier, avec une précision spécifiée par nb_decimales"""
  3.     nombre = int(str(nombre)+'00'*nb_decimales) # reconstitution du nombre en l'y adjoignant des tranches de '00' pour aller jusqu'à la précision souhaitée
  4.     liste_tranches = decoupage_tranches(nombre)
  5.     # gestion de la première tranche
  6.     dividende = int(liste_tranches.pop(0)) # on enlève la première tranche de la liste
  7.     chiffre = 0
  8.     while chiffre**2 <= dividende : # recherche de la racine carrée de la première tranche
  9.         chiffre = chiffre + 1
  10.     chiffre = chiffre - 1
  11.     racine = chiffre
  12.     reste = dividende - chiffre**2
  13.     # gestion des autres tranches
  14.     while liste_tranches != []:
  15.         dividende = int(str(reste) + liste_tranches.pop(0))
  16.         double = 2 * racine
  17.         chiffre = 0
  18.         while (double*10 + chiffre)*chiffre <= dividende :
  19.             chiffre = chiffre + 1
  20.         chiffre = chiffre - 1
  21.         racine = 10*racine + chiffre
  22.         reste = dividende - (double*10 + chiffre)*chiffre
  23.     return racine/10**(nb_decimales)

L’appel de la fonction donne :

Bloc de code informatique : voir l'article sur le site.
  
  1. >>> racine_potence(2387860,6)
  2. 1545.270202

Si l’on veut la racine carrée d’un nombre décimal, on le transforme en entier en le décalant d’un nombre pair de rangs $n=2p$ vers la droite et on calcule cet entier à la précision souhaitée puis on récupère la racine carrée du nombre décimal en décalant de $p$ rang(s) vers la gauche :

Bloc de code informatique : voir l'article sur le site.
  
  1. # calcul de la racine carrée de 1240.67835
  2. >>> racine_potence(1240678350,2) # on décale de 6 chiffres pour avoir un nombre entier
  3. 35223.26 # on décale de 6/2=3 chiffres vers la gauche pour retrouver la racine carrée du nombre de départ
  4. >>> math.sqrt(1240.67835)
  5. 35.22326432913338
Document joint

Cette archive contient tous les fichiers (fichiers tex, GeoGebra, scripts Python, illustrations,...) utilisés lors de la séquence.