L'algorithme de Briggs

8.1 Un peu d'histoire

Le programme le rappelle : « les procédés par lesquels les mathématiciens ont construit et tabulé le logarithme […] illustrent les liens entre discret et continu ». Au début du XVIIe siècle, il n'existe pas de machine à calculer. Pour multiplier de grands nombres, les astronomes et les navigateurs utilisent des tables de logarithmes : grâce à la relation $\ln(ab) = \ln a + \ln b$, une multiplication devient une addition. L'Écossais John Napier (ou Neper) publie les premières tables en 1614 ; le mot « népérien » vient de son nom. L'Anglais Henry Briggs publie en 1624 des tables très précises, qu'il calcule en extrayant des racines carrées successives : c'est la méthode qui suit.

8.2 Deux idées

On veut calculer $\ln a$, pour un réel $a > 0$. On définit la suite $(a_k)$ par $a_0 = a$ et $a_{k+1} = \sqrt{a_k}$ : on prend des racines carrées successives.

1. Chaque racine carrée divise le logarithme par deux. $\ln\left(a_{k+1}\right) = \ln\left(\sqrt{a_k}\right) = \dfrac12\ln\left(a_k\right)$. Donc $\ln\left(a_k\right) = \dfrac{\ln a}{2^k}$, c'est-à-dire $\ln a = 2^k\ln\left(a_k\right).$
2. Près de $1$, $\ln x \approx x - 1$ (tangente en $1$, leçon 4). Or $a_k = \mathrm{e}^{\ln a / 2^k}$ se rapproche de $\mathrm{e}^0 = 1$ quand $k$ augmente. Donc $\ln a \approx 2^k\left(a_k - 1\right).$

8.3 Le calcul de $\ln 2$

Avec $a = 2$ (valeurs arrondies) :

La calculatrice donne $\ln 2 \approx 0{,}693\,147$. Au chapitre 2, $\ln 2$ figurait parmi les valeurs approchées citées par le programme : la voici.

8.4 En Python

from math import sqrt

def briggs(a, k):
    for i in range(k):
        a = sqrt(a)
    return 2**k * (a - 1)

briggs(2, 20) renvoie 0.6931474097073078. La boucle for extrait $k$ racines carrées successives, puis la fonction renvoie $2^k\left(a_k - 1\right)$.

Attention aux arrondis. L'ordinateur calcule avec environ $16$ chiffres significatifs. Si $k$ est trop grand, $a_k$ est si proche de $1$ que $a_k - 1$ perd presque tous ses chiffres exacts : briggs(2, 60) renvoie 0.0. Pour $\ln 2$, $k = 20$ donne déjà six décimales exactes.

8.5 Un encadrement

D'après la leçon 4, $1 - \frac1x \leq \ln x \leq x - 1$ pour tout $x > 0$. Avec $x = a_k$, puis en multipliant par $2^k > 0$ : $2^k\left(1 - \frac1{a_k}\right) \leq \ln a \leq 2^k\left(a_k - 1\right).$ Pour $a = 2$ et $k = 20$ : $0{,}693\,146\,9 \leq \ln 2 \leq 0{,}693\,147\,5$. L'algorithme donne donc $\ln 2 \approx 0{,}693\,147$ à $10^{-6}$ près, et la valeur $2^k\left(a_k - 1\right)$ est toujours une valeur approchée par excès.

Pourquoi la méthode converge (pour aller plus loin). Avec $h = \frac{\ln a}{2^k}$, qui tend vers $0$ : $2^k\left(a_k - 1\right) = \ln a \times \dfrac{\mathrm{e}^h - 1}{h}$, et $\dfrac{\mathrm{e}^h - 1}{h}$ tend vers le nombre dérivé de l'exponentielle en $0$, qui vaut $1$.