Héron vit à Alexandrie, en Égypte romaine, probablement au I^er siècle de notre ère ; on ne sait presque rien de sa vie. Il enseigne et écrit des traités pratiques : machines à vapeur (l'éolipile), automates de théâtre, instruments de visée pour l'arpentage, et un traité de mesure des surfaces et des volumes, les Metrica, dont le manuscrit n'a été retrouvé, à Constantinople, qu'à la fin du XIX^e siècle. C'est là que figure la célèbre formule de Héron, qui donne l'aire d'un triangle à partir de ses trois côtés. Pour un triangle de côtés $7$, $8$ et $9$, elle conduit à $\sqrt{720}$, et Héron explique comment en obtenir une valeur approchée.

Voici le passage, dans la traduction donnée par Jean-Luc Chabert dans Histoires d'algorithmes :

Puisque $720$ n'a pas de côté rationnel, nous extrairons le côté avec une très petite différence de la façon suivante. Comme le premier nombre carré plus grand que $720$ est $729$ qui a pour côté $27$, divise $720$ par $27$ ; cela fait $26$ et $\frac{2}{3}$ ; ajoute $27$, cela fait $53$ $\frac{2}{3}$ ; prends-en la moitié, cela fait $26$ $\frac{1}{2}$ $\frac{1}{3}$. Car $26$ $\frac{1}{2}$ $\frac{1}{3}$ multiplié par lui-même donne $720$ $\frac{1}{36}$, de sorte que la différence (sur les carrés) est $\frac{1}{36}$. Si nous voulons rendre cette différence inférieure encore à $\frac{1}{36}$, nous mettrons $720$ $\frac{1}{36}$ trouvé tout à l'heure à la place de $729$ et en procédant de la même façon…

« $720$ n'a pas de côté rationnel » : un carré d'aire $720$ a pour côté $\sqrt{720}$, qui n'est pas une fraction. On va donc en chercher une valeur approchée. Héron écrit les fractions comme les Égyptiens, en sommes de fractions de numérateur $1$ : « $26$ $\frac{1}{2}$ $\frac{1}{3}$ » signifie $26 + \frac{1}{2} + \frac{1}{3} = 26 + \frac{5}{6}$.

• On part de $27$, car $27^2 = 729$ est le premier carré au-dessus de $720$.
• On divise : $\dfrac{720}{27} = 26 + \dfrac{2}{3}$.
• On ajoute $27$ : $26 + \dfrac{2}{3} + 27 = 53 + \dfrac{2}{3}$.
• On prend la moitié : $\dfrac{1}{2}\left(53 + \dfrac{2}{3}\right) = 26 + \dfrac{5}{6}$.

Héron vérifie ensuite son résultat en l'élevant au carré :

donc

Le carré de côté $26 + \frac{5}{6} \approx 26{,}8333$ a donc une aire qui ne dépasse $720$ que de $\frac{1}{36}$. En effet, $\sqrt{720} \approx 26{,}832\,816$ : en une seule étape, on est passé d'une erreur d'environ $0{,}17$ à une erreur d'environ $0{,}000\,5$.

La dernière phrase est la plus importante : pour faire mieux, on recommence avec la valeur obtenue à la place de $27$. En langage moderne, pour approcher $\sqrt{a}$, on part d'une valeur $u_0$ et l'on calcule

C'est un algorithme : une suite d'opérations simples, répétée autant de fois que nécessaire. C'est aussi une suite définie par récurrence, et toute la suite du texte consiste à comprendre pourquoi elle tend vers $\sqrt{a}$, et à quelle vitesse.

On part d'un carré $ABCD$ d'aire $a$, donc de côté $\sqrt{a}$. On prolonge les côtés $[AD]$ et $[BC]$ pour obtenir un rectangle $ABEF$ dont le côté $[AF]$ mesure un nombre $r > \sqrt{a}$ (une valeur approchée par excès de $\sqrt{a}$, comme $27$ pour $\sqrt{720}$). On trace la médiatrice du segment $[AE]$ : elle coupe la droite $(AF)$ en un point $J$. On complète le rectangle $ABJ'J$. On va démontrer que

Avant de démontrer, regardons. Avec $a = 720$ et $u_0 = 27$, voici les premiers termes, comparés à $\sqrt{720} \approx 26{,}832\,815\,729\,997$.

L'erreur passe de l'ordre de $10^{-1}$ à $10^{-4}$, puis $10^{-9}$, puis $10^{-19}$ : l'exposant fait plus que doubler à chaque étape. Une calculatrice affiche $u_3$ et $\sqrt{720}$ avec exactement les mêmes chiffres.

Une calculatrice ne connaît que des opérations élémentaires sur des chiffres. Pour une racine carrée, elle utilise soit une méthode « chiffre par chiffre », proche de la méthode de la potence apprise autrefois à l'école, soit une méthode de type Newton, selon les modèles. Dans les processeurs d'ordinateur, la norme IEEE 754, qui fixe depuis 1985 la façon de représenter et de calculer les nombres à virgule, impose que la racine carrée soit correctement arrondie : le résultat doit être le nombre représentable le plus proche de la vraie valeur. Les circuits y parviennent avec des algorithmes chiffre par chiffre ou avec des itérations de type Newton suivies d'une correction finale, selon les fabricants.

Un détail rend Newton particulièrement intéressant pour un circuit : la formule de Héron demande une division $\frac{a}{u_n}$, opération lente. On préfère souvent calculer d'abord $\frac{1}{\sqrt{a}}$, dont la méthode de Newton n'utilise que des multiplications, puis multiplier par $a$ (car $a \times \frac{1}{\sqrt{a}} = \sqrt{a}$).

Dans un jeu vidéo en trois dimensions, il faut sans cesse normaliser des vecteurs (les ramener à une longueur $1$, par exemple pour calculer l'éclairage d'une surface), donc diviser leurs coordonnées par $\sqrt{x^2 + y^2 + z^2}$. À la fin des années 1990, ces calculs coûtaient cher. Le code source du jeu Quake III Arena (1999), rendu public en 2005, contient une fonction devenue célèbre :

float Q_rsqrt(float number) {
    long i; float x2, y;
    x2 = number * 0.5F;
    y  = number;
    i  = * (long *) &y;             // lire les bits du nombre comme un entier
    i  = 0x5f3759df - (i >> 1);     // la constante « magique »
    y  = * (float *) &i;
    y  = y * (1.5F - (x2 * y * y)); // une étape de la méthode de Newton
    return y;
}

Elle calcule $\frac{1}{\sqrt{x}}$ en deux temps :

• une première approximation, obtenue par une astuce sur l'écriture binaire des nombres à virgule : comme cette écriture contient l'exposant de $2$, décaler les bits d'un cran revient presque à diviser le logarithme de base $2$ par deux, donc à prendre une racine carrée ; la constante $\text{5f3759df}$ (en hexadécimal) corrige le résultat ;
• une étape de Newton appliquée à l'équation $h(y) = \dfrac{1}{y^2} - x = 0$, qui donne la formule $y_{n+1} = y_n\left(\dfrac{3}{2} - \dfrac{x}{2}y_n^2\right)$, sans aucune division.

Après cette unique étape, l'erreur relative ne dépasse pas environ $0{,}2\,\%$, largement assez pour l'œil d'un joueur. L'origine de la constante est restée longtemps mystérieuse ; des enquêtes publiées au milieu des années 2000 font remonter l'astuce à des travaux antérieurs, chez Silicon Graphics et ailleurs, sans qu'un auteur unique soit établi avec certitude. Les processeurs actuels ont des instructions dédiées, et l'astuce n'est plus utile, mais elle reste un bel exemple d'algorithme qui mêle représentation des nombres, logarithme et méthode de Newton.

Le programme ci-dessous ne reproduit pas l'astuce binaire, impossible à écrire simplement en Python, mais il montre l'effet de l'étape de Newton sans division à partir d'une première approximation grossière.

L'erreur relative passe d'environ $3\,\%$ à environ $0{,}14\,\%$, puis à environ $3 \times 10^{-6}$, puis à environ $1{,}2 \times 10^{-11}$ : la convergence est encore quadratique.