Racine carrée : le CNRS revient sur un algorithme « jugé inutile »
Le 01 septembre 2020 à 07h59
3 min
Sciences et espace
Sciences
Les mathématiques ont été largement marquées par l’arrivée des ordinateurs et leur gigantesque puissance de calcul. Depuis des dizaines d’années, les cours (notamment à l’université) se sont largement adaptés et Patrick Popescu-Pampu du CNRS revient sur le cas de la racine carrée.
Il existe une méthode pour la trouver sur n’importe quel nombre… mais combien seraient capables de la réciter, voire simplement de s'être un jour posé la question de savoir si elle existait ? À priori pas grand monde… Pourtant, le professeur à l'Université de Lille rappelle qu’elle « était enseignée un peu partout sur Terre jusqu’à ce que la démocratisation des calculettes électroniques l’ait chassée des programmes ».
En effet, « à quoi bon enseigner une opération somme toute bien moins nécessaire dans la vie de tous les jours qu’une addition ou une multiplication ? », se demande-t-il. « Je dois dire que même moi, mathématicien, je ne m’en suis jamais servi dans mes recherches », ajoute-t-il.
Si on laisse de côté l’aspect utile de la chose (les calculatrices feront mieux et plus vite), il reste la « beauté du geste » et le fait d’essayer de comprendre les choses plutôt que les utiliser « bêtement ». En plus de donner l’algorithme, Patrick Popescu-Pampu livre son expérience personnelle :
« L’algorithme me sert aussi à intriguer les étudiants qui viennent d’entrer à l’Université. Parfois je leur demande un nombre à quatre ou cinq chiffres. Je calcule alors très vite au tableau sa racine carrée avec deux chiffres après la virgule. Ensuite je les prie de vérifier à la calculette que je ne me suis pas trompé. Ils trouvent cela étonnant et me demandent pourquoi l’algorithme donne le résultat correct. J’ai atteint mon but : avoir éveillé leur curiosité ».
Dans un autre article du CNRS, les mathématiciens Serge Cantat et Stéphane Le Borgne s’intéressant aussi au calcul de la racine carrée (enfin d’une valeur approchée), mais via la méthode de Héron. Attention il s’agit d’une « piste rouge » bien plus difficile à appréhender.
Le 01 septembre 2020 à 07h59
Commentaires (11)
Vous devez être abonné pour pouvoir commenter.
Déjà abonné ? Se connecter
Abonnez-vousLe 01/09/2020 à 08h57
En école d’ingé, on a tendance à tout démontrer pour reprendre les bases lors de la première année. Mais alors celle que j’ai faite ne s’est jamais penché sur la question de la racine.
Je ne connaissais pas la méthode de Héron et je viens d’y jeter un oeil et c’est vraiment malin !
Je me coucherai moins bête ce soir !
Le 01/09/2020 à 09h40
C’est surtout que nous avons des CPU très performant, qui font de milliards de calcul par seconde. Mais qui vérifie que les calculs sont bon?
La méthode de héron est utiliser presque partout car avec 10 itération, on arrive a un écart de 10-e30.
Mais il y a 20ans, on n’avait pas cette puissance de calcul, et par exemple, pour mesurer une distance dans un jeux video (par exemple quake :) ), il y a des astuces pour calculer plus vite les racine carré sans virgule, avec des entiers
Bref les mathématiques font l’informatique d’aujourd’hui ;)
Le 01/09/2020 à 09h42
Etudiant au CNAM , je savais extraire une racine carrée de nombre complexe ( sans passer par les angles) . C’était un peu long, mais exact !
Il faudrait que je retrouve ma méthode……
Le 01/09/2020 à 09h44
En Informatique, on fait son possible pour ne pas calculer de racine carrée, surtout quand on a besoin de performance. On préfère souvent conserver les carrés et adapter les tests en fonction de ça.
Connaitre une distance est rarement nécessaire, le carré d’une distance est souvent suffisant.
Le 01/09/2020 à 09h58
Bah c’est pourtant pas compliqué, pour extraire une racine carré il suffit de résoudre x^y en posant y =1⁄2
Le 01/09/2020 à 10h35
Perso c’est la méthode de la potence que j’ai apprise fin des années 80 en primaire.
Le 01/09/2020 à 10h47
Jolie methode.
Perso je connaissais la methode de heron, et je m’en sers parfois qd j’ai la flemme de sortir le smart ; mais je ne connaissais pas celle ci, tres futée.
Le 01/09/2020 à 11h20
Et pourtant certains le font et heureusement. C’est comme ça qu’un problème a été soulevé par des chercheurs il y a un bon moment sur le calcul en virgule flottante sur des proc Intel Intel Pentium
Le 01/09/2020 à 11h55
C’est la “fast inversed square root” qui permet de calculer 1/sqrt(x), ça s’applique sur les float, mais en faisant des opération entière et binaire. C’est effectivement très puissant car ça nécessite des calculs peu couteux et on obtient une précision suffisante pour faire de la 3D. Après, je te déconseille d’utiliser ça pour faire des calculs dont une imprécision a des conséquences qui dépassent une texture glitchée dans un jeu vidéo.
Soit dit en passant, la mise en œuvre par John Carmack (pour des float32) est sacrément tricky et joue énormément sur des imprécisions du langage C. Attention aux âmes sensibles, voici une horreur à base de référence, pointeur et déréférencement pour accéder à la représentation binaire d’un float :
(et il fait de même pour reconvertir en float) Une version un peu plus propre serait de passer par une structure “union”.
Le 01/09/2020 à 12h22
Ça m’a fait mal au cerveau en école quand on a étudier son “code” :) :)
Et j’utilise encore ce type d’astuce dans des composants embarqués en robotique biologique avec des CPU limité ;)
Le 05/09/2020 à 11h50
Super intéressant, merci NXI