Vous n'avez pas encore de notification

Page d'accueil

Options d'affichage

Abonné

Actualités

Abonné

Des thèmes sont disponibles :

Thème de baseThème de baseThème sombreThème sombreThème yinyang clairThème yinyang clairThème yinyang sombreThème yinyang sombreThème orange mécanique clairThème orange mécanique clairThème orange mécanique sombreThème orange mécanique sombreThème rose clairThème rose clairThème rose sombreThème rose sombre

Vous n'êtes pas encore INpactien ?

Inscrivez-vous !
Racine carrée : le CNRS revient sur un algorithme « jugé inutile »Crédits : francescoch/iStock

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.

11 commentaires
Avatar de Lyaume Abonné
Avatar de LyaumeLyaume- 01/09/20 à 08:57:23

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 !

Avatar de ajangot Abonné
Avatar de ajangotajangot- 01/09/20 à 09:40:01

Lyaume a écrit :

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 !

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

Bref les mathématiques font l'informatique d'aujourd'hui ;)

Avatar de kotec_le_gris Abonné
Avatar de kotec_le_griskotec_le_gris- 01/09/20 à 09:42:45

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......

Avatar de Faith INpactien
Avatar de FaithFaith- 01/09/20 à 09:44:31

ajangot a écrit :

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

Bref les mathématiques font l'informatique d'aujourd'hui ;)

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.

Avatar de Charly32 Abonné
Avatar de Charly32Charly32- 01/09/20 à 09:58:55

Bah c'est pourtant pas compliqué, pour extraire une racine carré il suffit de résoudre x^y en posant y =1/2 :embarassed:

Édité par Charly32 le 01/09/2020 à 09:59
Avatar de Z-os INpactien
Avatar de Z-osZ-os- 01/09/20 à 10:35:31

Perso c'est la méthode de la potence que j'ai apprise fin des années 80 en primaire.

Avatar de Drepanocytose Abonné
Avatar de DrepanocytoseDrepanocytose- 01/09/20 à 10:47:32

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.

Avatar de the_frogkiller Abonné
Avatar de the_frogkillerthe_frogkiller- 01/09/20 à 11:20:37

ajangot a écrit :

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

Bref les mathématiques font l'informatique d'aujourd'hui ;)

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

Avatar de tazvld Abonné
Avatar de tazvldtazvld- 01/09/20 à 11:55:52

ajangot a écrit :

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

Bref les mathématiques font l'informatique d'aujourd'hui ;)

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 :

i = * ( long * ) &y;

(et il fait de même pour reconvertir en float) Une version un peu plus propre serait de passer par une structure "union".

Avatar de ajangot Abonné
Avatar de ajangotajangot- 01/09/20 à 12:22:58

tazvld

Ç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é ;)

Il n'est plus possible de commenter cette actualité.
Page 1 / 2