ANNEXE E. C ALCUL DES FONCTIONS DE BIBLIOTHÈQUE ÉLÉMENTAIRES
8. Calcul de la racine carrée pour x appartenant à (0, oo)
Il s’agit probablement de l’un des plus vieux algorithmes toujours en vigueur, dont la paternité
reviendrait à Héron d’Alexandrie (Pr siècle). Grosso modo, la technique consiste à obtenir un
ordre de grandeur «convenable » de la racine carrée puis à appliquer la méthode de Newton
dont la convergence est, rappelons-le, quadratique. En calcul binaire, on pourra poser :
5 = 22mrl
avec i < n < 1 donc qrnP1 < 2 < 4”.
On obtient alors fi = 2”fi.
À présent, il nous reste à calculer fi. Cette opération est réalisée au moyen de la fraction
continue :
fi = 7 _ ,:;;;;;A2 _ 4 102 7-41 .
172 + 15 7-2
En introduisant cette valeur dans la formule de Héron-Newton :
a+1 = (a + nlyk)P
après trois tours d’itération, on obtient alors une précision relative sur y2 qui sera meilleure que
4,5 10-g.
Exemple
On se propose de calculer &7584,34833. On établit que :
4? < 17 584,348 33 < 48
et donc : dl7 584,348 33 = 256dO,268 315 862.
que
L’application de la fraction continue donne : fi = 0,518 098 408 4, laquelle, introduite dans
la formule de Newton-Héron, permet d’obtenir : fi = 0,517 992 155 5 à la première itération,
et J;F = 0,517 992 144 7 à la seconde.
En définitive, on trouve : J17584,348 33 = 132,605 989, tous les chiffres significatifs sont
exacts.
9. Éléments de bibliographie
A. RALSTON et H.S. WILF (1965) Méthodes mathématiques pour calculateurs arithmétiques,
Dunod.
427
8. Calcul de la racine carrée pour x appartenant à (0, oo)
Il s’agit probablement de l’un des plus vieux algorithmes toujours en vigueur, dont la paternité
reviendrait à Héron d’Alexandrie (Pr siècle). Grosso modo, la technique consiste à obtenir un
ordre de grandeur «convenable » de la racine carrée puis à appliquer la méthode de Newton
dont la convergence est, rappelons-le, quadratique. En calcul binaire, on pourra poser :
5 = 22mrl
avec i < n < 1 donc qrnP1 < 2 < 4”.
On obtient alors fi = 2”fi.
À présent, il nous reste à calculer fi. Cette opération est réalisée au moyen de la fraction
continue :
fi = 7 _ ,:;;;;;A2 _ 4 102 7-41 .
172 + 15 7-2
En introduisant cette valeur dans la formule de Héron-Newton :
a+1 = (a + nlyk)P
après trois tours d’itération, on obtient alors une précision relative sur y2 qui sera meilleure que
4,5 10-g.
Exemple
On se propose de calculer &7584,34833. On établit que :
4? < 17 584,348 33 < 48
et donc : dl7 584,348 33 = 256dO,268 315 862.
que
L’application de la fraction continue donne : fi = 0,518 098 408 4, laquelle, introduite dans
la formule de Newton-Héron, permet d’obtenir : fi = 0,517 992 155 5 à la première itération,
et J;F = 0,517 992 144 7 à la seconde.
En définitive, on trouve : J17584,348 33 = 132,605 989, tous les chiffres significatifs sont
exacts.
9. Éléments de bibliographie
A. RALSTON et H.S. WILF (1965) Méthodes mathématiques pour calculateurs arithmétiques,
Dunod.
427